Due: Wednesday, February 5th, in class.

Reading assignment: Kleinberg-Tardos, Sections 4.4, 5.1-5.4.

The problems have been carefully chosen for their pedagogical value, and hence might be similar to those given in past offerings of this course at UW, or similar to other courses at other schools.  Using any pre-existing solutions from these sources, for from the web, constitutes a violation of the academic integrity you are expected to exemplify, and is strictly prohibited.

Most of the problems only require one or two key ideas for their solution. It will help you a lot to spell out these main ideas so that you can get most of the credit for a problem even if you err on the finer details. A final piece of advice: Start working on the problem sets early! Don't wait until the day (or few days) before they're due.

Problems

1. A modified-Dijkstra for single pairs of nodes.

   This problem has been censored by the NSA. [It has also been removed from the homework.]

2. Using a heuristic to guide the search. In order to speed up Dijkstra's algorithm for certain classes of graphs, let's see if we can use some auxiliary information.

   Suppose we want to find a shortest-path from u to v. A heuristic is a value a(w) for every node w. The heuristic is valid if dist(w,v) is at least a(w) for every node w. The heuristic is consistent if a(x) is at most dist(x,y)+a(y) for all edges {x,y} in the graph. Here, dist(.) denotes the distances between nodes in the graph.

   Suppose we have a valid, consistent heuristic a(.). Recall that Dijkstra's algorithm will maintain a set S of nodes whose distances to u are known, and once v is in S, we will have the correct distance from u to v. The node w added to S at every step is the node not in S with smallest label d[w]. Instead, let's add the node with the smallest value d[w]+a(w). Prove that when v is added to S, we can stop and recover a shortest u-v path.

3. Grid graphs. Now let's see how these variants of Dijkstra run on a special family of graphs. Consider a k-by-k grid graph:

   

   So the number of nodes is n=k^2. The edges all have weight one. Consider two nodes u and v in this graph whose distance is r. You don't need to prove the following estimates, but you should at least give a good explanation of your answer (drawing pictures helps!)
   • Give an asymptotic formula for the number of nodes that Dijkstra's algorithm needs to add to S before it can compute a u-v shortest path (this formula should be in terms of r).
   • Now suppose we use the function a(w)=|w-v| (the Euclidean distance). Why is this a valid heuristic? Give an asymptotic formula for the number of nodes that the heuristic-Dijkstra algorithm (from problem 2) uses when from started at u.

4. Kleinberg and Tardos, Chapter 5, Exercise 6
5. Kleinberg and Tardos, Chapter 5, Exercise 7