Problem Set 5

Due before the start of lecture on December 9, 2025.
No submissions will be accepted after 11:59 p.m. Eastern time on Sunday, December 14, 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, December 14, 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). Although there is one problem that 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 e22 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:

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

16 points total

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

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

   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 2 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 "eel", 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 "eel" is inserted.

Problem 3: List-based priority queue

10 points total

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

2. (4 points) What would be the efficiency of the insert operation in this list-based implementation? Explain your answer briefly.

Problem 4: Testing for a path from one vertex to another

10 points total; 5 points each part

A graph may or may not include a path from one vertex to another vertex. To determine if a path exists, we can add the following two methods to the Graph class from lecture:

public boolean existsPath(String startID, String endID) {
    // Get the Vertex objects for the two vertices.
    Vertex start = this.getVertex(startID);
    Vertex end = this.getVertex(endID);

    if (start == null || end == null) {
        return false;            // at least one vertex ID was not found
    } else {
        this.reinitVertices();   // reset "bookkeeping" fields in vertices
        return existsPathVertices(start, end);
    }
}

private static boolean existsPathVertices(Vertex start, Vertex end) {
    /* Implement this method. */

}

The first method (existsPath()) is a fully implemented non-static method that takes as parameters the string IDs of two vertices. It begins by using the existing getVertex() method to obtain references to the Vertex objects for the specified vertices. If either of the vertex IDs are not found in the Graph (as indicated by a return value of null from getVertex()), the method returns false. If both of the vertices are found, existsPath():

• calls the existing reinitVertices() method to reset the “bookkeeping” fields in all of the Vertex objects in the Graph

• calls the second, not-yet-implemented method shown above (existsPathVertices()) to determine if there is a path between the two Vertex objects

• returns whatever boolean value it gets back from the second method.

Note that existsPathVertices() is a private, static method, and existsPath is a public, non-static method that serves as a “wrapper” for existsPathVertices(). We have seen pairs of methods with similar roles in both our LinkedTree and Graph classes, among other places.

1. Implement the second method so that it uses recursion to determine if there is a path in the graph from vertex start to vertex end. The method should return true if there is such a path and false otherwise. If start and end represent the same vertex, the method should return true. Your code must not use any of the existing methods of the Graph class.

   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 existsPathVertices() method in section 4-1 of ps5.

   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.

   • Queue.java and LLQueue.java, which are needed by the methods for breadth-first traversal

   • highway2.txt - a graph-info file that is based on the highway graph from lecture. However, in this version of the graph, the edges involving Portland are directed edges that go from Portland to Concord and Portland to Portsmouth respectively. As a result, there are no paths to Portland from any other vertex.

   To test your code:

   • Keep all of the files in the ps5 folder, and open that folder in VS Code using the File->Open Folder or File->Open menu option.

   • Replace the starter code for the existsPathVertices() method with your implementation of the method, and fix any syntax errors that are present in your code.

   • When you run the Graph class, enter highway2.txt when it asks you for the name of the graph-info file, and enter the names of the cities that you want to use as the starting point and ending point.

   • If you choose a city other than Portland as your starting point and Portland as your ending point, the program should tell you that there is not a path between the two cities. If you choose any other combination of cities, the program should tell you that there is a path between the two cities.

2. For a graph with V vertices and E edges, what would be the best-case time efficiency of your method from part 1? What would be the worst-case time efficiency? Use big-O notation, and explain your answers briefly.

Problems 5-7 refer to the following graph:

Problem 5: Graph traversals

10 points

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. (3 points) List the order in which you will visit the cities if you start from Atlanta 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. (2 points) What is the path from Atlanta 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. (3 points) List the order in which you will visit the cities if you start from Atlanta 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.

4. (2 points) What is the path from Atlanta 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.

Problem 6: Minimal spanning tree

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 Atlanta. Use the form (city1, city2) when specifying an edge.

Problem 7: Dijkstra’s shortest-path algorithm

10 points total

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

1. (7 points) Fill in the table provided in section 7-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. (3 points) What path(s) does the algorithm discover from Atlanta 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 8: 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 9: Alternative MST algorithm

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

Problem 10: Routing packets

8 points

You have been asked to hard-code a portion of the network routing table for one of the servers that your company owns. The lengths of cable connecting pairs of your company’s servers are given in the matrix below; a value of -1 in a given location indicates that there is no cable connecting that pair of servers.

Assume that you are focusing on server #5. For each of the other servers, determine where server #5 should route packets destined for that server – i.e., to which other server should packets destined for that server be sent next? Your goal is to minimize the total length of cable over which the packet would need to travel, assuming that all of the other servers are also routing packets in this way. Your answer should apply one of the graph algorithms that we covered in lecture. Show the steps that you take in employing the algorithm to solve this problem, and explain briefly why it is an appropriate algorithm for this problem.

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 December 2, 2025.