Algorithms



Introduction to Analysis of Algorithms CSE 4081 YOUR NAME:

Fall 2014 Exam 3 Points 40 Time 60 min

ANSWERS ARE TO BE CRISP, ONLY ON THE ANSWER SHEET PROVIDED.

[Students ignore these key words: Foundations, Problem solving, Algorithm understanding.]

|1a | |2 |

|1b | |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, |4 |

| |x3, x4, | |

| |x5, x6, | |

| |x7} | |

| |3U = | |

| | | |

| |C = { (x1), | |

| | | |

| | | |

| |(~x2), | |

| | | |

| | | |

| |(~x1), | |

| | | |

| | | |

| |(x1, x4), | |

| | | |

| | | |

| | | |

| |(x3, ~x4, x2, x5, ~x6, ~x7) | |

| |} | |

| |3C = | |

| | | |

| | |50 |

*

Q1. Refer to the graph G below.

|Algorithm BFS-traversal |Algorithm DFS-traversal |

|Input: G |Input: G |

|Output: -questions below- |Output: -questions below- |

|1 Let Q be a queue (of nodes); |1 Let S be a stack (of nodes); |

|2 push(Q, v2); // v2 is the node in above G |2 push(S, v1); // v1 is the node in above G |

|3 counter = 0; |3 counter = 0; |

|4 While Q is not empty do |4 While S is not empty do |

|5 v = pop(Q); |5 v = pop(S); |

|6 mark v as ‘finished’; |6 mark v as ‘finished’; |

|7 V = V – v; |7 V = V – v; |

|8 counter++; |8 counter++; |

|9 For each edge (v, w) ϵ E do |9 For each edge (v, w) ϵ E do |

|10 counter++; |10 E = E – (v, w); |

|11 E = E – (v, w); |11 if w is not ‘finished’ |

|12 if w is not ‘finished’ |then push(S, w); |

|then push(Q, w); |end for; |

|end for; |end while; |

|end while; |End algorithm. |

|End algorithm. | |

|a. What is the value of the ‘counter’ after the algorithm |c. What is the value of the ‘counter’ after the algorithm |

|terminates? [2] |terminates? [2] |

|Ans. n+m, 12, or 15 |Ans. n, 5, or 8 |

|b. Which nodes are on the leaves of the resulting BFS-traversal |d. What is the largest depth of the DFS-traversal spanning tree, |

|spanning tree? [3] |starting with 0 at root (v1)? [3] |

|Ans. v3, v4 |Ans. 4, v1-v2-v5-v4-v3, v1-v3-v4-v5-v2, v1-v4-v3-v5-v2 |

|Or, v3, v4, v5 | |

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 = 6,

x – y = 0.

a. Convert the following problem into standard form of LP. [2]

max (3x-3y), 2x+4y=2.

Most constraining is c, with x ................
................

In order to avoid copyright disputes, this page is only a partial summary.

Google Online Preview   Download