Quiz 2 Solutions

Introduction to Algorithms November 12, 2008

Massachusetts Institute of Technology 6.006 Fall 2008

Professors Ronald L. Rivest and Sivan Toledo Quiz 2 Solutions

Quiz 2 Solutions

Problem 1. BFS/DFS [10 points] (2 parts)

Give the visited node order for each type of graph search, starting with s, given the following ad-

jacency lists and accompanying ﬁgure:

adj(s) = [a, c, d],

adj(a) = [ ],

adj(c) = [e, b],

adj(b) = [d],

adj(d) = [c],

adj(e) = [s].

s a

ecb

(a) Breadth First Search

Solution: s a c d e b

(b) Depth First Search

Solution: s a c e b d

6.006 Quiz 2 Solutions Name 2

Problem 2. Miscellaneous True/False [30 points] (10 parts)

For each of the following questions, circle either T (True) or F (False). Explain your choice. (No

credit if no explanation given.)

(a) T F While running DFS on a directed graph, if from vertex u we visit a ﬁnished vertex

v, then the edge (u, v) is a cross-edge.

Explain:

Solution: False. The edge could be either a cross-edge or a forward edge.

Note: The edge cannot be a back edge—a back edge goes to a vertex that has

started, but not ﬁnished (a “gray vertex”, in CLRS terms).

(b) T F Changing the RELAX function to update if d[v] ≥ d[u] + w(u, v) (instead of

strictly greater than) may produce different shortest paths, but will not affect the

correctness of the Bellman-Ford outputs d and π.

Explain:

Solution: False. The parent pointers may not lead back to the source node if a

zero-length cycle exists.

In the example below, relaxing the (s, a) edge will set d[a] = 1 and π[a] = 1.

Then, relaxing the (a, a) edge will set d[a] = 1 and π[a] = a. Following the π

pointers from t will no longer give a path to s, so the algorithm is incorrect.

tas

1 1

6.006 Quiz 2 Solutions Name 3

already sorted.

Explain:

Solution: True. All input orderings give the worst-case running time; the run-

ning time doesn’t depend on the order of the inputs in any signiﬁcant way.

(d) T F Let P be a shortest path from some vertex s to some other vertex t in a directed

graph. If the weight of each edge in the graph is increased by one, P will still be

a shortest path from s to t.

Explain:

Solution: False. See the counterexample below.

(e) T F If a weighted directed graph G is known to have no shortest paths longer than k

edges, then it sufﬁces to run Bellman-Ford for only k passes in order to solve the

single-source shortest paths problem on G.

Solution: True. The ith iteration ﬁnds shortest paths in G of i or fewer edges,

by the path relaxation property (see p. 587 in CLRS).

6.006 Quiz 2 Solutions Name 4

(f) T F If a topological sort exists for the vertices in a directed graph, then a DFS on the

graph will produce no back edges.

Explain:

Solution: True. Both parts of the statement hold if and only if the graph is

acyclic.

(g) T F Dynamic programming is more closely related to BFS than it is to DFS.

Explain:

Solution: False. DFS is more closely related. The top-down approach to dy-

namic programming is effectively performing DFS on the subproblem depen-

dence graph. The bottom-up approach means solving subproblems in the order

of a reverse topological sort, which is also related to DFS.

(h) T F A depth-ﬁrst search of a directed graph always produces the same number of

tree edges (i.e. independent of the order in which the vertices are provided and

independent of the order of the adjacency lists).

Explain:

Solution: False. The DFS forest may contain different numbers of trees (and

tree edges) depending on the starting vertex and upon the order in which vertices

are searched.

Consider the example below. If the DFS starts at a, then it will visit b next, and

(a, b) will become a tree edge. But if the DFS visits b ﬁrst, then a and b become

separate trees in the DFS forest, and (a, b) becomes a cross edge.

6.006 Quiz 2 Solutions Name 5

(i) T F Suppose we do a DFS on a directed graph G. If we remove all of the back edges

found, the resulting graph is now acyclic.

Explain:

Solution: True. If DFS ﬁnds no back edges, then the graph is acyclic. Remov-

ing any back edges found doesn’t change the traversal order of DFS, so running

DFS again on the modiﬁed graph would produce no back edges.

(j) T F Both DFS and BFS require Ω(V ) storage for their operation. (That is, for work-

ing storage, above and beyond the storage needed to represent the input.)

Explain:

Solution: True. Each needs to keep track of the vertices that have already been

visited.

6.006 Quiz 2 Solutions Name 6

Problem 3. Miscellaneous Short Answer [20 points] (3 parts)

(a) Suppose you want to get from s to t on weighted graph G with nonnegative edge

