## Description

1. A Strongly Connected Component (SCC) S in a directed graph G = (V, E) is a maximal set of vertices S ⊆ V such that

for every pair of vertices u and v in S, they are mutually reachable from each other. A directed graph may contain

multiple SCCs. If we can decompose a directed graph into its SCCs, we can build a SCC graph: create a node for

each SCC and assign a directed edge Si → Sj

if there is a node p in the SCC Si has a directed edge to a node q in

SCC Sj

in the original graph.

A directed graph with eight nodes and corresponding three strongly connected components: S1 = {a, b, e}, S2 = { f , g}, S3 = {c, d, h}. So the

SCC graph has three nodes S1

, S2 and S3 and three edges S1 → S2

, S1 →

S3

, S3 → S2

.

(a) Prove that the SCC graph is a DAG (Directed Acyclic Graph).

(b) Given a directed graph G = (V, E) and all nodes can be reached from node v. Write an algorithm to build the

SCC graph. Prove the correctness and the time complexity. Your algorithm should be in linear time.

(Hint:

i. Do DFS on node v and assign post-order numbers to all nodes.

ii. Do another DFS against the edges on the node with the largest post-order number. The nodes the DFS can

reach belongs to a SCC.

iii. Remove the nodes in the SCC and repeat the second step.)

2. The longest path in a Directed Acyclic Graph (DAG) is a path that has the maximum length.

(a) Given a DAG with unweighted edges, the length of a path is the number of edges in the path. Write an algorithm

that finds the longest path in such a DAG.

(b) Given a DAG with weighted edges and the weights of edges are real numbers, the length of a path is the sum

of weights of the edges in the path. Write an algorithm that finds the longest path in such a DAG.

(c) Now consider a scheduling problem for a project which consists of n jobs. Each job i has an execution time

ti

, and a precondition that specifies jobs i can not be started before some jobs are finished. The precondition

relations between jobs are acyclic. Multiple jobs can be executed at the same time if the preconditions for those

jobs are satisfied. Give an algorithm to find a schedule that minimized the total time to finish all jobs. (Hints:

we can think each job as a node in a DAG. An edge u → v represents job v can not be started before finishing

job v.)

3. We have a number of n files, and file i has a length `i and probability pi

that whether it is accessed, and we want to

write these files on a tape in some order. We assume that every time we need to access a file, we have to start from

the beginning of tape until we reach the start of the requested file, so the time to access a file is proportional to the

total length of all the files that are saved before it. Design an algorithm that finds the optimal order of files on the

tape. The optimal order is an order that minimizes the average access time. The average access time is Pn

i=1

di pi

where di

is distance of the beginning of file i from the beginning of the tape (the total length of all the files that is

saved before file i).

4. In class we have seen the problem of scheduling jobs where each job i has a length of execution pi

, and a deadline

di

. Somebody built an algorithm SC which gives such optimal scheduling. She claims that the time complexity of

her algorithm is o(n log n) (little o stands for a function that is asymptotically below n log n). Show how you can use

SC to design a sorting algorithm with o(n log n) time complexity.

Æ Homework assignments are STRICTLY due on the exact time indicated. Please submit a hard copy of your homework

solution with your Name, Bruin ID, Discussion Number, clearly indicated on the first page. If your homework

consists of multiple pages, please staple them together. Email attachments or other electronic delivery methods are

not acceptable.

Æ We recommend to use LATEX, LYX or other word processing software for submitting the homework. This is not a

requirement but it helps us to grade the homework and give feedback. For grading, we will take into account both

the correctness and the clarity. Your answer are supposed to be in a simple and understandable manner. Sloppy

answers are expected to receiver fewer points.

Æ Unless specified, you should justify your algorithm with proof of correctness and time complexity.