The exam is open book, open notes, and calculators are permitted (although they are not necessarily helpful). You should take at most 3 hours for the exam.
You should read all the problems as soon as possible; problems are not necessarily in order of difficulty.
Please solve ALL the problems. T/F questions are worth 3 points each. Multiple choice questions are worth 5 points each. The exam totals 150 points.
First name:
Last name:
True or false ?
1. T F Mergesort is both and . Answer True False
2. T F If f(n) is O(n2) and g(n) is O(n), then f(n)/g(n) is O(n). Answer True False
3. T F Consider any graph G with edge capacities, a source s, and a sink t. Suppose the maximum flow from s to t is greater than 0, so there is a path from s to t. Then there always exists an edge so that increasing the capacity on the edge increases the maximum flow from s to t. Answer True False
4. T F For a string N of length n and a pattern P of length p, after the suffix tree for N is constructed, all occurences of the pattern in the string can be found in O(p) time. Answer True False
5. T F If I multiply all the edge capacities in an s-t flow problem by a positive constant k > 0, then the maximum flow increases by the same factor of k. Answer True False
6. T F If I add 1 to all the edge capacities in an s-t flow problem, then the maximum flow increases by 1. Answer True False
7. T F I have two random walks, both starting at 0 and with a reflecting boundary at 0. Each step, Walk A goes up 1 with probability 1/2 and down 1 with probability 1/2 (except at the boundary). Each step, Walk B goes up 1 with probability 1/3 and down 1 with probability 2/3. The average time for walk A to reach 1000 is less than the average time for walk B to reach 100. Answer True False
8. T F In the set resemblance problem, we took several permutations, and checked how many times in order to estimate the resemblance. Things would work equally well if we has use instead of everywhere. Answer True False
9. T F If there are 25 people in a room, it is more likely than not that some two have the same birthday. Answer True False
10. T F The probability that a random number between 1 and 10100 is prime is between 1 in 100 and 1 in 200. Answer True False
11. T F Let G ge a connected, undirected graph whose edge weights are all even integers. I choose a subset S of the edges and add 1 to each of them. The edges in the minimum spanning tree do not change. Answer True False
12. T F I have a connected weighted undirected graph G with a minimum spanning tree T. If I increase the weight of one edge, the new minimum spanning tree T' of the new graph G' differs from T in at most one edge. Answer True False
13. T F The minimum spanning tree of an undirected, connected, weighted graph (with positive edge weights) is always no larger than the minimum Traveling Salesman tour for the graph. Answer True False
14. T F One way to implement topological sort is to repeatedly do the following (until no vertices are left): find a vertex with indegree 0, output it, and remove it and all of its outgoing edges from the graph. Answer True False
15. T F One way to solve an integer linear program is to solve the unconstained linear program and round. Answer True False
16. T F If I could factor, I could break RSA. Answer True False
17. T F If I could break RSA, I could factor. Answer True False
18. T F The following is a 1/2-approximation for MAX-SAT; pick any truth assignment T and let T' be the truth assignment that disagrees everywhere with T. From T or T', choose the assignment that satisfies more clauses. Answer True False
19. T F For the greedy set cover problem, suppose I am trying to cover a set X using a collection of sets C such that each set S in C has size at most 4. Then I can obtain a set cover whose size is within a factor of 4 of the optimal using the greedy algorithm. Answer True False
20. T F A linear program that has at least 1 solution always has a unique optimal solution. Answer True False
21. T F The planar 2-approximation algorithm for the Traveling Salesman Problem will also work in three-dimensional space. Answer True False
22. T F A linear program always has at least one solution. Answer True False
23. Suppose I throw 1000 balls at random into 2000 bins. The number of empty bins I expect is closest to: (a) 1000 (b) 1100 (c) 1200 (d) 1300 (e) 1400 (f) 1500
Answer a b c d e f
24. Suppose I create a Bloom filter using 8 hash functions and 16 bits per item, that is, the size of the hash is dependent on the number of items being hashed. The probability of a false positive is closest to: (a) 0.05 (b) 0.02 (c) 0.004 (d) 0.0006 (e) 0.00008 (f) none of these is even the right order of magnitude
25. A proper vertex coloring of an undirected graph assigns a color to each vertex in such a way that if (u,v) is an edge of the graph, then vertex u and vertex v do not have the same color. Suppose that I have a graph with n vertices, e edges, and maximum degree d. Without loss of generality, let my set of colors be {1,2,3,...}. The greedy algorithm chooses an uncolored vertex at each step and assigns as its color the smallest possible valid number. The BEST upper bound we can give on the number of colors used by this algorithm is: (a) 2 (b) e (c) n (d) n/2 (e) d (f) d+1 (g) d+2
Answer a b c d e f g
26. Consider each of the following word as a set of letters: [arid, dash, drain, heard, lost, nose, shun, slate, snare, thread]. If I apply the greedy set-cover algorithm, breaking ties in favor of the word that appears first in the dictionary, what is the size of the resulting set cover? (a) 1 (b) 2 (c) 3 (d) 4 (e) 5 (f) 6
27. Which of the following problems is not known to be NP-hard? (a) Vertex Cover (b) Independent Set (c) Factoring (d) 3-SAT (e) Clique (f) none of the above
28. Strassen's algorithm split a matrix into 4 equal-sized parts and used 7 matrix multiplications. Assuming we could split the matrix into M equal-sized parts and find the answer using N multiplications (and various additions and subtractions) on these matrices, for what values of M and N, respectively, would we get something that is asymptotically faster than Strassen's algorithm? (a) 16 and 50 (b) 64 and 340 (c) 9 and 15 (d) a and b (e) a and c (f) b and c (g) all of the above (h) none of the above
Answer a b c d e f g h
29. For a dynamic programming problem, we obtain the following recurrence:
Answer a b c d e
30. I have developed a new type of hashing called ``Paired Hashing''. Each item hashed gets a pair of hash values in the range [0,n-1], with each hash value being given by a different random hash function. How many items should I expect to hash before getting a collision (two items with the same pair of hash values), say with probability 1/2. (a) (b) (c) (d) (e)
31. Consider the following matrix game, where a positive payoff goes to the row player. For
32. For the above game, the best strategy for the row player is to chose row 1 with probability: (a) 1/4 (b) 1/3 (c) 1/2 (d) 2/3 (e) 3/4
33. Which of the following is true about the residual graph of a flow network? (a) When there is no augmenting path from the source to sink, you've found the max-flow/min-cut. (b) All of the edges in the residual graph should have positive weight. (c) An edge in the residual graph at one step can be reversed in subsequent steps of the max-flow algorithm. (d) all of the above (e) none of the above
34. A Carmichael number is: (a) a 2 pseudo-prime (b) a 3 pseudo-prime (c) a 5 pseudo-prime (d) all of the above (e) none of the above (f) just (a) and (b)
35. Which of the following statements are true: (a) 16 is a non-trivial square root of 1 modulo 51; hence 51 is composite. (b) 7 is a non-trivial square root of 1 modulo 47; hence 47 is composite. (c) 8 is a non-trivial square root of 1 modulo 55; hence 55 is composite. (d) all of the above (e) none of the above
36. Consider the Multiple Catalog problem. You are a mail order catalog specialist, with a large list of n customers, and m items to sell. With the data you have available, you can accurately predict (completely) which people will buy each item you advertise. Because of costs, you can only advertise up to r items in a catalog. However, you are allowed to make two distinct catalogs, and ship one catalog to each customer. Your goal is simply to maximize the number of sales. This problem is NP-hard. One approximation algorithm is to just ship one type of catalog. You can guarantee that this is within what factor of the optimal solution using two catalogs? (a) 1 (b) 3/2 (c) 2 (d) 3 (e) no constant factor
37. Consider the following graph.
38. For the flow problem above, which edge does not cross the minimum cut? (a) sa (b) cd (c) ft (d) ef (e) none of the above
39. Suppose I try to find the gcd of 4402 and 2697 using Euclid's algorithm. Which of the following is not an intermediate step? (a) Euclid(713,279) (b) Euclid(124,31) (c) Euclid(155,124) (d) Euclid(93,62) (e) Euclid(1705,992)
40. 6301 is prime. Which of the following is equal to ? (a) xyz (b) yz2/x2 (c) z3/x (d) 1/(x2 y2) (e) none of the above
41. Consider the Huffman tree where the character frequencies are: Freq(A) = 16; Freq(B) = 8; Freq(C) = 4; Freq(D) = 2; Freq(E) = 1; Freq(F) = 1. The total length of the encoding with the above frequencies and the derived Huffman tree is: (a) 62 (b) 63 (c) 64 (d) 30 (e) 31