Problem Set 10

due by 11:59 p.m. Eastern time on Thursday, December 10, 2020

There is no late submission for this assignment.
No submissions will be accepted after Thursday, December 10th.

Preliminaries

In your work on this assignment, make sure to abide by the collaboration policies of the course.

If you have questions while working on this assignment, please come to office hours, post them on Piazza, or email cs112-staff@cs.bu.edu.

Make sure to submit your work following the instructions found at the end of the assignment.

Part I

50 points total

Creating the necessary file

Problems in Part I will be completed in a single PDF file. To create it, you should do the following:

1. Open the template that we have created for these problems in Google Docs: ps10_partI

2. Select File->Make a copy..., and save the copy to your Google Drive using the name ps10_partI.

3. Add your work to this file.

4. Once you have completed all of these problems, choose File->Download->PDF document, and save the PDF file on your machine. The resulting PDF file (ps10_partI.pdf) is the one that you will submit. See the submission guidelines at the end of Part I.

Problem 1: Hash tables

15 points total; individual-only

The following sequence of keys is to be inserted into an initially empty hash table of size 8 that employs open addressing:

cat, goat, dog, bird, bison, ant, flea, bat, duck

The hash function assigns to each key the number of characters in the key. For example, h("cat") is 3, because "cat" has 3 characters.

1. Assume that linear probing is used to insert the keys. Determine which key causes overflow, and show the table at that point by adding the keys at the appropriate positions in the table that we have provided in section 1-1 of ps10_partI.

2. Now assume that quadratic probing is used. Determine which key causes overflow, and show the table at that point.

3. Next, assume that double hashing is used, with the value of the second hash function based on the first character in the key: a = 1, b = 2, c = 3, d = 4, e = 5, f = 6, g = 7, etc. Determine which key causes the table to overflow, and show the table at the point at which it does so.

Now consider the fourth table provided for problem 1 in ps10_partI. You should assume that this table is using double hashing with the hash functions described above. The table includes a number of existing keys, and positions 0 and 6 are shaded to indicate that they are removed positions – i.e., ones that used to hold an item that has since been removed.

4. If we now insert an item whose key is "cat", what is the probe sequence – i.e., the sequence of positions examined during probing – for that insertion?

5. Show what the table will look like after "cat" is inserted.

Problem 2: Comparing data structures

6 points total; individual-only

A supermarket chain wants you to implement an in-memory database that can be used to access facts about the products they sell. Although a snapshot of this database will be periodically copied to disk, its contents fit in memory, and your component of the application will operate only on data stored in memory.

Here are the requirements specified by the managers of the supermarket chain:

• They want to be able to retrieve product records by specifying the name of the product.

• They want to be able to specify the first n characters of a product name and to retrieve all records that begin with those characters.

• They want the time required to retrieve a record to be as efficient as possible – on the order of 20 operations per retrieval, given a database of approximately one million records.

• They want to be able to increase the size of the database – adding large sets of new records – without taking the system offline.

Given this list of requirements, which data structure would be the better choice for this application, a balanced search tree (e.g., a 2-3 tree) or a hash table – or would these two data structures work equally well?

Explain your decision, specifying as many reasons as possible for the choice that you make.

Problem 3: Complete trees and arrays

9 pts. total; individual-only

We will cover complete trees in lecture during the week of April 21.

Assume that you have a complete tree with 200 nodes, and that you represent it in array form.

1. Node A of the tree is in position 50 of the array. What are the indices of A’s left child, right child, and parent? Explain how you got your answers.

2. What is the height of the tree? Explain your answer briefly.

3. The bottom level of the tree contains some number of leaf nodes. Is the rightmost leaf node in the bottom level the left child of its parent or the right child of its parent? Explain your answer briefly.

Problem 4: Heaps

10 pts. total; individual-only

Consider the following heap of integers:

1. Show the heap as it will appear:

   • after one removal (i.e., after one call to the remove() method discussed in lecture)

   • after a second removal.

   You should include two separate diagrams, one for how the heap will look after each removal. To do so, you should:

   • Edit the diagram provided in section 4-1 of ps10_partI by clicking on it and then clicking the Edit link that appears below the diagram.

   • Make the necessary changes to the tree to show the results of the first removal.

   • Click the Save & Close button.

   • Make a copy of your edited diagram within the Google Doc and edit it to show the results of the second removal.

2. Suppose we have the original heap and that 40 is inserted followed by 25. Show the final heap by editing the diagram that we have provided in section 4-2 of ps10_partI.

Problem 5: Heaps and heapsort

10 pts. total; individual-only

Consider the following complete tree of integers:

