In addition to all concepts from Quiz 1, Quiz 2, Quiz 3, Quiz 4, and Quiz 5.

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

• graph, vertex, edge
• directed, undirected graphs
• weighted, unweighted graphs
• adjacent, neighbor, outgoing edges, incoming edges, out-degree, in-degree, degree
• path, reachable, path length, distance
• connected component, strongly-connected component
• adjacency-list representation, adjacency-matrix representation
• breadth-first search, depth-first search of a graph
• Dijkstra's algorithm

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

• vectors and their functions
• printf
• string.c_str()

Practice problems

1. Consider the following graph:
   
   1. Give the adjacency-list representation of the graph.
   2. Give an adjacency-matrix representation of the graph.
2. Let G be an undirected graph with an odd number of vertices. Prove that G contains at least one vertex with an even degree.
3. Play the Dijkstra Adventure Game by running dag in a terminal window. Be sure to play once or twice with the --random option:

     $ dag --random
   

   (I'm sorry for how tedious the game can be -- the graph is big!)
4. In this problem we will analyze Dijkstra's algorithm as given in lecture:

     Dijkstra(G, s):
         for each vertex v in G:
             d[v] = INFINITY
         d[s] = 0
         PQ = make empty heap
         PQ.insert(s with priority 0)
   
         while !PQ.isEmpty():
             current = PQ.removeMin()
             for each neighbor v of current:
                 if d[v] > d[current] + weight(current, v):
                     d[v] = d[current] + weight(current, v)
                     PQ.insertOrUpdatePriority(v with priority d[v])
   

   Assume that Dijkstra's algorithm is executing on a graph with n vertices and m edges, and that PQ.insertOrUpdatePriority has a worst-case running time of O(lg n) for a heap containing n items.
   1. In the worst-case, how many items might be stored in the heap PQ?
   2. In the pseudocode above, d is a dictionary where each key is some vertex v and the value is the currently-shortest-known distance from s to v. How many key-value pairs are stored in this dictionary? What data structure might you use to store this dictionary, and what is the running time of getting or setting the value for a key?
   3. For a single neighbor v of some current vertex, what is the running time of that neighbor's single execution of the inner for-loop:

        if d[v] > d[current] + weight(current, v):
            d[v] = d[current] + weight(current, v)
            PQ.insertOrUpdatePriority(v with priority d[v]) 

   4. How many total times will that inner for-loop execute for the entire graph? In other words, in terms of n and m, how many neighbors (total) are in the graph?
   5. The analysis of part (d) is a bit strange at first because we're considering the total number of neighbors in the entire graph rather than just the neighbors of the current vertex (which varies from graph to graph). This allows us to analyze the total cost of all executions of the for-loop (in sum, for all executions of the while-loop), though, rather than just analyze the cost of exploring the current vertex's neighbors. The total cost of all executions of the inner for-loop is then:

        O( #num_neighbors +  
           #num_neighbors*cost_of_each_for_loop_execution ) 

      (The first term, #num_neighbors, is the total cost of getting the neighbors for every vertex in the graph using an adjacency-list representation. The second term is the product of (c) and (d) above.) Combine your answers to part (c) and (d) to determine the total cost of executing the for-loop.
   6. The only remaining costs in this algorithm are the initialization cost (before the while-loop) and the total cost of executing the line

        current = PQ.removeMin() 

      for all executions of the while-loop. What are these costs, in terms of n and m? What is the total cost of Dijkstra's algorithm?

Home Page