Problem Set 10

Due by 10 p.m. on Wednesday, August 5, 2026.
No late submissions will be accepted.

Preliminaries

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

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

The Problems

80 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).
• All of these problems are individual-only. See the policies on academic conduct for a reminder of the relevant guidelines.

Creating the necessary folder

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

Creating the necessary file

The problems 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 ps10.

4. Add your work to this file.

5. Once you have completed all of the problems, choose File->Download->PDF document, and save the PDF file on your machine. The resulting PDF file (ps10.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 ps10 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

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 ps10, 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 ps10, stopping at the point at which overflow occurs.

3. Finally, 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 ps10, stopping at the point at which overflow occurs.

Now consider the fourth table provided for Problem 2 in the ps10 template (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
        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 ps10.

   To facilitate your testing, we are providing 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.

     To use this class, you will also need the following classes from the example code provided on our Lectures page:

     • Queue.java

     • LLQueue.java

   • 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:

   • Put the above files in the same folder, and replace the starter code for the existsPathVertices() method with your implementation of the method. Compile the class, 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

10 points

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

2. (2 points) What is the path from Seattle to Denver in the minimal spanning tree? Give the path in the form

   A -> B -> C ->  etc.
   

   where A, B, and C are vertices.

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 ps10 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

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 ps10.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 August 3, 2026.