Description
1. Assume that the DFS procedure considers (explores) the vertices in alphabetical order, and assume the
adjacency list is ordered alphabetically.
(a) Run TOPOLOGICAL-SORT on Fig.1. Show:
i. the discovery time and finish time of each node;
ii. the returned linked-list.
(b) Run STRONGLY-CONNECTED-COMPONENTS on Fig.2. Show:
i. The discovery time and finish time for each node after running the first-pass DFS;
ii. The discovery and finish time for each node in the second-pass DFS on the transposed graph;
iii. The DFS forest produced by the second-pass, and the component DAG.
Figure 1: Graph for Q1(a)
Figure 2: Graph for Q1(b)
2. You are given a system of m inequalities involving n variables, x1, . . . , xn. Each inequality is of the form
xj ≥ xi + cij
, for some pair of indices i, j ∈ {1, . . . , n} and some non-negative constant cij ≥ 0.
The system is given as a weighted, directed graph G. The graph G has vertices, numbered 1, . . . , n, and
m edges. Each inequality as above is represented in G as an edge from vertex i to vertex j with weight
cij . Moreover, G is represented in adjacency list format.
(a) First assume that G is acyclic. Your task is to design an algorithm that takes G as input, and
computes an assignment to the variables that satisfies the system of inequalities represented by
G. More precisely, such a satisfying assignment is a list of non-negative numbers (a1, . . . , an) that
satisfy aj ≥ ai + cij for each inequality xj ≥ xi + cij in the system of inequalities. Your algorithm
should run in time O(m + n).
(b) Now consider the previous problem, but G is a general directed graph (not necessarily acyclic).
Design an algorithm that determines if the system of inequalities has a satisfying assignment, and
if so, outputs a satisfying assignment. Your algorithm should run in time O(m + n).
Hint: Think carefully about the precise conditions under which the system of inequalities has a
satisfying assignment. You may use any standard algorithm as a subroutine. You may also use an
algorithm that solves the first part of the problem as a subroutine to solve the second part.
3. Your city has n junctions numbered 1 through n. There are m one-way roads between the junctions.
As a mayor of the city, you have to ensure the security of all the junctions. To ensure the security, you
have to build some police checkpoints.
Each checkpoint can only be built at a junction. A checkpoint
at junction i can protect junction j if either i = j or the police patrol car can drive from i to j and then
drive back to i. Building checkpoints costs some money.
As some areas of the city are more expensive
than others, building checkpoints at some junctions might cost more money than other junctions. You
have to determine the minimum budget B needed to ensure the security of all the junctions.
Design an algorithm to solve this problem. The input consists of
(a) a list of costs c1, . . . , cn, where ci
is the cost of building a checkpoint at junction i, and
(b) for every junction i, a list of all pairs (i, j) that represent a one-way road from junction i to junction
j.
The output is (the minimum budget) B.
You may use any standard algorithms as subroutines. Be sure to state the running time of your algorithm,
and to justify your running time bound. Your algorithm should run in time O(n + m).
4. Given two matrices A : p × q, B : q × r, C = AB is a p × r matrix, and time to compute C is p × q × r
(calculating by Cij =
Pq
k=1 AikBkj ).
Given three matrices A : p × q, B : q × r, C : r × s, though (AB)C = A(BC), the time required to
compute in the two cases could vary greatly. (E.g., when p = r = 1, q = s, one is 2q and the other is
2q
.)
Now, given n matrices Ai
, i = {1, 2, . . . , n}, and Ai has size pi × pi+1. Find the minimum cost way to
compute the multiplication A1A2 . . . An. (Dynamic programming)
2
