Problem Set 6 FAQ

Problem 2
Problem 4
Problem 5

If you don’t see your question here, post it on Piazza or come to office hours! See the links in the navigation bar for both of those options.

Problem 2

For problem 2, part 1, I’m having trouble determining the time efficiency. Do you have any suggestions?

Start by analyzing the inner loop. One way to do this is to make a table that records the number of nodes accessed by each of the two methods calls (getItem and addItem) for each value of j:
```
j    # nodes accessed by getItem    # nodes accessed by addItem
0
1
...
```
You won’t need to fill it in entirely in order to see a pattern emerge. Then you can use the pattern to determine an approximate expression for the overall number of accesses made by one execution of the inner loop in the worst case.

Next, analyze the outer loop. Here again, you can use a table to determine a pattern for the number of accesses made by a given call of getItem(i) as a function of i. Then you can use the pattern to determine the overall number of accesses made by all of the calls to getItem(i).

Finally, because each of the m iterations of the outer loop performs a full execution of the inner loop, the overall running time will have the following form:
```
(total # accesses by calls to getItem(i)) + (m * (# accesses by inner loop))
```
For problem 2, part 2, I’m having trouble thinking of ways to improve the efficiency. Do you have any suggestions?

In lecture and lab, we’ve seen at least two different examples in which we improved the efficiency of a method like intersect() that is a client of the LLList class. One way to improve the efficiency of intersect() is to do something similar to what we did in those examples. (Don’t forget that we post the solutions to the lab exercises, so you may want to review those solutions!)

In addition to the technique that we used in lecture and lab, it may also be possible to take other steps to improve the efficiency of the intersect() method.
For problem 2, part 2, does the order of the items in the intersection matter?

No, and you should feel free to use this fact as part of your efforts to improve the efficiency of the algorithm.

Problem 4

In Problem 4, do we need to use an iterator?

No, and we don’t recommend using one.

Iterators can be useful when you are writing code that is a client of a collection class – i.e., a method or program that is outside the class and that uses an instance of the class in some way.

In this problem, you aren’t writing client code. Rather, you are adding non-static methods to the collection classes themselves. Because these new methods are inside their respective classes, they have access to the private fields of their class, and thus an iterator is not needed.

Rather, when implementing the ArrayList version of removeAll(), you should write code that directly manipulates the underlying array of items. When implementing the LLList version of removeAll(), you should write code that directly manipulates the underlying linked list of items.
In Problem 4, can our removeAll() methods call the existing non-static methods (e.g., getItem())?

In theory, yes. However, for full credit, you will need to make sure that your use of these other methods still allows your removeAll() methods to execute in linear (i.e., O(n)) time.
I haven’t been able to figure out how to make the ArrayList version of removeAll() have a runtime of O(n). Any suggestions?

This is indeed a tricky problem. Try drawing a concrete array on paper that includes multiple occurrences of a given value v, and think about how you could efficiently reorder the elements so that all occurrences of v are removed. In order to do so in linear time, a given element of the array should move at most once.

Problem 5

For problem 5, can we make use of the LLList class, or do we need to create our own linked list class from scratch?

You need to implement your own linked list. However, you do not need to write a separate class for the linked list itself. The only additional class that you will need besides LLBag is a class for the nodes in the linked list, which should be a private inner class called Node within your LLBag class. See the LLList, LLStack, and LLQueue classes for examples of this.

You should use a field within your LLBag class to hold a reference to either the first node of the linked list or the dummy head node, if you choose to use one. Then, you should write LLBag versions of the methods found in ArrayBag, rewriting them so that instead of manipulating an array of items they manipulate a linked list of Node objects.