Question 1 – Graph Algorithm

Suppose a CS curriculum consists of n courses, all of them mandatory. The prerequisite graph G has a node for each course, and an edge from course v to course w if and only if v is a prerequisite for w. Find and algorithm that works directly with this graph representation, and computes the minimum number of semesters necessary to complete the curriculum (Assume that a student can take any number of courses in one semester). The running time of your algorithm should be linear.

Using following example to justify your answer:

The CS Department requires fifteen one-semester courses with the prerequisites shown below:

cs1 cs2 cs3

cs4 requires cs2

cs5 requires cs4

cs6 requires cs1 and cs3

cs7 requires cs4

cs8 requires cs5 and cs6

cs9 requires cs7

cs10 requires cs9 cs11 requires cs8

cs12 requires cs3

cs13 requires cs6

cs14 requires cs4 and cs6 cs15 requires cs14

Your task is to determine the minimum number of semesters needed to finish the degree.

(Hint: Represent the courses and their prerequisites as a DAG. Finding the minimum number of semesters translates to a simple graph problem, e.g., Using adjacency-matrix representation in BFS).

Please provide:

1. Manually plot the DAG
2. Explain the algorithm that you are going to implement by the Pseudo-code, and

indicate the minimum number of semesters necessary to finish the degree.

3. Write and run your program to print out the result for verification (i.e., minimum

number of semesters)

Question 2 – Shortest path algorithm design and programming implementation

(1)

Suppose there are a group of cities, which are modeled by a strongly connected undirected graph G = (V, E) with positive edge weights representing the distances between two cities. A particular city is the capital city a Î V. Give an efficient algorithm for finding shortest paths between all pairs of cities, with the one restriction that these paths must all pass through the capital city. (Note that: we allow one city to be passed more than once if needed).

(2) Programming: Implement your designed algorithm, and print out the shortest path from node d to node i via node a using the graph shown below. Suppose the capital city is node “a”