## 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