22C:44 Final Exam Information

The midterm exam is scheduled for Friday, August 1st, from 8:00 to 9:50 in Room 105, MLH (our usual classroom).

The exam contains 6 problems and is worth 250 points, 25% of your total grade. The problems are on the following topics:

• Problem 1 is on dynamic programming (50 points). How do we express a problem in terms of subproblems? How does this lead to a recurrence that can then be coded as a recursive function? Why is the recursive function often quite inefficient? How can the recursive function be rewritten more efficiently using a table to remember solutions to subproblems?

• Problems 2 and 3 are on minimum spanning trees (40 points each). What is the crucial property of minimum spanning trees that make a variety of greedy algorithms work for this problem? What happens to a minimum spanning tree when an edge weight is changed? Is it easy to compute spanning trees that minimize other quantities, for example, the weight of a heaviest edge in the spanning tree, the product of the weights of the edges, etc.?

• Problem 4 is on Dijkstra's Algorithm (40 points). How does using different data structures to store the vertices in V-S affect the running time of Dijkstra's algorithm? What is the crucial property of shortest paths in graphs with non-negative edge weights, that makes Dijkstra's algorithm correct?

• Problem 5 is on the Dynamic programming algorithm for the all-pairs-shortest-path problem (40 points). How do the slow and fast algorithms for the all-pairs-shortest-path problem work?

• Problem 6 is a somewhat open ended question, that is vaguely related to shortest path problems. The problem is mainly meant to test your ability to think "algorithmically", rather than your knowledge of a specific topic. (40 points)