Problem Set 5

Due by 11:59 p.m. Eastern time on Monday, August 3, 2026.
No late submissions will be accepted so that we can post solutions before the final exam.

Preliminaries

Homework is due by 11:59 p.m. Eastern time on the stated due date. For this assignment, no late submissions will be accepted so that we can post solutions before the final exam. Plan your time carefully, and don’t wait until the last minute to begin an assignment. Starting early will give you ample time to ask questions and obtain assistance.

In your work on this assignment, make sure to abide by our policies on academic conduct.

If you have questions while working on this assignment, please come to office hours, post them on Ed Discussion, or email cscie22-staff@lists.fas.harvard.edu

The Problems

100 points total

Notes:

There are no extra grad-credit problems for this problem set.
There is only one part to this problem set, and all of your answers should be submitted in a single file (see below). If a problem requires you to write a Java method, you should submit that method in the same file as your other work.

Creating the necessary folder

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

Creating the necessary file

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

Access the template that we have created by clicking on this link and signing into your Google account as needed.
When asked, click on the Make a copy button, which will save a copy of the template file to your Google Drive.
Select File->Rename, and change the name of the file to ps5.
Add your work for the problems to this file.
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 (ps5.pdf) is the one that you will submit. See the submission guidelines at the end of the problem set.

Problem 1 Heaps and heapsort

10 points total

Consider the following complete tree of integers:

(4 points) Turn this tree into a max-at-top heap using the procedure outlined in lecture, and show the heap that is produced. In your copy of the ps5 file (see above), edit the diagram that we have provided 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, and then click the Save & Close button.
(2 points) What is the array representation of the max-at-top heap that you obtain in part 1?
(4 points) 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.
1. What will the heap and the array look like after one element has been put into its final position by heapsort – i.e., at the end of the first iteration of the loop in heapSort()?
2. What will the heap and the array look like after two elements have been put into their final positions?

Problem 2 Hash tables

20 points total

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

the, my, an, by, do, we, if, to, go

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

Assume that linear probing is used to insert the keys. Add the above sequence of keys to the table that we have provided for 2-1 in ps5, stopping at the point at which overflow occurs.
Now assume that quadratic probing is used. Add the above sequence of keys to the table that we have provided for 2-2 in ps5, stopping at the point at which overflow occurs.
Finally, assume that double hashing is used, and that the second hash function h2 is based on the part of speech of the key, as follows:
- h2(k) = 1 if k is a noun or pronoun (e.g., "we", "my")
- h2(k) = 2 if k is a verb (e.g., "do", "go")
- h2(k) = 3 if k is an article (e.g., "the", "an")
- h2(k) = 4 if k is any other part of speech (the rest of the words above).
Add the above sequence of keys to the table that we have provided for 2-3 in ps5, stopping at the point at which overflow occurs.

Now consider the fourth table provided for Problem 2 in the ps5 template (the one under section 2-5). Assume that this hash table was created using double hashing with the hash functions described above. The table includes a number of existing keys, and positions 2 and 7 are shaded to indicate that they are removed positions – i.e., ones that used to hold an item that has since been removed.

If we now insert an item whose key is "see" (which is a verb), what is the probe sequence – i.e., the sequence of positions examined during probing – for that insertion?
Show what the table will look like after "see" is inserted.

Problem 3 List-based priority queue

10 points total

(6 points) A priority queue could be implemented using a list instead of a heap. Describe how you could use a list to implement a priority queue in which the insert operation would have a time complexity of O(1). You may assume either a list implemented using an array or a list implemented using a linked list, but make sure to indicate which implemention you are using.
(4 points) What would be the worst-case time efficiency of the remove operation in this list-based implementation? Explain your answer briefly.

Problem 4 A non-recursive DFS

*10 points total

In the Graph class from lecture, depth-first traversals are accomplished using a recursive method called dfTrav. Write a method called dfTravIter that uses iteration instead of recursion to perform a depth-first traversal. The new method will be somewhat similar to the bfTrav method (the one for breadth-first traversal), but you will need to use a stack instead of a queue to store the yet-to-be visited vertices. In addition, you may need to add a given vertex to the stack more than once if you encounter it multiple times before it is visited. As a result, you should check if a vertex has been visited twice: once before adding it to the stack, and once when it is removed from the stack (to ensure that you don’t visit it twice). You may assume that the new method has only one parameter: a Vertex object for the origin of the traversal. Like the original recursive version of the method, your iterative version should print the id values of the vertices as they are visited, and it should also modify the parent fields in the vertices to form a depth-first spanning tree.

You are welcome to implement your method in the context of the Graph class in order to test it, but ultimately you should include your method under Problem 4 in your ps5 file.

To facilitate your testing, you can download ps5.zip.

Unzip this archive, and you should find a folder named ps5 which includes the following files:

Graph.java - a version of the Graph class from lecture that includes the starter code shown above along with a main method that you can use to test your solution.
highway.txt - a graph-info file for the highway graph from lecture
Queue.java and LLQueue.java, which are needed by the methods for breadth-first traversal
Stack.java and LLStack.java, which you will need in your new implementation of depth-first traversal.

To test your code:

Keep all of the files in the ps5 folder, and open that folder in VSCodium using the File->Open Folder or File->Open menu option.
Add your new dfTravIter method to the Graph class, and modify the existing depthFirstTrav method so that it calls your new method.
Compile Graph.java, and fix any syntax errors that are present in your code.
When you run the Graph class, enter highway.txt when it asks you for the name of the graph-info file, and enter the name of the city that you want to use as the starting point of the traversal.

Important: There are multiple possible depth-first traversals from a given starting point. As a result, your iterative method may visit the cities in a different order than the original recursive method would. The key thing is to ensure that the traversal follows a given path as deeply as possible before backing up.

Problems 5-7 refer to the following graph:

Problem 5 Graph traversals

10 points total

Suppose that you have purchased a pass that allows you to fly anywhere you wish along the routes that are shown in the diagram above.

(3 points) List the order in which you will visit the cities if you start from Denver and do a depth-first traversal. You should assume that the edges of each vertex are stored in order of increasing distance, as we did in the lecture examples.
(2 points) What is the path from Denver to Boston in the depth-first spanning tree? Give the path in the form
```
A -> B -> C ->  etc.
```
where A, B, and C are vertices.
(3 points) List the order in which you will visit the cities if you start from Denver and do a breadth-first traversal. You should assume that the edges of each vertex are stored in order of increasing distance, as we did in the lecture examples.
(2 points) What is the path from Denver to Boston in the breadth-first spanning tree? Give the path in the form
```
A -> B -> C ->  etc.
```
where A, B, and C are vertices.

Problems 6-9 Coming soon!

Submitting Your Work

Coming soon!