CSE 421 Assignment #2
Spring 2016

Due: Friday, April 15, 2016.

Reading Assignment: Kleinberg and Tardos Chapter 3, Chapter 4 (we will skip sections 4.8 and 4.9).

Problems: (see the Grading Guidelines before answering)

1. Your company has been consulted by Homeland Security to do risk analysis for networks. In particular, Homeland Security is interested in determining whether there are single points of network failure that could prevent an emergency broadcast message sent from any remaining node being received by all remaining nodes in the network (and, if so, to find what single points of failure exist so that they can be corrected). The issue seems familiar and you recall that your Algorithms instructor suggested that an extension of recursive depth-first search will do the job for problems like this.

   Show how to modify the code for recursive depth-first search of undirected graphs to (i) assign each node v a number, dfsnum(v), indicating the sequence number for when it was first visited by depth-first search, and (ii) compute smallest(v) for each node v, the smallest dfsnum of any node that was encountered in the recursive call DFS(v).

   Show how to determine whether or not v is a single point of network failure in a connected network by comparing dfsnum(v) and smallest(w) for the children w of v in the DFS tree. (You will need a separate simpler condition for the root of the DFS.)

2. Kleinberg and Tardos, Chapter 3, Problem 10, pages 110-111.

3. Kleinberg and Tardos, Chapter 4, Problem 4, page 190.

4. Kleinberg and Tardos, Chapter 4, Problem 13, pages 194-195.

5. Extra credit: Kleinberg and Tardos, Chapter 4, Problem 26, page 202.