weights, but you would like to stop by u if it isn’t too inconvenient. (Here too incon-

venient means that it increases the length of your travel by more than 10%.)

Describe an efﬁcient algorithm that would determine an optimal s to t path given your

preference for stopping at u along the way if not too inconvenient. It should either

return the shortest path from s to t, or the shortest path from s to t containing u.

Solution: Run Dijkstra’s algorithm twice, once from s and once from u. The short-

est path from s to t containing u is composed of the shortest path from s to u and the

shortest path from u to t. Compare the length of this path with the length of the path

from s to t, and choose the one to return based on their lengths.

(b) Explain how the “rod-cutting” problem described in class can still be solved by dy-

namic programming, even if cuts now cost $1 each. (In class, we assumed cuts were

free.) Here is the pseudocode for the original solution, where the cuts were free:

r = [0]

(n + 1)

for k in range(1, n + 1):

ans = p[k]

for i range(1, k):

ans = max(ans, p[i] + r[k - i])

r[k] = ans

(It sufﬁces to explain how to express r

, the maximum revenue achievable for a rod of

size n, in terms of r

, r

, ..., r

n−1

and the prices p

that the market will pay for a piece

of length i, for i = 1, 2, ...n.)

Solution: Modify the ﬁfth line to account for the loss in revenue due to the cost of

the cut:

ans = max(ans, p[i] + r[k - i] - 1)

6.006 Quiz 2 Solutions Name 7

requires O(V ) time to initialize, worst-case f(V, E) time for each EXTRACT-MIN

operation and worst-case g(V, E) time for each DECREASE-KEY operation. How

much (worst-case) time does it take to run Dijkstra’s algorithm on an input graph

G = (V, E)?.

Solution: O(V · f (V, E) + E · g(V, E))

6.006 Quiz 2 Solutions Name 8

Problem 4. A Series of Tubes [20 points] (2 parts)

Consider a network of computers represented by a directed graph G. Each vertex v ∈ V represents

a computer, and each edge (u, v) ∈ E represents a network link from u to v.

(a) Let each edge (u, v) in G have a weight w(u, v) ∈ (0, 1], representing the probability

that a packet going from u to v is successfully delivered. Give an efﬁcient algorithm

to ﬁnd the path along which a packet has the highest probability of reaching its desti-

nation (i.e., the path for which the product of the edge weights is maximized).

Hint: Transform the weights and use a shortest path algorithm.

Solution: Construct a new graph G

, letting w

(u, v) = − log w(u, v). Shortest

paths in G

correspond to highest probability paths in G, because

, v

i+1

) =

−

log w(v

, v

i+1

) = − log (

w(v

, v

i+1

)), which is minimized when the product

term is maximized.

The new weights are non-negative, so run Dijkstra’s algorithm on G

to ﬁnd the highest

probability paths.

(b) Now, instead of weighted edges, consider weighted vertices. In other words, network

links never drop packets, but nodes might. Edges are not weighted, but each vertex

v has a weight w(v) ∈ (0, 1], representing the probability that an incoming packet is

not dropped by that node. Give an efﬁcient algorithm to ﬁnd the path along which a

packet has the highest probability of reaching its destination (i.e., the path for which

the product of the vertex weights is maximized).

Hint: Transform the graph and use the algorithm from part (a).

Solution: Construct a new edge-weighted graph G

by assigning each edge the

weight w

(u, v) = w(v), then run the algorithm from part (a).

Note 1: It’s reasonable to assume here that the weight of the source vertex, s, is 1,

because the originating computer won’t drop the packet. Even without this assump-

tion, the problem isn’t much harder—adjust the weight of each edge originating at s

by multiplying it by w(s).

Note 2: Using the weight function w

(u, v) = w(u) · w(v) is problematic because the

weight of each vertex, except for the source and the target, is included in two edges of

the path, so those vertices are double-counted.

6.006 Quiz 2 Solutions Name 9

Problem 5. Fast Flyer [20 points] (3 parts)

You are given a list of all scheduled daily ﬂights in the US, giving departure airports, departure

times, destination airports, and arrival times. We want an algorithm to compute travel times be-

tween airports, including waiting times between connections. Assume that if one ﬂight arrives at

time t and another departs at time t

≥ t, travelers can make the connection. Further assume that at

a given airport, no two events (arrivals or departures) occur at the same time, and that there are at

most 100 events at any airport during a given day. All times are given in GMT; don’t worry about

time zones.

Construct a weighted graph so that given a departure airport, a departure time T , and a destination

airport, we can efﬁciently determine the earliest time T