1. Turn this tree into a max-at-top heap using the procedure outlined in lecture and lab, and show the heap that is produced.

   • Edit the diagram provided in section 5-1 of ps10_partI by clicking on it and then clicking the Edit link that appears below the diagram.

   • Make the necessary changes to the tree to show the final heap.

2. What is the array representation of the max-at-top heap that you obtained in part 1?

3. Heapsort begins by turning the array to be sorted into a heap. Assume that your answer to part 2 is the result of this process of turning the original array into a heap.

   What will the array look like after one element is put into its final position by heapsort – i.e., at the end of the first iteration of the loop in heapSort()?

   What will the array look like after the second element is put into its final position?

Submitting your work for Part I

Note: There are separate instructions at the end of Part II that you should use when submitting your work for that part of the assignment.

Submit your ps10_partI.pdf file using these steps:

1. If you still need to create a PDF file, open your ps10_partI file on Google Drive, choose File->Download->PDF document, and save the PDF file on your machine.

2. Login to Gradescope by clicking the link in the left-hand navigation bar, and click on the box for CS 112.

3. Click on the name of the assignment (PS 8: Part I) in the list of assignments on Gradescope. You should see a pop-up window labeled Submit Assignment. (If you don’t see it, click the Submit or Resubmit button at the bottom of the page.)

4. Choose the Submit PDF option, and then click the Select PDF button and find the PDF file that you created. Then click the Upload PDF button.

5. You should see a question outline along with thumbnails of the pages from your uploaded PDF. For each question in the outline:

   • Click the title of the question.
   • Click the page(s) on which your work for that question can be found.

   As you do so, click on the magnifying glass icon for each page and doublecheck that the pages that you see contain the work that you want us to grade.

6. Once you have assigned pages to all of the questions in the question outline, click the Submit button in the lower-right corner of the window. You should see a box saying that your submission was successful.

Part II

30 points total

Preparing for Part II

Begin by downloading the following zip file: ps10.zip

Unzip this archive, and you should find a folder named ps, and within it the files you will need for Part II. Make sure that you keep all of the files in the same folder.

Problem 6: Binary tree iterator

30 points; pair-optional

This is the only problem of the assignment that you may complete with a partner. See the rules for working with a partner on pair-optional problems for details about how this type of collaboration must be structured.

The traversal methods that are part of the LinkedTree class are limited in two significant ways: (1) they always traverse the entire tree; and (2) the only functionality that they support is printing the keys in the nodes. Ideally, we would like to allow the users of the class to traverse only a portion of the tree, and to perform different types of functionality during the traversal. For example, users might want to compute the sum of all of the keys in the tree. In this problem, you will add support for more flexible tree traversals by implementing an iterator for our LinkedTree class.

You should use an inner class to implement the iterator, and it should implement the following interface:

public interface LinkedTreeIterator {
    // Are there other nodes to see in this traversal?
    boolean hasNext();

    // Return the value of the key in the next node in the
    // traversal, and advance the position of the iterator.
    int next();
}

There are a number of types of binary-tree iterators that we could implement. We have given you the implementation of a preorder iterator (the inner class PreorderIterator), and you will implement a postorder iterator for this problem.

Your postorder iterator class should implement the hasNext() and next() methods so that, given a reference named tree to an arbitrary LinkedTree object, the following code will perform a complete postorder traversal of the corresponding tree:

LinkedTreeIterator iter = tree.postorderIterator();
while (iter.hasNext()) {
    int key = iter.next();

    // do something with key
}

Here are the tasks that you should perform:

0. Review the code that we’ve given you in the PreorderIterator class and the preorderIterator() method, and understand how that iterator works. It’s worth noting that you can’t actually use a PreorderIterator object yet, because it will only work after you have completed the next task.

1. In order for an iterator to work, it’s necessary for each node to maintain a reference to its parent in the tree. These parent references will allow the iterator to work its way back up the tree.

   In the copy of LinkedTree.java that we’ve given you for this assignment, the inner Node class includes a field called parent, but the LinkedTree code does not actually maintain this field as the tree is updated over time. Rather, this parent field is assigned a value of null by the Node constructor, and its value remains null forever.

   Before implementing the iterator, you should make whatever changes are needed to the existing LinkedTree methods so that they correctly maintain the parent fields in the Node objects.

   • For example, when a Node object is first inserted in the tree, you should set its parent field to point to the appropriate parent node.

   • Think about when the parent of a node can change, and update the necessary method(s) to modify the parent field in a Node object whenever its parent changes.

   • The root of the entire tree should have a parent value of null.

