CS575 Assignment 4

Description

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

[Part A] Theory [90%]:

 (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.

1. [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.

1. [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).

1.  [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 G² = (V, E²) such that (u, w) Î E² if and only if for some v Î V, both (u, v) Î E and (v, w) Î That is, G² 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 G² from G for the adjacency-matrix representation of G. Give the running time of your algorithm.

Hint:

Adjacency matrix in In G^2:

A²[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 G²

1. [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).

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

1. (4%) Design a DFS-based algorithm for checking whether a graph is bipartite.
2. (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.

1. Construct such a graph for the following maze.
2. 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

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.

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

• (8%) Implement your algorithm of finding the connected components for (i) and (ii), and print out the connect components of (i) and (ii).
• (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.