Data Structures and Algorithms

Foundations of Algorithms

Homework #5

All members of the collaboration group are expected to participate fully in solving collaborative problems, and peers will assess performance at the end of the assignment. Note, however, that each student is required to write up their solutions individually. Common solution descriptions from a collaboration group will not be accepted. Furthermore, to receive credit for a collaborative problem, each student in the collaboration group must actively and substantively contribute to the collaboration.

Self-Study Problems All of the following problems come from the textbook and have solutions posted on the web at

http://mitpress.mit.edu/algorithms.

You are permitted to use this site to examine solutions for these problems as a means of self-checking your solutions. These problems will not be graded.

Problems: 22.1-7, 22.3-12, 22-1, 23.1-6, 24.1-3, 24.3-6, 26.2-11, 26-4

Problems for Grading 1. [20 points] Suppose we have a connected graph G = (V,E), and a specific vertex u ∈ V . Suppose we

compute a depth-first search tree rooted at u and obtain a tree T that includes all nodes of G. Suppose we then compute a breadth-first search tree rooted at u and obtain the same tree T . Prove that G = T . (In other words, if T is both a depth-first search tree and a breadth-first search tree rooted at u, then G cannot contain any edges that do not belong to T .)

2. Suppose you and your friend Alanis live together with n − 2 other people at a popular “cooperative” apartment. Over the next n nights, each of you is supposed to cook dinner for the co-op exactly once, so some one cooks on each of the nights. To make things interesting, everyone has scheduling conflicts with some of the (e.g., exams, deadlines at work, basketball games, etc.), so deciding who should cook on which night becomes a tricky task. For concreteness, let’s label the people {p1, . . . , pn} and the nights {d1, . . . , dn}. Then for person pi, associate a set of nights Si ⊂ {d1, . . . , dn} when they are not available to cook. A feasible dinner schedule is defined to be an assignment of each person in the co-op to a different night such that each person cooks on exactly one night, there is someone to cook on each night, and if pi cooks on night dj , then dj /∈ Si.

(a) [10 points] Describe a bipartite graph G such that G has a perfect matching if and only if there is a feasible dinner schedule for the co-op.

(b) [10 points] Your friend Alanis takes on the task of trying to construct a feasible dinner schedule. After great effort, she constructs what she claims is a feasible schedule and then heads off to work for the day. Unfortunately, when you look at the schedule she created, you notice a big problem—n − 2 of the people at the co-op are assigned to different nights on which they are available (no problem there), but for the other two people pi and pj , and the other two days dk and dl, you discover she has accidentally assigned both pi and pj to cook on night dk and no one to cook on night dl. You want to fix the schedule but without having to recompute everything from scratch. Show that it is possible, using her “almost correct” schedule, to decide in only O(n2) time whether there exists a feasible dinner schedule for the co-op. If one exists, your algorithm should also provide that schedule.

3. [20 points] Collaborative Problem: You are helping some security analysts monitor a collection of networked computers, tracking the spread of an online virus. There are n computers in the system, labeled C1, C2, . . . , Cn, and as input, you are given a collection of trace data indicating the times at

1

which pairs of computers communicated. Thus the data is a sequence of ordered triples (Ci, Cj , tk). Such a triple indicates that Ci and Cj communicated at time tk. Assume there are m triples total.

Now let us assume that the triples are presented to you in sorted order of time. For purposes of simplicity, we will assume that each pair of computers communicates at most once during the inter- val you are observing. The security analysts you are working with would like to be able to answer questions of the following form: If the virus was inserted into computer Ca at time x, could it pos- sibly have infected computer Cb by time y? The mechanics of infection are simple—if an infected computer Ci communicates with an uninfected computer Cj at time tk, (in other words, if one of the triples (Ci, Cj , tk) or (Cj , Ci, tk) appears in the trace data), then computer Cj becomes infected as well, starting at time tk. Infection can thus spread from one machine to another across a sequence of communications, provided that no step in this sequence involves a move backwards in time. Thus, for example, if Ci is infected by time tk and the trace data contains triples (Ci, Cj , tk) and (Cj , Cq, tr), where tk ≤ tr, then Cq will become infected via Cj . (Note that it is okay for tk to be equal to tr. This would mean that Cj had open connections to both Ci and Cq at the same time, so a virus could move from Ci to Cq.)

For example, suppose n = 4, the trace data consists of the triples

(C1, C2, 4), (C2, C4, 8) (C3, C4, 8) (C1, C4, 12),

and the virus was inserted into computer C1 at time 2. Then C3 would be infected at time 8 by a sequence of three steps—first C2 becomes infected at time 4, then C4 gets the virus from C2 at time 8, and then C3 gets the virus from C4 at time 8. On the other hand, if the trace data were

(C2, C3, 8) (C1, C4, 12) (C1, C2, 14),

and again the virus was inserted into computer C1 at time 2, then C3 would not become infected during the period of observation. Observe, however, that although C2 becomes infected at time 14, C3 only communicates with C2 before C2 becomes infected. There is no sequence of communications moving forward in time by which the virus could get from C1 to C3 in this second example.

Design an algorithm that answers questions of this type: given a collection of trace data, the algorithm should decide whether a virus introduced at computer Ca at time x could have infected computer Cb by time y. Prove that the algorithm runs in time O(m). Also, prove the correctness of your algorithm.

4. Collaborative: We define the Escape Problem as follows. We are given a directed graph G = (V,E) (picture a network of roads.) A certain collection of vertices X ⊂ V are designated as populated vertices, and a certain other collection S ⊂ V are designated as safe vertices. (Assume that X and S are disjoint.) In case of an emergency, we want evacuation routes from the populated vertices to the safe vertices. A set of evacuation routes is defined as a set of paths in G such that (i) each vertex in X is the tail of one path, (ii) the last vertex on each path lies in S, and (iii) the paths do not share any edges. Such a set of paths gives way for the occupants of the populated vertices to “escape” to S without overly congesting any edge in G.

(a) [20 points] Given G, X, and S, show how to decide in polynomial time whether such a set of evacuation routes exists.

(b) [20 points] Suppose we have exactly the same problem as in (a), but we want to enforce an even stronger version of the “no congestion” condition (iii). Thus we change (iii) to say, “the paths do not share any vertices.” With this new condition, show how to decide in polynomial time whether such a set of evacuation routes exists. Also provide an example with the same G, X, and S in which the answer is “yes” to the question in (a) but “no” to the question in (b).

2