Project #97580 - Algorithm

Question 1. Let A[1], . . . , A[2k] be a list of values that are sorted in increasing order. Your goal is find the i ∈ [k] such that f(i) = A[i + k] − A[i] is maximized. Unfortunately you don’t have time to test all k pairs but luckily you are happy with an approximate solution. (1) Design a 2-approximation that only requires reading O(1) values from the list. (2) Design a (1 + )-approximation that only requires reading O( −1 log k) values from the list. Hint: For the first part consider reading A[1], A[k], A[k + 1], and A[2k]. For the second part, one possible approach involves performing O(1/) binary searches. Remember to analyze the running time and prove the approximation ratio.

Question 2. Let G = (V, E) be an undirected graph in which each node has degree at most d. Design a polynomial time algorithm that finds an independent set whose size is at least 1/(d + 1) times that of the largest independent set. Remember to analyze the running time and prove the approximation ratio.

Question 3. The input to the Min-Squares problem is a set of positive integers x1, . . . , xn, r and L. We want to know if it is possible to partition x1, . . . , xn into r sets S1, S2, . . . , Sr such that Xr i=1 ï£« ï£­ X x∈Si x ï£¶ ï£¸ 2 ≤ L . Prove that Min-Squares is NP-Complete via a reduction from SubsetSum.

Question 4. Design (and analyze) a factor 4 approximation algorithm for Min-Squares, i.e., minimizing Pr i=1 P x∈Si x 2 . Hint: For Q3 and Q4, note that Pr i=1 P x∈Si x 2 ≥ r ( Pn i=1 xi/r) 2 .

Question 5. In the Best-Sat problem, we are given a set of OR-clauses, and we want to find an assignment that satisfies as many as possible. You may assume that the variables involved in each clause are distinct, i.e., you can’t have a clause like x1 ∨ x2 ∨ x¯2 ∨ x3. (1) Randomly set each variable to true or false by flipping a coin. Suppose the input has m clauses, of which the jth has kj literals. What is the expected number of clauses satisfied as a function of k1, . . . , km? Show that if all clauses contain exactly k literals, then the ratio between the optimal value and the expected number of satisfied clauses is ≤ 1 + 1/(2k − 1). (2) Can you make this algorithm deterministic? Hint: Instead of flipping a coin for each variable, select the value that satisfies the most of the as-of-yet unsatisfied clauses.

Question 6. The input to demi3sat is a 3sat formula φ. The output should be “yes” iff there is a satisfying assignment for φ such that exactly half the variables are set to “true”. Prove that demi3sat is NP-complete.

 Subject Computer Due By (Pacific Time) 12/04/2015 12:00 am
TutorRating
pallavi

Chat Now!

out of 1971 reviews
amosmm

Chat Now!

out of 766 reviews
PhyzKyd

Chat Now!

out of 1164 reviews
rajdeep77

Chat Now!

out of 721 reviews
sctys

Chat Now!

out of 1600 reviews

Chat Now!

out of 770 reviews
topnotcher

Chat Now!

out of 766 reviews
XXXIAO

Chat Now!

out of 680 reviews