T F T F T F T F T F T F T F
T F T F
T F
T F T F T F T F
T F T F
T F T F T F T F T F
Adding two n-bit numbers can be done in time O(n).
Multiplying two n-bit numbers can be done in time O(n1.99).
The following is a legitimate choice for RSA: N = pq = 35, e = 3.
T(n)=3T(n/3)+n2,T(1)=0hassolutionT(n)=O(n2).
The FFT of the vector (0, 0, …, 0) is the vector (1, 0, …, 0).
Depth-first search in a DAG with n nodes takes O(n) time.
If a graph with positive and negative edges has no negative cycles reachable from s, then Dijkstras algorithm works in finding shortest paths from s.
If all weights in a graph are distinct, then there is a unique shortest path from s to t.
In a weighted graph with distinct edge lengths, the two shortest edges are both in the minimum spanning tree.
In a weighted graph with distinct edge lengths, the three shortest edges are all in the minimum spanning tree.
In union-find with path compression, every find takes O(log n) time.
There is a polynomial algorithm for linear programming.
Simplex is a polynomial-time algorithm.
If in a network we increase the capacity of an edge in the minimum cut, the maximum flow gets increased.
In a dynamic programming algorithm, the time required by the algorithm is determined by the number of nodes of the DAG of the subproblems.
In a dynamic programming algorithm, using recursion with memoized (hashed) results can enable the algorithm to run much faster for some instances.
If in a network we decrease the capacity of an edge in a minimum cut, the maximum flow gets decreased. If in a network all capacities are integers, then the maximum flow will have integer value.
If in a linear program all coefficients are integers , then the optimum solution will have integer value. Branch-and-bound always returns the optimum.
Local search algorithms always return the optimum.
1 True or False? (60 points)
Circle the right answer. No explanation necessary. No points subtracted for wrong answers, so give us your best guess.
2
T F = ̸= T F = ̸= T F = ̸= T F = ̸= T F = ̸= T F = ̸= T F = ̸=
T F = ̸= T F = ̸=
T F = ̸= T F = ̸=
For the remaining questions there are four possible answers:
– true (T);
– false (F);
– trueifandonlyifP =NP (=);and – trueifandonlyifP ̸=NP (̸=).
In each case, circle the right one.
3SAT is NP-complete.
2SAT is NP-complete.
There is a polynomial-time reduction from 2SAT to 3SAT.
There is a polynomial-time reduction from 3SAT to 2SAT.
If a problem A reduces to a problem B , and B is NP-complete, then A is NP-complete. Factoring is in NP.
There is a polynomial time algorithm for telling, given a graph G, whether there is a simple path of length 5 from s to t.
There is a polynomial time algorithm for telling, given a graph G and an integer k, whether there is a simple path of length k from s to t.
There is a polynomial reduction from integer linear programming to linear programming.
There is a polynomial algorithm for approximating the Traveling Salesman Problem with triangle inequality within a factor of two.
There is a polynomial algorithm for approximating the general Traveling Salesman Problem within a factor of two.
3
2 Red Nodes (70 points)
We are given a graph with positive weights in which certain nodes are designated red (think of them as toll stations), and an integer R. We want to find the shortest path from s to t that uses at most R intermediate red nodes (i.e., not counting the two end nodes).
We want to solve this problem by dynamic programming (another way to see it: by R runs of Dijkstra). Fill the blanks:
For each node i and r ≤ R, let dist(i, r) be the length of the shortest path from s to i using at most r intermediate red nodes.
1. Describe briefly how to compute the dist(i, 0)’s for every node i.
2. Describe briefly how to compute the dist(i, r + 1)’s once you have all dist(j, r)’s.
3. What is the running time of your overall algorithm, as a function of the number of nodes n and edges m of the graph? Justify briefly.
4
4. Suppose now that you want to want to find the shortest path from s to t that goes through at least R red nodes (e.g., now the red nodes are drive-through MacDonald’s). Do you think there is an efficient algorithm for solving this problem? Justify your answer.
5. Now we have a more general problem: We are given a graph with two positive integer weights on each edge (say, time and energy, t(i,j) and e(i,j)). We are asked, is there a path from s to t which has total time at most T and total energy consumption at most E? Give a dynamic programming algorithm for this problem. Fill the blanks:
For each node i and integers t ≤ T and e ≤ E define the predicate CAN GO(i, t, e), which is intended to be true
CAN GO(i, 0, 0) =
for t = 1,…,T, for e = 1,…,E, for each node i CAN GO(i,t,e) =
5
3 Contiguous Set Cover (15 points)
We know that the set cover problem (given a collection of sets and a number B, is there a sub- collection of B sets whose union covers everything?) is NP-complete. But suppose that the sets are contiguous, as in the collection of sets {1, 2, 3}, {1, 2}, {2, 3, 4}, {3, 4, 5}.{4, 5, 6, 7}. Give an efficient algorithm for solving this problem and prove that it is correct.
(Hint: There is a very simple idea that works here. If you are thinking and writing a complicated solution, the chances are overwhelming that it is wrong. Two sentences should suffice to explain the algorithm.)
6
4 Lollipops (20 points)
Let G be a graph with 2n nodes. We say that G has a lollipop if G has a simple cycle with n nodes, and there is also a simple path consisting of the remaining n nodes of G, and finally there is an edge connecting one of the endpoints of the path with one of the nodes in the cycle. Lollipop is this problem: Given a graph G with an even number of nodes, does it have a lollipop? We want to show that this problem is NP-complete. Fill the blanks below.
First, Lollipop is in NP because
We shall reduce
Describe the reduction: Given a
to .
7