COT 5405 Analysis of Algorithms Spring 2005
On-Campus Comprehensive Exam
Name: ______
UFID: ______- ______
E-mail: ______
Instructions:
1. Write neatly and legibly
2. While grading, not only your final answer but also your approach to the problem will be evaluated
3. You have to attempt ALL THREE problems. You have choices under each problem.
5. Total time for the exam is 120 minutes
6. You are not allowed to use a calculator for this exam
I have read carefully, and have understood the above instructions. On my honor, I have neither given nor received unauthorized aid on this examination.
Signature: ______
Date: ____ (MM) / ____ (DD) / ______(YYYY)
Q1. Please attempt only 2 out of the following 3 subparts
(7.5 points each = total 15 points)
a) You are interested in analyzing some hard-to-obtain data from two separate databases having n and m numerical values – so there are n + m values in total – and you may assume that no two values are the same. You’d like to determine the median of this set of n + m values, which we will define here to be the (n+m)/2 th smallest value. However, the only way you can access these values is through queries to the databases. In a single query, you can specify a value k to one of the two databases, and the chosen database will return the kth smallest value that it contains. Give an efficient algorithm that finds the median assuming that each query to any of the databases requires constant time. Also, derive the asymptotic complexity of your algorithm.
(Hint: For your convenience, you may assume that both n and m are in the form 2i – 1, where i is an integer).
Solution:
Follow the method repetitively. Compare the individual medians of the two databases by querying them. Whichever is greater, discard the elements greater than it from your consideration. Similarly, whichever is smaller, discard the elements smaller than it from your consideration. Thus, at every stage we are pruning half of the current input size. So the overall complexity is O(log (n+m) ).
b) Consider the 0/1 knapsack problem with n objects whose profits and weights are, respectively. The capacity of the knapsack is m.
(1) Suppose all the objects have the same profit.
Give an efficient algorithm to solve this problem. Prove that the output of your algorithm is optimal.
(2) Suppose the weight of each object is ³ em for some pre-defined constant fraction e.
Develop a polynomial time algorithm to solve this problem.
c) Consider the 0/1 knapsack problem with n objects whose profits and weights are, respectively. The capacity of the knapsack is m.
(1) Suppose all the objects have the same profit.
Give an efficient algorithm to solve this problem. Prove that the output of your algorithm is optimal.
(2) Suppose the weight of each object is ³ em for some pre-defined constant fraction e.
Develop a polynomial time algorithm to solve this problem.
d) On a table lie n coins in a row, where the ith coin from the left has value xi ³ 0. Do not assume anything about the order of the xi’s – they are in no particular order. You get to pick up any set of coins, so long as you never pick up two adjacent coins. Give a polynomial-time algorithm that picks a (legal) set of coins of maximum total value. Prove that your algorithm is correct, and runs in polynomial time.
Q2. Please attempt only 1 out of the 2 subparts (8 marks):
a) The LONGEST-PATH problem (which decides for a given <G, k>, where G is a directed graph and k is an integer, if there exists a simple path in G whole length is ³ k) is known to be NP-complete. Now we consider the other problem:
DAG-LONGEST-PATH: Given <G, k> where G is a directed acyclic graph and k is an integer, is there a simple path in G whole length is ³ k?
A student claims that since DAG-LONGEST-PATH directly reduces to LONGEST-PATH, it must be NP-Complete too. Now, his claim is either right or it is wrong. If it is wrong, there are three possible ways his claim could be wrong:
· DAG-LONGEST-PATH is not in NP
· DAG-LONGEST-PATH does not reduce to LONGEST-PATH
· DAG-LONGEST-PATH does reduce to LONGEST-PATH but that does not mean DAG-LONGEST-PATH is NP-Complete.
Answer the following questions:
a. Is DAG-LONGEST-PATH in NP? Prove or disprove.
b. Does DAG-LONGEST-PATH reduce to LONGEST-PATH? If yes, show how.
c. If we assume DAG-LONGEST-PATH ≤p LONGEST-PATH, can we declare that DAG-LONGEST-PATH is NP-Complete from there?
b) 2-Sol-SAT is same as the CNF-SAT problem with the extra condition that you decide whether the Boolean expression is satisfiable with at least two distinct solution sets.
A solution set is defined as a set of Boolean assignments to all the variables used in the clauses so that the final expression is satisfied. For example, for (x1) Ù (x1Úx2) is satisfiable with two solution sets (x1 = true, x2 = true) and (x1 = true, x2 = false).
Is 2-Sol-SAT NP-Complete? If yes, show how. Otherwise, give a polynomial time algorithm to solve 2-Sol-SAT.
Q3. Attempt any 3 out of 5 subparts (3 * 4 = 12 points)
Answer in short (justification must be given for each problem, a yes or no answer is not sufficient):
a. Manna and Jimin both submit their PhD theses.
· Jimin claims to have found out a polynomial time algorithm to decide SAT.
· Manna claims to be have found out a o(N) time algorithm to sort N arbitrary even integers.
Who is more likely to get his/her PhD?
b. Prove or disprove: for all c > 0, .
c. Suppose problem A can be reduced into problem B in Θ(n3) time. Problem B is known to have an O(n4) algorithm. Choose the strictest bound of running time of A using B from the following three options:
· Θ (n3) + O(n4) = O(n4)
· Θ (n3) * O(n4) = O(n3 + 4) = O(n7)
· Θ (n3) º O(n4) = O( Θ(n3) )4 = O(n12)
d. Suppose a professor has proved that some NP-complete problems cannot be solved faster than O(n10000) time. Does that mean P ¹ NP?
e. A melon-selling farmer has n melons. The weight of each melon, an integer (lbs), is distinct. A customer asks for exactly m pounds of uncut melons. Now, the farmer has the following problem: If it is possible to satisfy the customer, he should do so by finding the appropriate melons as efficiently as possible, or else tell the customer that it is not possible to fulfill his request.
The farmer’s problem is (choose the answer closest to truth):
· In P
· Not in P
· Can’t tell L
Analysis of Algorithms Spring 2005 On-Campus Final Exam Page 14 of 14