Introduction to Analysis of AlgorithmsCSE 4081YOUR NAME:
Fall 2014Exam 3Points 40Time 60 min
ANSWERS ARE TO BE CRISP, ONLY ON THE ANSWER SHEET PROVIDED.
[Students ignore these key words: Foundations, Problem solving, Algorithm understanding.]
1a / 21b / 2
1c / 3
1d / 3
2a / 3
2b / 2
2c / 3
2d / 2
3a / 3
3b / 2
3c / 2
3d / 3
4a / 2
4b / 2
4c / 2
4d / 4
5a / 1
5b / 1
5c / 1
5d / 1
5e / 1
5f / 1
5g / U = {x1, x2,
x3, x4,
x5, x6,
x7} / 3U =
C = { (x1),
(~x2),
(~x1),
(x1, x4),
(x3, ~x4, x2, x5, ~x6, ~x7)
} / 3C =
/ 4
50
*
Q1. Refer to the graph G below.
Input: G
Output: -questions below-
1 Let Q be a queue (of nodes);
2 push(Q, v2); // v2 is the node in above G
3 counter = 0;
4 While Q is not empty do
5v = pop(Q);
6mark v as ‘finished’;
7V = V – v;
8 counter++;
9For each edge (v, w) ϵ E do
10 counter++;
11 E = E – (v, w);
12 if w is not ‘finished’
then push(Q, w);
end for;
end while;
End algorithm. / Algorithm DFS-traversal
Input: G
Output: -questions below-
1 Let S be a stack (of nodes);
2 push(S, v1); // v1 is the node in above G
3 counter = 0;
4 While S is not empty do
5v = pop(S);
6mark v as ‘finished’;
7V = V – v;
8 counter++;
9For each edge (v, w) ϵ E do
10 E = E – (v, w);
11 if w is not ‘finished’
then push(S, w);
end for;
end while;
End algorithm.
a. What is the value of the ‘counter’ after the algorithm terminates? [2]
Ans. n+m, 12, or 15 / c. What is the value of the ‘counter’ after the algorithm terminates? [2]
Ans. n, 5, or 8
b. Which nodes are on the leaves of the resulting BFS-traversal spanning tree? [3]
Ans. v3, v4
Or, v3, v4, v5 / d. What is the largest depth of the DFS-traversal spanning tree, starting with 0 at root (v1)? [3]
Ans. 4, v1-v2-v5-v4-v3, v1-v3-v4-v5-v2, v1-v4-v3-v5-v2
Q2.
a.Using the DFS-based Articulation Point finding algorithm on the graph G above, starting with node v1, what will be the num values of all nodes? [3]
Ans: Pre-order DFS traversal
v1: 1, v2: 2, v5: 3, v4: 4, v3: 5
Or, v1: 1, v3: 2, v4: 3, v5: 4, v2: 5
b. Is there a “back-arc” that could not be traveled by the DFS traversal?If so, which one? If not, why so? [2]
Ans. Yes. v2-v1,
or, v3-v1
c. What will be their low values?[3]
Ans: all 1’s
d.Which node(s) is/are the articulation point(s)?[2]
Ans: none
Q3.Use the DFS-based strongly connected component finding algorithm on the graph G below, and answer the following questions.
a. Start the first pass DFS with the node v4. What is the post-order traversal number on each node after you finish? [3]
Ans: Post-order DFS traversal
v3 (1), v1 (2), v5(3), v4 (4), and v2 (5)
b. How many DFS spanning tree(s) do you have from the above traversal, and what is (are) it (they)? [2]
Ans. 2 Trees,
v4-v5-v1-v3, v2
c. Which node will you start with your second pass DFS traversal?[2]
Ans. v2
Highest numbered.
d. What are the resulting strongly connected components in G?[3]
Ans. (v4-v5-v1-v3), (v2)
Q4. Maximize (3x - 3y), subject to the three linear constraints
2x + 4y <= 28,
3x – y >= 6,
x – y <= 3
The two variables x, y >= 0.
a. Convert the following problem into standard form of LP.[2]
max (3x-3y), 2x+4y<=28, -3x+y<= -6, x-y<=3
x, y>=0
b. Convert your standard form LP to a slack form.[2]
z=0+3x-3y, a=28-2x-4y, b= -6+3x-y, c=3-x+y
x, y, a, b, c >=0
c. Which one is your first entering variable?[2]
x
d. Run twopivoting iterations in the Simplex algorithm and write the resulting slack form. If it terminates before three iterations, then say so, and write the final slack form. [4]
1st iteration:
Note: x=0, y=0 is not a feasible solution: (x=0, y=0, a=28, b= -6 [bad], c=3)
b does not constrained, but needs x>=2.
Most constraining is c, with x<=3
x=3-c+y,
a=28-6+2c-2y-4y = 22+2c-6y
b= -6-9-3c+3y+y = -15-3c+4y
z= 9-3c+3y-3y = 9-3c
2nd iteration:
No entering variable, Simplex algorithm stops, with
Optimum=9, at x=3, y=0
Ans: to be the above slack form from 1st iteration.
Ans.
Q5. Answer Yes/No for the following six short questions.[6]
a. Is 2-SAT problem outside the NP-class?
Ans. No
b. Is it true that there are problems which are not NP-class problems?
Ans. Yes.
c. Is it true that the set of NP-class problems is a subset of the NP-complete problems?
Ans. No.
d. Is it true that no exponential algorithm can be developed when a problem is proved to be P-class?
Ans. No.
e. In order to prove a problem X to be NP-hard, one needs to develop a polynomial transformation from a known NP-hard problem Y to X. Is this statement true?
Ans. Yes.
f. There exists a polynomial transformation from a problem X to a known P-class problemY. Is X also a P-class problem?
Ans. Yes.
g. Translate the following SAT problem to a 3-SAT problem. [4]
[Write each new 3-clause in a separate line for better readability.]
U = {x1, x2, x3, x4, x5, x6, x7} / 3U =variables must not be repeated
C = { (x1), (~x2), (~x1),
(x1, x4),
(x3, ~x4, x2, x5, ~x6, ~x7) } / 3C =