CS 50 Homework 13 (Section 2 Prof. Brown)
Due by class time Wednesday, May 1
- Review Exercises R15.6 through R15.9 (page 645). Justify your answer in each
case.
- 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.
- 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 above?
- Study the code for the LinkedList2 class.
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 13 and drop this folder into the drop box. If
needed, 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.