Description

Topics: Graph theory; Depth-first search, Breadth-first search, topological sorting, and linear programming.

[Part A] Theory [90%]:

1. (9%) Explain how to determine whether or not an undirected graph is connected? And whether or not it is a tree? Using the following graph as an example to justify your answer.

2. [8%] Does an undirected graph with 5 vertices, each of degree 3 exist? If yes draw the graph, otherwise explain why there is no such graph.

3. [10%]Apply depth first search to the following graph. Show the graph after a new edge has been identified as a tree, forward, backward, or cross edge and indicate its type. Show also the current color of all the nodes. (NOTE: assume starting from node 1, and go to node 2 first).

4. [10%] Apply topological sort to the graph below. Show the sequence of the nodes found by your application. Include also the discovery and finishing time of each node. (Assume the starting node is 1, the second node to go is 7. Also node 2 will be selected before node 4.)

5. (11%) The square of a directed graph G(V, E) is the graph G2 = (V, E2) such that
(u, w)  E2 if and only if for some v  V, both (u, v)  E and (v, w)  E. That is, G2 contains an edge between u and w whenever G contains a path with exactly two edges between u and w. Describe an efficient algorithm for computing G2 from G for the adjacency-matrix representation of G. Give the running time of your algorithm.

Hint:
Adjacency matrix in In G2: A2[i, j] = 1 if (A[i, 1] =1 && A[1, j] = 1) or (A[i, 2] =1 && A[2, j] = 1) or… or (A[i, n] =1 && A[n, j]=1)

Algorithm is defined in function CreateGsquare(A, n)
Input: Adjacency matrix A for graph G (n = |V|)
Output: Adjacency matrix Asquare for graph G2

6. [12%] A graph is said to be bipartite if all its vertices can be partitioned into two disjoint subsets X and Y so that every edge connects a vertex in X with a vertex in Y. (We can also say that a graph is bipartite if its vertices can be colored in two colors so that every edge has its vertices colored in different colors; such graphs are also called 2-colorable).

(a) (4%) Indicate whether graph (i) and (ii) are bipartite

b. (4%) Design a DFS-based algorithm for checking whether a graph is bipartite.
c. (4%) Design a BFS-based algorithm for checking whether a graph is bipartite.

7. [10%]

One can model a maze by having a vertex for a starting point, a finishing point, dead ends, and all the points in the maze where more than one path can be taken, and then connecting the vertices according to the paths in the maze.
a. Construct such a graph for the following maze.
b. Which traversal–DFS or BFS–would you use if you found yourself in a maze and why?

8. [10%] A merchant plans to manufacture two models of home computers at costs of $250 and $400, respectively. To sell the computers, the $250 model yields a profit of $45 and the $400 model yields a profit of $50. The merchant estimates that the total monthly demand will not exceed 250 units. Find the number of units of each model that should be stocked in order to maximize profit. Assume that the merchant does not want to invest more than $70,000 in computer inventory.

9. [10%] Using the Simplex Algorithm to solve the three variables linear programming problem
Maximize P = 20×1 + 10×2 + 15×3
Subject to: 3×1 + 2×2 + 5×3 ≤ 55
2×1 + x2 + x3 ≤ 26
x1 + x2 + 3×3 ≤ 30
5×1 + 2×2 + 4×3 ≤ 57
x1 , x2 , x3 ≥ 0

Show the results through the pivot operations and linear program (show the table step by step by hand).

[Part B]: Graph Algorithm (20%)

B.1. (10%)
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 (1%)
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. (1%)
3. Write and run your program to print out the result for verification (i.e., minimum number of semesters) (8%)

B.2. (10%)
In order to find the connected components or find out whether there is a cycle in graph (i) and (ii), you need to choose and use correct data structure of the graph representation for time and space efficiency.

(a) (2%) Indicate what data structure to represent (i) and (ii), respectively.

(b) (8%) Implement your algorithm of finding the connected components for (i) and (ii), and print out the connect components of (i) and (ii).
(c) (8%) Implement your algorithm of determining whether there is a cycle in (i) and (ii), and print out your finding by “yes” or “no”. (Extra 5 points: print out the cycle nodes in a correct order).
(Note: For (b) and (c), you can do one of them).

B.3. [Optional Extra point 10%]

To answer the Question #9 (Part A), implement the Simplex Algorithm and display the results by your program.