UMM CSci 2101 Problem sets, Fall 2004: Takehome 2

CSci 2101 Data Structures: Takehome exam II.

Due Monday, April 18th at 8pm.

Please submit the paper-and-pencil part to Elena's office (slide it under the door if the door is closed). The program part is to be submitted by e-mail to Elena. Absolutely no late submissions are accepted, the deadline is firm. Don't try to submit at the last minute, allow extra time for bounced e-mail and similar things. Double-check to make sure that you are submitting the right files (only .java files need to be submitted).

You may use any printed and online materials and your own problem sets. You are allowed to talk to each other about general approaches to the problems. You may also discuss particular compilation issues, but you may not reproduce any part of another person's code or a solution of a paper-and-pencil problem. You may not get any help on the assignment from anyone else outside of the class.

Problem 1 (12 points)

Part 1

You are given this implementation of a binary search tree of integers. Write a recursive method mirror() in the IntNode class that turns a tree into its mirror image by switching the left and the right subtrees. Write the starting method mirror() in the class IntBST and the testing program. Print out the resulting tree in in-order and pre-order to check that you "mirrored" it correctly. Try your method on several trees, including an empty tree. Comment out your test cases.

Part 2

Your goal is to write a method of IntBST which compares two trees and returns true if they are exactly the same, false otherwise. You will write a recursive method of the class IntNode:


public boolean isSame(IntNode otherTreeNode)

The method takes another IntNode and returns true if the subtree rooted at this node is the same as the subtree rooted at the node otherTreeNode, and false otherwise.

Write the method


public boolean isSame(IntBST otherBST)

of IntBST class that takes another tree and starts the recursion. Test your program on several trees, including the cases when both or one of the trees are empty.

Problem 2, paper-and-pencil (8 points)

You are given the following program:


public class GuessWhat {
    public static void main(String [] args) {
	Object [] array = new Object[5];
	array[0] = new Object();
	array[1] = new A(2);
	array[2] = new A(2);
	array[3] = new B(2, 3);
	array[4] = new B(2, 5);
	
	for (int i = 0; i < array.length; ++i) {
	    System.out.println(array[i]);
	}
	
	System.out.println(array[0].equals(array[2]));
	System.out.println(array[1].equals(array[2]));
	System.out.println(array[1].equals(array[3]));
	System.out.println(array[3].equals(array[4]));
	System.out.println(array[3].equals(array[1]));
	System.out.println(((A) array[3]).equals(array[4]));
    }
}

class A {
    protected int one;

    public A(int n) {
	one = n;
    }

    public boolean equals(Object obj) {
	A a = (A) obj;
	if (one == a.one) return true;
	return false;
    }

    public String toString() {
	return "one = " + one;
    }
}

class B extends A {
    protected int two;

    public B(int n, int m) {
	super(n);
	two = m;
    }

    public boolean equals(Object obj) {
	B b = (B) obj;
	if (one == b.one && two == b.two) return true;
	return false;
    }

    public String toString() {
	return "one = " + one + " two = " + two;
    }
    
}

Question 1.Draw the memory diagram after all of the objects have been created. Show the "true" class of each object.

Question 2. For each call of the method equals in main write down which of the methods was called. You have 3 options: the method of the class Object, A, or B. Clearly say what variables are compared by each method and explain the results. Note that the equals method of Object comprares the addresses only.

As usual, it's OK to run the program. If one of the print statements gives a run-time error, explain the error (i.e. which method was called and what in that method has caused the error), comment out the line, and run the program again.

Problem 3 (15 points)

Part 1

Rewrite the class PriorityHeap so that it stores elements of any class that implements Comparable interface. I.e.instead of the array of elements of class Item your priority heap will have an array of class Comparable, and all the comparisons to find the right place for an element will be done using compareTo() method. Specifically, the new PriorityHeap class will have the following public methods:

public PriorityHeap() - the constructor,
public boolean isEmpty() - the method to test if the priority heap is empty,
public void enqueue(Comparable element) - enqueue the element
public Comparable dequeue() - dequeue the element with the highest priority
public void print() - print the queue using the elements' toString() method

You may write private helper methods in addition to the public ones.

Do not create any new objects within the PriorityHeap clas, just assign the references.

Test your program on classes String and Integer.

Part 2

Write a class Something that implements Comparable interface. The class will have the following 2 variables:

int number
String str

Write the following methods of this class:

public Something(int n, String s) that initializes the two variables,
public int compareTo(Object obj) which compares two Somethings. Somethings are compared in the following way: first we compare the two numbers. If one is greater than the other one then that object is greater. If the two numbers are equal, we compare the two strings, and the object with the string that's alphabetically greater than the other one is greater. If the two numbers and the two strings are the same, then the objects are equal.
Make sure that you follow the definition of compareTo() method: return a negative number if this object is smaller than the other object, 0 if they are equal, and a positive number otherwise.
public String toString() returns the String containing the number and the string of the object.

Part 3

Test your priority heap with the objects of the class Something.

This is a takehome exam from CSci 2101 course.