CIT594 Second Quiz

CIT594 Second Quiz
Spring, 2004

Name_________________________________________

Please read all questions carefully. Answer questions briefly and to the point. You have plenty of room for correct answers. Point values are in parentheses

For the following questions, assume the following class has been defined:

public class Student {
    String name;
    int studentId;
    ...other stuff...
}

Student names and academic records are not necessarily unique, but a studentId uniquely identifies a student. There may be different objects representing the same student.

For the following questions, write only the code that is asked for; do not include extra code. Assume that your answers will be in an appropriate class or method, and do not write that surrounding class or method. You will lose points for inappropriate code.

(10 pts) Write a complete equals method to put into the Student class.

   public  boolean  equals( Object  x) {
	
       if ( ! (x instanceof Student)  ) return false;
	   
       return ((Student) x).studentId  ==  studentId;
   }

  Note the cast from Object to Student!

Somewhere in the program, there is the declaration
Set myStudents = new TreeSet(); In order for this to work,
1. (2 pts) What change needs to be made to the definition of the Student class?
  
  It must implement Comparable
2. (2 pts) What additional method (besides equals) needs to be added to the Student class?
  
  public int compareTo(Object o) (name alone is enough)
3. (8 pts) Write the necessary method.
  
  Long version:
```
    public int compareTo(Object o) throws ClassCastException {
        if (o instanceof Student)
            return studentId - ((Student)o).studentId;
        else
            throw new ClassCastException("Not a Student!");
    }
```
  Short, equivalent version:
```
    public int compareTo(Object o) {
        return studentId - ((Student)o).studentId;
    }

  Note the cast from Object to Student!
```
Somewhere in the program, there is the declaration:
Set myOtherStudents = new HashSet(myStudentSorter);
In order for this to work,
1. (2 pts) What additional method (besides equals) needs to be added to the Student class?
  
  public int hashCode() (name alone is enough)
2. (6 pts) Write the necessary method.
```
    public int hashCode() {     (must use only studentId)
        return studentId;         
    }
```
Suppose you want to replace the declaration in question #2 with:
Set myStudents = new TreeSet(myNameComparator);
(This is supposed to keep the students in sorted order by their name field.) You can assume that two Student objects with equal StudentId fields will also have equal name fields (but equal names do not guarantee equal student IDs.)
1. (2 pts) What change needs to be made to the definition of the Student class?
  
  No change is needed
2. (2 pts) What method needs to be added to the NameComparator class?
  
  public int compare(Object o1, Object o2) (name alone is enough)
3. (8 pts) Write the necessary method.
```
    public int compare(Object o1, Object o2) {
        int x = ((Student)o1).name.compareTo(((Student)o2).name);
        if (x != 0) return x;  // equal names don't guarantee same student
        return ((Student)o1).studentId - ((Student)o2).studentId;
    }
```
  You need to compare names first, so that students are sorted by names. But you still need to compare students id - otherwise, students with the same names but different id will be stored as one single student. -2 for wrong method signature, -6 for not comparing names, -6 for not comparing id.
4. (2 pts) To make this work, do you need to change the definition of equals? Why or why not?
  
  No, because equal students still have equal IDs.
5. (8 pts) Write a method to print the student names in order.
```
    static void print(Set students) {
        for (Iterator iter = students.iterator(); iter.hasNext();) {
            Student element = (Student) iter.next();
            System.out.println(element.name);
        }
    }
```
(8 pts) State Dr. Dave's four rules for doing recursion.
1. Do the base case(s) first.
2. Recur only with a simpler case.
3. Don't modify non-local variables.
4. Don't look down.
In the following method, assume that makeName() takes constant time and generates random strings:
```
   public Vector makeNames(int n) {
       Vector names = new Vector();
       for (int i = 0; i < n; i++) {
           String name = makeName();
           if (!names.contains(name)) {
               names.add(name);
           }
       }
       return names;
   }
```
1. (3 pts) What is the big-O running time of this method?
  
  O(n²), or quadratic
2. (3 pts) What is the simplest change that you could make to this method to make it faster?
  
  Replace the Vector with a HashSet.
3. (4 pts) If you made the above change, what would be the big-O running time of the resultant method? Why?
  
  O(n), because the contains test would go from linear time to constant time.

(8 pts) Assume the following class has been defined:

public class Tree {
    public String value;
    private Vector children;
    ...other stuff...
}

Write a print() method for this class that prints the values of the tree in preorder, one value per line.

    void print() {
        System.out.println(value); // OK to use size() and get(i) or elementAt(i) instead
        for (Iterator iter = children.iterator(); iter.hasNext();) {
            Tree element = (Tree) iter.next();
            element.print();
        }
    }

I have defined three methods for searching trees: depth-first, breadth-first, and depth-first iterative deepening. Suppose I take these methods and, without changing them in any way, apply them to a Graph. (The only difference between my Tree class and my Graph class is that the Graph class allows cycles.) Assume that the graph does contain, somewhere, a "goal node."
1. (3 pts) What will happen if I try to do a depth-first search on this graph? That is, will the goal node be found, and if so, how long will it take?
  
  The method may get caught in a loop. (Not required: If successful, it will take O(n) time, where n is the number of nodes on the graph.)
2. (3 pts) What will happen if I try to do a breadth-first search on this graph? That is, will the goal node be found, and if so, how long will it take?
  
  The method will succeed, and will take O(n^k) time, where k is the average branching factor and n is the distance to the goal node.)
3. (3 pts) What will happen if I try to do a depth-first iterative deepening search on this graph? That is, will the goal node be found, and if so, how long will it take?
  
  The method will succeed, and will take O(n^k) time, where k is the average branching factor and n is the distance to the goal node.)

(5 pts) A binary tree has the following walks:

Preorder:
D C G B A F E
Inorder:
G C D A B F E
Postorder:
G C A E F B D

Draw the binary tree.

(8 pts) For an array containing random values, what is the running time of the following method (big-O notation), and does it successfully find the maximum value in the array?
```
   public static int max(int[] array) {
       int direction = 1;
       int middle = array.length / 2;
       int value = array[middle];
       for (int i = middle; i >=0 && i < array.length; i += direction) {
           if (array[i] > value) {
               value = array[i];
               direction = -direction;
           }
       }
       return value;
   }
```
O(n) on size of array, not guaranteed to find maximum. Explanation (not required): The expected running time is approximately linear on the size of the array, because we are likely to change direction only a few times. Because the method stops as soon as it runs off one end of the array, it may never examine values near the other end.