This study guide includes topics covered since Quiz 6; you should also study all concepts from earlier in the course. The earlier study guides are available here: Quiz 1, Quiz 2, Quiz 3, Quiz 4, Quiz 5, and Quiz 6.

You should be able to define or explain the following terms:

• cycle
• directed acyclic graph (DAG)
• topological sort
• trees
• spanning tree, minimum spanning tree (MST)

You should be familiar with the following C++-related concepts:

• valgrind

Practice problems

1. Consider the following set of courses and their prerequisites:
   • PHYS 005: none
   • PHYS 007: PHYS 005 and MATH 025
   • PHYS 008: PHYS 007 and MATH 033
   • PHYS 014: PHYS 008, MATH 027, and MATH 033
   • PHYS 050: MATH 027 and MATH 033
   • PHYS 111: PHYS 014 and MATH 033
   • PHYS 112: PHYS 014, PHYS 050, and MATH 033
   • PHYS 113: PHYS 111 and MATH 027
   • PHYS 114: PHYS 111 and MATH 033
   • MATH 025: none
   • MATH 027: none
   • MATH 033: MATH 025
   Assuming that a physics student can take only one course at a time, use a graph algorithm from this course to find a sequence of courses that satisfies the prerequisites. Show the graph on which you executed the graph algorithm.
2. In lecture we saw a variant of recursive depth-first search that also determined if the graph contained a cycle. Recursive depth-first search is extremely simple and elegant if the algorithm does not need to track additional information or return any value:

     dfs(G, src):                           // This function initializes the
         isVisited = new dictionary         // dictionary and calls the
         for each vertex v in G:            // recursive helper function.
             isVisited[v] = false
         recursiveDfs(G, src, isVisited)
   
     recursiveDfs(G, src, isVisited):       // This recursive function
         isVisited[src] = true              // searches the graph.
         for each neighbor v of src:
             if !isVisited[v]:
                 recursiveDfs(G, v, isVisited)
     

   1. Execute dfs on the following graph, using s as the source vertex. Draw the stack frame diagram for the program as it executes. (Assume that isVisited refers to a single copy of the dictionary for all frames of the stack.)
      
   2. Modify the pseudocode above to accept a second vertex, dest, as an argument. Return true if there is a path from src->dest in G, and return false otherwise.
   3. Modify the pseudocode again to return the length of some src->dest path (not necessarily the shortest path) if there is a path from src to dest in G. If there is no src->dest path, return -1.
3. Execute Prim's algorithm to find a MST of the following graph using s as the initial vertex. For each step of the algorithm, show which edges and vertices have been selected for the MST up to that step.
4. Find the smallest weighted, undirected graph G such that G has multiple distinct MSTs.

Home Page