The file sorts.java contains | Computer Science homework help

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:

<T extends Comparable<? super T>>

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<Integer> 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.