Homework 3 (assigned January 24, due January 30)

Reading: tba.

Partial written assignment: Solve the following "Do" exercises and assigned problems. Only solutions to the assigned problems should be turned in.
Note: You are responsible for the material covered in both "Do" exercises and assigned problems.
Note: If you work with others, indicate their names at the top of your homework paper. Everyone must submit their own independently written solutions.

"Do" Exercises (not to be handed in):

1. Problem 26-6, pages 763–765.

Assigned Problems (to be handed in):

When describing an algorithm in pseudocode, explain the meaning of your variables in English. Comment the lines of your pseudocode. Your pseudocode should be short, clear, and complete to receive full credit. If your code is long, difficult to read, or incomplete, you will not receive full credit.

1. This problem considers the extent of failure on a network. The network is designed to carry traffic from a designated source vertex s to a designated target vertex t. We will model the network as a directed graph (G = (V, E), in which the capacity of each edge is 1 and in which each vertex lies on at least one path from s to t.
   When the network is running smoothly, the maximum s-t flow in G has value k. However, an attacker has destroyed some of the edges in the network, so that there is now no path from s to t using the remaining (surviving) edges. You believe the attacker has destroyed only k edges, the minimum number needed to separate s from t, i.e., the size of a minimum s-t cut. Assume that you are correct in believing only k edges have been deleted.
   The network administrators are running a monitoring tool on vertex s, which has the following behavior. If you issue the command ping(v), for a given vertex v, it will report whether there is a path from s to v. So ping(t) reports that no path currently exists. (ping(s) always reports a path from s to itself.) You would like to determine the extent of failure in the network using this monitoring tool, through efficient use of the ping command.
   Give an algorithm that issues a sequence of ping commands to various vertices in the network and then reports the full set of vertices that are not currently reachable from s. Note that you could do this by pinging every vertex in the network, but you would like to perform this task by using many fewer pings, since only k edges have been deleted. In issuing this sequence of ping commands, your algorithm is allowed to decide which vertex to ping next based on the outcome of earlier ping operations.
   Give an algorithm that accomplishes this task using only O(k log n) pings.
   • Describe your algorithm in pseudocode. (12 points)
   • Explain how your algorithm works and argue that it is correct. (2 points)
   • Analyze the running time of your algorithm. Explain how it achieves the stated complexity. (1 point)

2. Ad hoc networks are made up of low-powered wireless devices. These networks can be used on battlefields and in other hard-to-reach areas. The idea is that a large collection of these wireless devices can be distributed through the area of interest (e.g., by dropping them from an airplane); the devices would then automatically configure themselves into a functioning wireless network.
   These devices can communicate only within a limited range. We assume all the devices are identical; there is a distance D such that two devices can communicate if and only if the distance between them is at most D.
   Ideally, our ad hoc network is reliable, but because the devices are cheap and low-powered, they frequently fail. If a device v detects that it is likely to fail, it should transmit its information to some other backup device in the network within its communication range. We require each device v to have k potential backup devices, all within distance D of v; we call these k devices the backup set of device v. Also, we do not want any device to be in the backup set of too many other devices; otherwise, a single failure might affect a large fraction of the network.
   Suppose we are given the communication radius D, parameters b and k, and a matrix d[1 .. n, 1 .. n] of distances, where d[i, j] is the distance between device i and device j. Describe an algorithm that either computes a backup set of size k for each of the n devices, such that that no device appears in more than b backup sets, or reports (correctly) that no good collection of backup sets exists. Hint: use a flow network.
   • Describe your algorithm in pseudocode. (12 points)
   • Explain how your algorithm works. (2 points)
   • Analyze the running time of your algorithm. (1 point)