Midterm Exam 3

This is a take-home exam with 3 problems. The number of points for each problem appears in brackets next to the problem number. There are 100 points total on the exam.

This exam is open book, which means you can consult the textbook, the contents of the /home/cs230/download puma directory, your own copies of the handouts, assignments/labs and solutions, and lecture notes to solve the problems. However, I (Takis) am the only person with whom you can talk about the exam. I will clarify the problems if you have trouble understanding them, but because this is an exam, I cannot help you solve the problems.

All of the problems require a hardcopy submission and a softcopy submission. Hand over the hard copy before the beginning of next class. Put the soft copies of your files in a folder called Exam3 and place them inside your own home drop directory before the beginning of next class.

If you cannot get a program to work completely, you should turn in what you have so that you get partial credit. If your program does not work correctly, you must include a note in your file header that describes what aspects of your program do and do not work, and what is the overall strategy that you were trying to pursue. Be sure to use copious println() statements when debugging, but comment them out for the final submission.

Your solutions will be evaluated not only on the basis of correctness, but also on the basis of good programming style and good design of classes. Your implementations should be clear and concise, contain effective comments, and be thoroughly tested.

Good Luck!

Problem 1: [20 pts] Heapsort implementation

Create a class HeapSort.java which sorts using a heap as described in the textbook and in class. Your HeapSort() should use a MaxHeap. It should take as input an array of Comparable elements and return them sorted in the same array.
Using the LinkedMaxHeap implementation in the javafoundations will require only a few lines of code. However note that LinkedMaxHeap is incomplete because it needs the implementation of the getMax() method (which can be accomplished in 1-2 line(s) of code).

In your HeapSort class include a main() method that acts as a driver to show correctness of your code. You should make sure that your code works correctly. Of course, feel free to define any helper methods that you think are appropriate and useful in this particular application.

Finally, answer the following questions:

1. Draw the UML diagram of the relevant classes you are using in your solution. (Hand-drawn UML is fine.)
2. What is the running time (in Big-Oh notation) of your implementation?
3. Is it possible to make heapsort run faster by a constant factor with a different implementation? Explain.

Problem 2: [60 pts] Graph implementation

Create AdjMatGraph.java which implements the (linked) Graph interface using an adjacency matrix for the edges. Your implementation should allow for an undirected graph to be represented. It should be appropriate to use an array of generic type T to hold the graph's vertices, and a 2-D array of booleans as your adjacency matrix of edges: The i-th vertex has as adjacent vertices those that appear as "true" in the i-th row of the edge array.

The contstructor should initialize an empty graph and allocate space for the vertices and edges arrays.
Adding a vertex should first check to see if there is space in the vertices and edges arrays and expand them as needed.
Deleting a vertex should first locate it in the vertices array, then delete it from there and delete its column and row from the edges array. Some array compacting is necessary as we should not leave gaps of deleted vertices in these arrays.
Adding or deleting an edge should first locate the indices of the edge's endpoints in the edges array and then update the edges array accordingly. Checking if a graph is empty and reporting its size (the number of vertices) is straightforward. Printing a graph should print both the vertices and edges arrays in a neat way.

In your AdjMatGraph class you should include a main() that shows correctness and should also test every method you have included.

Problem 3: Short Questions

Below are 4 questions that you are asked to respond to in a paragraph each. To get full credit, it is required that you express yourself clearly, concisely, and to the point. 

a. [5 pts]

How many leaves will be contained in a full binary tree of height 5? How about a complete binary tree of height 5? Explain.

b. [5 pts]

Explain how a binary tree can be implemented using an array. 

c. [5 pts]

What is the root of a decision tree? 

d. [5 pts]

Complete the running times for the following operations of the data structures shown:

Assume that each data structure contains n elements. Depending on the data structure, the operations are known by different names. For example, "InsertElement" is called as "push" in a Stack, enqueue in a Queue, addNode in a Tree and addVertex in a Graph. Similarly for "FindElement" and "DeleteElement"