1. The ﬁle Sorts.java contains several different sorting methods that operate on integer arrays. We want to make these algorithms generic, like we did with the Search methods, so that they will work on any object type. To do this, convert the static methods to generic methods using the same steps as in Homework 5. Be careful to consider which method parameters (and possibly, local variables) must also be converted to use the type parameter.
As with the search methods, sorting methods must use the compareTo method when comparing objects to determine their order. So again we have to ensure that objects in the arrays we sort implement the Comparable interface and modify the code to
use compareTo in place of greater than/less than operators. Refer back to Homework 5 and the referenced section of the textbook.
2. Add a method isSorted to this class. This method is for determining if an array is sorted or not, and should also be a generic method.
3. As with the methods in Searches.java, if I give you an array of objects to sort that don’t implement Comparable, the sorting method will fail (hopefully at the compile stage!). To ensure that the type parameter used by our generic methods “screens out” object types that aren’t searchable or sortable, replace the simple type parameter in the method header (after the keyword static) with the following:
By adding this more complex form of type parameter, things that can’t be compared won’t compile if someone tries to pass an array of a non-comparable type. Furthermore, things that inherit from a class that implements Comparable will work.
4. Test that arrays of type String work with your methods by writing a test program in a separate class to test your changes to the Sorts class. This program will perform the following operations:
◦ open a ﬁle (you’ll get the ﬁle’s name from the command-line) that contains a
count, then a list of dictionary words, one word per line
the ﬁrst line in the ﬁle is the number of words in the ﬁle; use this to create an
array of the proper size read words from each subsequent line of the ﬁle into the array test each sorting method as described below
5. Download and use these test ﬁles: american-words.35, american-words.80, dictionary.txt,
and large ﬁle of unsorted strings (the ﬁrst three ﬁles are already sorted).
6. Write a real simple program to test that an array of some non-comparable type does
NOT work. use your Polynomial class for this test.
Part 1: Questions 1. (2 points) When deriving a new class from an existing class using inheritance, which instance variables are accessible to the derived class? Write down the best answer:
those with the private access modiﬁer
those with the protected access modiﬁer
those with no access modiﬁer
4. both 1 and 2
5. both 2 and 3
2. (2 points) Show a simple example of how an alias is created in Java. For this example,
you might use String objects.
3. (4 points) Read the code below and determine what is output when it runs. Write out your
answer and show the contents of the array tee. Assume uninitialized array slots contain
ess = new int ;
ess = 101;
tee = ess;
ess = -3;
4. (4 points) Give the order of growth estimate of the following functions using Big-O
◦ 13N + 2
◦ 13N + 2 + N
◦ 13N + 2 log2N
◦ 3N log2N + 23N
Part 2: Stack Questions (26 points)
1. (9 points) Practice your understanding of stacks by drawing the abstact diagram of a stack and its contests after each stack operation. If there is no change to the stack’s state after an operation, just say “No Change.” Be sure to label the top of stack:
LinkedStack stk = new LinkedStack();
int x = stk.top();
int y = stk.top();
stk.push(x + y);
int x = stk.top();
int y = stk.top();
stk.push(x * y);
2. (9 points) Assume we’re using a LinkedStack to implement the stack from the previous problem. Show the state of the stack after each instruction executed in the above problem. Be sure to label the top of stack properly.
3. (4+4 points) Using the code for class LinkedStack in your text, show how to add methods equals and toString, for a stack. Just write these out here, don’t print out the whole class.
Two stacks are equal if they have the same size, and contain the exact same items in the same order.
The string representation toString should return of a stack is just the
word Top: followed by each element separated by a space. Note this does break the stack discipline (that you can only see the ﬁrst item in the stack) but is useful for debugging applications that use the stack.