2. Next, add a skeleton for your iterator class, which you should name PostorderIterator (note that only the P and I are capitalized). It should be a private inner class of the LinkedTree class, and it should implement the LinkedTreeIterator interface. Include whatever private fields will be needed to keep track of the location of the iterator. Use our PreorderIterator class as a model.

3. Implement the constructor for your iterator class. Make sure that it performs whatever initialization is necessary to prepare for the initial calls to hasNext() and next().

   In the PreorderIterator constructor that we’ve given you, this initialization is easy, because the first node that a preorder iterator visits is the root of the tree as a whole. For a postorder iterator, however, the first node visited is not necessarily the root of the tree as a whole, and thus you will need to perform whatever steps are needed to find the first node that the postorder iterator should visit, and initialize the iterator’s field(s) accordingly.

4. Implement the hasNext() method in your iterator class. Remember that it should execute in O(1) time.

5. Implement the next() method in your iterator class. Make sure that it includes support for situations in which it is necessary to follow one or more parent links back up the tree, as well as situations in which there are no additional nodes to visit. If the user calls the next() method when there are no remaining nodes to visit, the method should throw a NoSuchElementException.

6. Add a postorderIterator() method to the outer LinkedTree class. It should take no parameters, and it should have a return type of LinkedTreeIterator. It should create and return an instance of your new class.

7. Test everything! At a minimum, you must do the following: In the main() method, add a unit test that uses the while-loop template shown near the start of this problem to perform a full postorder traversal of a sample tree.

Bonus Only

Problem 7: Determining if an array is a heap

20 points; individual-only

Make sure to begin by following the instructions given above under Preparing for Part II.

In Problem7.java, we have given you the following pair of methods, one of which still needs to be implemented:

public static <T extends Comparable<T>> boolean isHeap(T[] arr) {
    if (arr == null || arr.length == 0) {
        return false;
    }

    return isHeapTree(arr, 0);
}

private static <T extends Comparable<T>> boolean isHeapTree(T[] arr, int i) {
    // Implement this method.

}

Together, these methods are meant to determine if an array of objects corresponds to a heap. The methods are generic, and they should work with an array of any type T that implement Comparable<T>.

Implement the second method so that it uses recursion to process the complete tree/subtree whose root is at position i in the array arr. The method should return true if that tree/subtree is a heap, and false if it is not a heap. A leaf node is the root of a heap with only one node.

Note that the first method – which is a public wrapper method for the method that you will write – makes the initial call to your method with a value of 0 for i, which means that it will determine if the complete tree represented by the full array is a heap. You should not modify this wrapper method.

In implementing your recursive method, you may find it helpful to review:

• the arithmetic rules for navigating through a complete tree that is stored in an array

• how the compareTo() method can be used to compare two objects.

We have included a main() method with one unit test. You should add at least two others.

Submitting your work for Part II

Note: There are separate instructions at the end of Part I that you should use when submitting your work for that part of the assignment.

You should submit only the following file:

• LinkedTree.java

If you did the bonus assignment, also submit:

• Problem7.java

Make sure that you do not try to submit a .class file or a file with a ~ character at the end of its name.

Here are the steps:

1. Login to Gradescope as needed by clicking the link in the left-hand navigation bar, and then click on the box for CS 112.

2. Click on the name of the assignment (PS 8: Part II) in the list of assignments. You should see a pop-up window with a box labeled DRAG & DROP. (If you don’t see it, click the Submit or Resubmit button at the bottom of the page.)

3. Add your files to the box labeled DRAG & DROP. You can either drag and drop the files from their folder into the box, or you can click on the box itself and browse for the files.

4. Click the Upload button.

5. You should see a box saying that your submission was successful. Click the (x) button to close that box.

6. The Autograder will perform some tests on your files. Once it is done, check the results to ensure that the tests were passed. If one or more of the tests did not pass, the name of that test will be in red, and there should be a message describing the failure. Based on those messages, make any necessary changes. Feel free to ask a staff member for help.

   Note: You will not see a complete Autograder score when you submit. That is because additional tests for at least some of the problems will be run later, after the final deadline for the submission has passed. For such problems, it is important to realize that passing all of the initial tests does not necessarily mean that you will ultimately get full credit on the problem. You should always run your own tests to convince yourself that the logic of your solutions is correct.

7. If needed, use the Resubmit button at the bottom of the page to resubmit your work. Important: Every time that you make a submission, you should submit all of the files for that Gradescope assignment, even if some of them have not changed since your last submission.

8. Near the top of the page, click on the box labeled Code. Then click on the name of each file to view its contents. Check to make sure that the files contain the code that you want us to grade.