Assignment 1

 

  1. PART I: Pen-and-paper (PDF) exercises:
    1. Suppose we have n binary heaps, each with approximately n elements in min-heap order. Consider the following code that builds a single heap out of all the elements in all the heaps: 
      
    done = false
    initialize empty bigHeap
    while not done	
        done = true
        for i=1 to n
	    if heap(i).notEmpty()
                x = heap(i).extractMin()
                bigHeap.insert (x)
                done = false
            endif
        endfor
    endwhile
      Analyize the running time with an explanation.
    2. Insert the nine (1-letter) keys "A B C D E F G H I" into an empty multiway tree of degree 2 and show the intermediate steps. Also, work out the insertion steps for a multiway tree of degree 3.
    3. Show the intermediate trees when the seven keys "D A C B E F G" get inserted into a self-adjusting binary tree. Remember that a newly inserted element is moved to the root so that every insertion will cause re-organization. Write down the which rotation case (e.g., Case 1(a), Case 3, etc) you are using with each diagram.
    4. Who devised Mergesort and what is this person's role in the history of computer science?
    Note: Credit will not be given only for answers - show all your work: your reasoning, steps you took to get your answer etc.

  2. PART II: Implement (1) a binary search tree, and (2) a multiway tree as described in Module 3. In particular:
    • Your binary search tree algorithm will need to implement the TreeSearchAlgorithm interface that itself extends the OrderedSearchAlgorithm interface.
    • Your multiway tree algorithm will need to implement the MultiwayTreeSearchAlgorithm interface that itself extends the OrderedSearchAlgorithm interface.
    • For testing deletion, the OrderedSearchAlgorithm interface has a deletion method Note that the other operations are to find the successor and predecessor of a given key.
    • Implement insertion and search for both the binary search tree and multiway tree. Implement deletion for only binary search trees.
    • Implement successor and predecessor for the binary tree, but not for the multiway tree.
    • Important: you will need to understand how to enumerate elements in a data structure before starting your assignment. In particular, we will be using Java's Enumeration interface. If you haven't done this before, please read through an example, perhaps the one in Module 7 of CS-2113. Here is another simple example: DataStructureWithEnumeration.java. Your own enumeration implementation can be very simple -- it does not have to be efficient.
    • Note that you will be building your binary tree code using the TreeNode class. In this class, all you will need to use are the three fields left, right and parent. You may choose to use a constructor if you wish but do not have to since all these variables are public.
    • Make sure that your code properly sets the parent field for each tree node.
    • Similarly, you will build your Multiway tree using the MultiwayNode class. Note that a multiway tree node contains variables for storing data and child-pointers.
    • As usual, you will need to include tests in your main method. In particular, include the example from Part I above.
    • Name your file MultiwayTree.java.
    • Suggested steps for implementation:
      • First, implement search and insertion for the simple binary search tree. This will get you comfortable with "tree" programming. Try to do this in the first week. Also, use the pseudocode towards the end of Module3 (for multiway trees) as a starting point - just comment out the part about moving a newly-inserted (or searched-for) element to the root.
      • Then, implement deletion for binary search trees and test.
      • Write your binary search tree code in a file called BinarySearchTree.
      • Next, get search and insertion working for multiway trees using only one key value.
      • Get search and insertion working for 2-3 key values and go from there.
      • You do not need to implement delete for the multiway tree.
    • Compare the performance of the multiway tree with the binary search tree.
    • For the multiway tree, use m=2 for tests. To get better performance you might want to try higher values of m. Note: m is a value that you set in your code. It is NOT provided by the test environment.
    • You may use this properties file: a1.props
    • Remember to set testDelete=true when testing deletion in the binary search tree. You can also set testLarge=false initially while you are testing and debugging.
    • Similarly, it will help to first set testEnum=false so that you can test insertion and search before tackling enumeration.
    • Note that algtest will call your initialize() method for each new test, which is where you would reset, create a new root etc.
    • Relevant links:
      Algorithm interface
      SearchAlgorithm interface
      OrderedSearchAlgorithm interface
      TreeSearchAlgorithm interface
      TreeNode class
      ComparableKeyValuePair class
      MultiwayTreeSearchAlgorithm interface
      MultiwayNode class
    • To summarize: you will need to provide empty implementations of setPropertyExtractor for both Binary and Multiway trees, and empty implementations of successor, predecessor, delete for the Multiway tree.

Submission: