Problem Set 6

due by 11:59 p.m. on Wednesday, June 25, 2025

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

38 points total

Creating the necessary folder

Create a subfolder called ps6 within your cs112 folder, and put all of the files for this assignment in that folder.

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. Access the template that we have created by clicking on this link and signing into your Google account as needed.

2. When asked, click on the Make a copy button, which will save a copy of the template file to your Google Drive.

3. Select File->Rename, and change the name of the file to ps6_partI.

4. Add your work for the problems from Part I to this file.

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

Problem 1: Checking for keys above a value

10 points total; individual-only

The code below represents one algorithm for determining if there are any keys greater than a given value v in an instance of our LinkedTree class. The anyGreaterInTree() method returns true if there are any keys greater than v in the tree/subtree whose root node is specified by the first parameter of the method, and it returns false if there are no such keys. The anyGreater() method returns true if there are any keys greater than v in the entire tree represented by the LinkedTree object on which the method is invoked and false otherwise.

public boolean anyGreater(int v) {
    // make the first call to the recursive method,
    // passing in the root of the tree as a whole
    return anyGreaterInTree(root, v);
}

private static boolean anyGreaterInTree(Node root, int v) {
    if (root == null) {    
        return false;
    } else {
        boolean anyGreaterInLeft = anyGreaterInTree(root.left, v);
        boolean anyGreaterInRight = anyGreaterInTree(root.right, v);
        return (root.key > v || anyGreaterInLeft || anyGreaterInRight);
    }
}

1. For a binary tree with n nodes, what is the time efficiency of this algorithm as a function of n? Use big-O notation, and explain your answer briefly.

   If the time efficiency depends on the keys in the tree or on the tree’s shape, you should explain why and give three big-O expressions: one for the best case, one for the worst case if the tree is balanced, and one for the worst case if the tree is not balanced. If the time efficiency does not depend on the keys or the shape of the tree, you should explain why and give one big-O expression.

2. If the tree is a binary search tree, we can revise the algorithm to take advantage of the ways in which the keys are arranged in the tree. Write a revised version of anyGreaterInTree that does so. Your new method should avoid visiting nodes unnecessarily. In the same way that the search for a key doesn’t consider every node in the tree, your method should avoid considering subtrees that aren’t needed to determine the correct return value. Like the original version of the method above, your revised method should also be recursive.

3. For a binary search tree with n nodes, what is the time efficiency of your revised algorithm as a function of n?

   Here again, if the time efficiency depends on the keys in the tree or on the tree’s shape, you should explain why and give three big-O expressions: one for the best case, one for the worst case if the tree is balanced, and one for the worst case if the tree is not balanced. If the time efficiency does not depend on the keys or the shape of the tree, you should explain why and give one big-O expression.

Problem 2: Balanced search trees

6 points; individual-only

Illustrate the process of inserting the key sequence

V, C, M, F, K, H, P, Y, S, J

into an initially empty 2-3 tree. Show the tree after each insertion that causes a split of one or more nodes, and the final tree.

We have given you a sample diagram that includes nodes of different sizes. Make copies of the diagram so that you can use separate diagrams for the results of each insertion that causes a split, and for the final tree. Note that you do not need to keep the shape of the tree that we have given you. Rather, you should edit it as needed: deleting or adding nodes and edges, replacing the Xs with keys, adding or removing keys, and making whatever other changes are needed.

Problem 3: Complete trees and arrays

6 points total; individual-only

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

1. Node A of the tree is in position 40 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

8 points 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 ps6_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 we insert the following sequence of values:

   40, 55, 20
   

   Show the final heap by editing the diagram that we have provided in section 4-2 of ps6_partI.

Problem 5: Heaps and heapsort

8 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 show the heap that is produced.

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 ps6_partI.pdf file using these steps:

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

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 6: 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.