that a traveler can be guaranteed (ac-

cording to the schedules!) of arriving at her destination on that day (ignore overnight ﬂights and

overnight airport stays).

(a) What do vertices represent? What do edges in your graph represent, and what is the

weight of an edge?

Solution: There are many ways to represent the problem with a weighted graph.

Here is one good solution. We create a vertex for every ﬂight departure and every

ﬂight arrival. That is, each vertex corresponds to a particular time (arrival or departure

of a ﬂight) at a particular airport. We also create one vertex for the departure time at

the departure airport.

We create an edge for every ﬂight. The weight of these edges is the ﬂight time. We

also create an edge from every event (departure or arrival) at an airport to the next

event at the same airport. The weight of these is the time between the events.

(b) Give an upper bound on the number of edges and vertices in your graph if there are n

airports in the US and m daily ﬂights. Justify your bound.

Solution: For the construction given above, the number of vertices is clearly 2m+1.

The number of edges is a bit harder to bound. One bound is 1 + 99n + m, since there

are at most 100 events at an airport (so 99 intervals between them, plus one more from

the start time) and m ﬂight edges. There are other bounds that we can derive for the

number of edges here. This part was graded based on the construction in the ﬁrst part.

6.006 Quiz 2 Solutions Name 10

running time in terms of the number of vertices, V , and the number of edges, E?

Solution: For the construction above, we need to sort the events at each airport to

create the edges. This takes O(V lg V ), but this is likely to be a loose bound since we

don’t solve one big sorting problem but many small ones. If we use Radix sort, the

cost drops to O(V ).

Once the graph is constructed, we can ﬁnd the shortest travel times using BFS or DFS;

since our vertices are associated with a time and an airport, all the reachable vertices

from the starting vertex represent times in which a traveler can be at an airport. By

ﬁnding the earliest reachable vertex per airport we ﬁnd the solution.

We can also use Dijkstra (and we can use Fibonacci heaps), or a shortest-paths algo-

rithm for DAGs (this construction is a graph, and is acyclic because travelers always

move forward in time).

6.006 Quiz 2 Solutions Name 11

Problem 6. Articulation Points [20 points] (3 parts)

We deﬁne an articulation point as a vertex that when removed causes a connected graph to become

disconnected. For this problem, we will try to ﬁnd the articulation points in an undirected graph

(a) How can we efﬁciently check whether or not a graph is disconnected? (Hint: think of

a recent problem set question)

Solution: Run BFS or DFS on a node in G (since G is undirected, any node will

do). If the size of the set of visited nodes does not equal |V |, then the graph is discon-

nected.

(b) Describe an algorithm that uses a brute force approach to ﬁnd all the articulation points

in G in O(V (V + E)) time.

Solution: For each vertex v in G, remove v and all the edges connected to v. Run

the algorithm from part a. If the graph G is disconnected, then v is an articulation

point. Add v and all its edges back into G and repeat.

6.006 Quiz 2 Solutions Name 12

An observer comments that the polynomial time algorithm is rather slow and suggests

to use a linear time DFS approach instead. Let’s explore this idea some more.

tree produced from an undirected graph, recalling that cross edges can’t happen in the

DFS of an undirected graph. Argue that a non-root, non-leaf vertex u is an articulation

point if and only if there exists a subtree rooted at a child of u that has no back edges

to a proper ancestor of u.

Solution: The ﬁrst thing to note is that the claim is an if and only if statement so we

need to prove it in both directions.

Claim 1: If u is an articulation point, then there exist a subtree rooted at a child of u

that has no back edges to a proper ancestor of u.

We can prove this by contradiction. Assume all the subtrees have back edges to a

proper ancestor of u. If we remove u, every subtree of u can still reach a proper

ancestor of u through the back edge. Since the graph is still connected, u cannot be

an articulation point, so our initial assumption is violated. Therefore, there must be a

subtree with no back edge to a proper ancestor of u.

Claim 2: If there exist a subtree rooted at a child of u that has no back edges to a

proper ancestor of u, then u is an articulation point.

The important fact to realize is that a DFS on an undirected graph only produces tree

edges and back edges. Because there are no cross edges, then there is no path from

one subtree rooted at a child of u to another subtree rooted at a child of u, nor a path

to a vertex that is neither an ancestor or descendent of u. Since the assumption says

there are no back edges either, then there must only be tree edges. If we remove u,

then the subtree that has no back edges will be disconnected since we are effectively

removing the connecting tree edge. Hence, u is an articulation point.

Since Claim 1 and Claim 2 are true, then the original claim is true.

(FYI: The above idea can be extended to yield an O(V + E) algorithm to ﬁnd all

articulation points, but we don’t have time for all of that on this quiz!)