CS 50 Homework 12 (Section 1 — Prof. Marshall)

1. Review Exercises R15.6 through R15.9 (page 645). Justify your answer in each case.

2. Here is a simple algorithm to remove duplicates from an array. Look at a[i]. Count how many times it occurs in a. If the count is larger than 1, remove a[i] by shifting the remaining elements over to fill in the gap. For example, if the array has values

         2  6  10  2  7  5  10  6  5  3
   

   then the array would be changed to

         2  7  10  6  5  3
   

   What is the growth rate of this algorithm in big-O notation, as a function of array size n? Justify your answer.

3. Consider the following algorithm to remove all duplicates from an array. Sort the array using quicksort (or mergesort). Then, for each element in the array, look at its next neighbor to see whether or not it is present more than once. If it isn't, keep going; otherwise remove it by shifting the remaining elements over, and then check again. For example, removing duplicates from the above array with this algorithm would result in

         2  3  5  6  7  10
   

   What is the growth rate of this algorithm in big-O notation, as a function of array size n? Justify your answer. Is it a faster algorithm than the one from part 2?

4. Study the code for the LinkedList2 class discussed in lecture. This implementation is fairly basic, but differs somewhat from the one in Chapter 16 of the textbook. It uses singly-linked nodes and keeps track of both the head and tail of the list.

   Add the following new methods to LinkedList2 to enhance its functionality, and provide a test program called TestList that demonstrates your new methods:

   • public boolean equals(LinkedList2 other)
     This method compares the list with the other list and returns true if and only if the two lists are the same length and contain equal elements in corresponding positions. You may assume that all elements have an equals method available.

   • public void insertAfter(Object find, Object newElement)
     This method searches from the beginning of the list for an element that equals find. If such an element is located, then newElement is inserted immediately after it. If the find element is not in the list, then the list is not changed.

   • public void insertBefore(Object find, Object newElement)
     This method is like insertAfter, except that newElement is inserted immediately before the first occurrence of the find element.

   Files to submit: LinkedList2.java, TestList.java

Turning in Your Homework

Write out your answers to parts 1-3 on paper and turn this in during class. For part 4, put the specified files into a single folder named Your Name HW 12 and drop this folder into the drop box. If you are an off-campus student, you may copy your folder to a CLEAN floppy disk (one containing no other files or folders), and hand this in at the beginning of class, instead of using the drop box.