Exam 2 Cards

Question 1

What NP hard problem did we start with for our reduction to show that 0-1 knapsack is NP hard?

Answer 1

subset sum

Question 2

Suppose that graph A from the pdf for the exam has a flow network as indicated. What augmenting path would the edmonds-karp algorithm choose?

Answer 2

2, 3, 6,

Question 3

Experimental cuisine problem - what is the value of P and what is the value of k

Answer 3

p is 0 and k is k_clique

Question 4

If V is the number of vertices, E is the number of edges, and f* is the max flow of the network, what is the asymptotic runtime of Ford-Fulkerson?

Answer 4

O(E |f*|)

Question 5

In the maximum flow for the graph G on the pdf for the exam, what is the flow on the edge from vertex s to vertex 1?

Answer 5

8

Question 6

What is the maximum flow of the graph G that appears on the pdf for the exam?

Answer 6

30

Question 7

For the graph G on the pdf for the exam, what is the min ST cut? Select all vertices on the S side of the cut.

Answer 7

1, 3, 4, 6

Question 8

Showing that a problem is an element of NP means that if it is solvable in deterministic polynomial time then so is every problem in NP

Answer 8

False

Question 9

Let X be a problem that belongs to the class NP, then which one of the following is true?

Answer 9

If X is NP-Hard then it is NP-Complete

Question 10

Consider two decision problems, Q1, Q2 such that Q1 reduces un polynomial time to 3-SAT and 3-SAT reduces in polynomial time to Q2. Then which of the following is consistent with the above statement?

Answer 10

Q2 is NP-Hard

Question 11

In graph A on the pdf, in the corresponding residual flow graph Gf, what is the capacity of the edge from node 1 to node 2?

Answer 11

6

Question 12

The problem 3-SAT anad 2-SAT are

Answer 12

NP-Complete and in P respectively

Question 13

To verify a yes answer for the Set-Partition problem, a good certificate would be the value v such that each partition sums to the value v.

Answer 13

False

Question 14

Consider the following two problems on undirected graphs
a : given G does G have a vertex cover of size |V| - 4?
B : Given G does G have a vertex cover of size 5

Which of the following is true?

Answer 14

Both a and B are in P

Question 15

Select all statements that imply that the flow is maximum

Answer 15

there is no augmenting path from S to T in the residual flow network, AND the flow across any ST cut is equal to the capacity of the minimum cut

Question 16

Suppose we have a flow network X with a maximum flow and we increase the capacity of an edge in the flow network by 4 and we wish to update the maximum flow without starting over. What is the maximum number of augmenting paths that the Edmunds-Karp algorithm might require to bring X to the new max flow?

Answer 16

4