Problem Set 5

Due before the start of lecture on May 5, 2026. No submissions will be accepted after 11:59 p.m. Eastern time on Sunday, May 10, so that we can post solutions before the final exam.

Preliminaries

Homework is due prior to the start of lecture. If it is submitted more than 10 minutes after the start of lecture, it will be considered a full day late. There will be a 10% deduction for late submissions that are made by 11:59 p.m. on the Sunday after the deadline. For this assignment, no submissions will be accepted after 11:59 p.m. Eastern time on Sunday, May 10, so that we can post solutions before the final exam.

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).

Creating the necessary folder

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

Creating the necessary file

The problems from this assignment will all 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 ps5.

4. Add your work for the problems to this file.

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

1. (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. (2 points) What is the array representation of the max-at-top heap that you obtain in part 1?

3. (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; 4 points each part

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

to, the, their, my, bring, do, an, you, 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.

1. 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.

2. 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.

3. Next, 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) = 3 if k is a verb ("bring", "do", "go")
   • h2(k) = 4 if k is an article ("the", "an")
   • h2(k) = 5 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 ps5 (the one under section 2-5). Assume that this hash table is using double hashing with the hash functions described above. The table includes a number of existing keys, and positions 1, 4 and 5 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 "try" (which is a verb), 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 "try" is inserted.

Problem 3: Determining if two vertices are adjacent

15 points total; 5 points each part

1. Given the graph representation used in the Graph class from lecture, write a simple Java method that takes two Vertex objects as parameters and determines if the vertices are adjacent. The method should return true if the vertices are adjacent, and false if they are not adjacent. Keep in mind that the edges in the graph may be directed, which means that you may need to check both vertices’ adjacency lists.

2. If a graph with V vertices were represented using the Graph class from lecture, what would be the worst-case time efficiency of the algorithm from part a? Use big-O notation, and explain your answer briefly.

3. We can make the process of determining if two vertices are adjacent more efficient if we modify the representation of the graph. Describe a modification that will achieve this goal, and explain how your algorithm would be changed to take advantage of the changed representation. State the worst-case time efficiency of the more efficient algorithm using big-O notation, and explain your answer briefly.

Problems 4-6 refer to the following graph:

Problem 4: Graph traversals

12 points; 3 points each part

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.

1. List the order in which you will visit the cities if you start from L.A. 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. What is the path from L.A. to New York in the breadth-first spanning tree? Give the path in the form

   A -> B -> C ->  etc.
   

   where A, B, and C are vertices.

3. List the order in which you will visit the cities if you start from L.A. 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.

4. What is the path from L.A. to New York in the depth-first spanning tree? Give the path in the form

   A -> B -> C ->  etc.
   

   where A, B, and C are vertices.

Problem 5: Minimal spanning tree

10 points total

1. (8 points) A cheaper version of the same pass requires that you confine yourself to flights that are part of a minimal spanning tree for the graph. List the order in which flights/edges will be added to this tree if you build it using Prim’s algorithm, starting from L.A. Use the form (city1, city2) when specifying an edge.

2. (2 points) What is the path from St. Louis to Boston in the minimal spanning tree? Give the path in the form

   A -> B -> C ->  etc.
   

   where A, B, and C are vertices.

Problem 6: Dijkstra’s shortest-path algorithm

13 points total

Suppose you set out to use Dijkstra’s algorithm to determine the shortest distance from L.A. to every other city in the graph.

1. (8 points) Fill in the table provided in section 6-1 of ps5 to show how the distance estimates are refined over the course of the algorithm. Once a city is finalized, you should no longer include its distance in subsequent columns.

2. (5 points) What path(s) does the algorithm discover from L.A. to Boston? Include both the final shortest path and any temporary estimates for the shortest path that are later replaced. Give the paths in the form

   A -> B -> C ->  etc.
   

   where A, B, and C are vertices.

Problem 7: Directed graphs and topological sort

10 points total; 5 points each part

1. Is the graph below a directed acyclic graph (a DAG)?

   

   If it isn’t a DAG, specify all cycles that are present in the graph. If it is a DAG, use topological sort to find one of the possible topological orderings of the vertices in the graph.

2. Repeat the process outlined above on the graph below.

Problem 8: Alternative MST algorithm

10 points

Prim’s algorithm is just one possible algorithm for finding a minimum spanning tree. Another such algorithm was developed by Kruskal:

kruskal_MST(Graph g) {
    put each of g’s vertices in its own set

    while (there is more than one set) {
        let e = the minimum-cost edge that hasn’t been considered

        if (e connects vertices that are in different sets) {
            add e to the MST
            merge the sets containing the vertices connected by e
        }
    }
}

Note that this algorithm considers the edges in order of increasing cost. In addition, at an intermediate stage of the algorithm, there may be multiple trees that are not connected to each other, although they will ultimately be joined together to form a single MST.

For example, if we applied Kruskal’s algorithm to the graph above, we would start out with the following sets:

{A}, {B}, {C}, {D}, {E}, {F}

We would consider the edge (C, E) first, because it has the lowest cost (400). Because it connects vertices in different sets, we would add this edge to the tree and merge the sets involved to get:

{A}, {B}, {C, E}, {D}, {F}

We would next consider the edge (D, F), because it has the smallest remaining cost. Because it connects vertices in different sets, we would add this edge to the tree and merge the sets involved to get:

{A}, {B}, {C, E}, {D, F}

We would next consider the edge (D, E), because it has the smallest remaining cost. Because it connects vertices in different sets, we would add this edge to the tree and merge the sets involved to get:

{A}, {B}, {C, D, E, F}

We would next consider the edge (C, D), because it has the smallest remaining cost. Because it connects vertices that are already in the same set, we would not add this edge to the tree.

We would next consider the edge (A, B), because it has the smallest remaining cost. Because it connects vertices in different sets, we would add this edge to the tree and merge the sets involved to get:

{A, B}, {C, D, E, F}

We would next consider the edge (B, C), because it has the smallest remaining cost. Because it connects vertices in different sets, we would add this edge to the tree and merge the sets involved to get:

{A, B, C, D, E, F}

Finally, we would consider the edge (B, D). Because it connects vertices in the same set, we would not add this edge to the tree.

Apply Kruskal’s algorithm to the airline graph from earlier in the problem set, which is reproduced below. List the edges of the MST in the order in which the algorithm would add them, using the format (city1, city2) for an edge.

Submitting Your Work

Submit your ps5.pdf file by taking the following steps:

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

2. Click on the name of the assignment 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.)

3. 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.

4. 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.

5. Once you have assigned pages to all of the problems 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.

Last updated on April 28, 2026.