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: 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: Write the following methods of this class:

Part 3

Test your priority heap with the objects of the class Something.
This is a takehome exam from CSci 2101 course.

The views and opinions expressed in this page are strictly those of the page author. The contents of this page have not been reviewed or approved by the University of Minnesota.