1. The file 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 file (you’ll get the file’s name from the command-line) that contains a
count, then a list of dictionary words, one word per line
the first line in the file is the number of words in the file; use this to create an
array of the proper size
◦
◦ read words from each subsequent line of the file into the array
◦
test each sorting method as described below
5. Download and use these test files: american-words.35, american-words.80, dictionary.txt,
and large file of unsorted strings (the first three files 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:
1.
those with the private access modifier
2.
those with the protected access modifier
3.
those with no access modifier
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
0.
int[] ess;
int[] tee;
ess = new int [8];
ess[4] = 101;
tee = ess;
ess[4] = -3;
System.out.print(tee[6]);
4. (4 points) Give the order of growth estimate of the following functions using Big-O
notation:
◦ 13N + 2
◦ 13N + 2 + N
2
◦ 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();
stk.push(7);
stk.push(5);
stk.push(4);
int x = stk.top();
stk.pop();
int y = stk.top();
stk.pop();
stk.push(x + y);
int x = stk.top();
int y = stk.top();
stk.push(x * y);
stk.pop();
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 first item in the stack) but is useful for debugging
applications that use the stack.
