NAME:

CMPSCI 611
Advanced Algorithms
Final Exam Fall 2015

A. McGregor 17 December 2015

DIRECTIONS:

• Do not turn over the page until you are told to do so.

• This is a closed book exam. No communicating with

other students, or looking at notes, or using electronic
devices. You may ask the professor to clarify the mean-
ing of a question but do so in a way that causes minimal
disruption.

• If you finish early, you may leave early but do so as

quietly as possible. The exam script should be given to
the professor.

• There are five questions. Some questions may be eas-

ier than others. Don’t spend too long on a problem if
you’re stuck – you may find that there are other easier
questions.

• The front and back of the pages can be used for solu-
tions. There is also a blank page at the end that can
be used. If you are using these pages, clearly indicate
which question you’re answering.

• The exam will finish at 15:00 pm.

• Good luck!

1 /10
2 /10
3 /10
4 /10
5 /8+3
Total /48+3

1
Question 1 (True or False): For each of the following statements, indicate whether the state-
ment is true or false by circling the appropriate option. It is not necessary to give justification.

1. Given a bipartite graph, the maximum matching can be found in polynomial time.

• TRUE
• FALSE

2. The max value of 2x1 + x2 subject to the constraints x1 ≥ 0, x2 ≥ 0, x1 + x2 ≤ 1 is 2.

• TRUE
• FALSE

3. The Simplex algorithm runs in polynomial time.

• TRUE
• FALSE

4. If every capacity in a flow network is integral then the maximum flow between any two
nodes is integral.

• TRUE
• FALSE

5. For any random variable X, P (X − E [X])2 ≥ t2 ≤ V [X] /t2 .

 

• TRUE
• FALSE

2
Question 2 (Numbers): Let A = {a1 , a2 , . . . , an } be a set of positive integers where n is odd.
You may assume that the integers are distinct. The elements are not sorted.

1. Assuming any operation on two numbers in A takes O(1) time, how fast can each of the
following operations be performed (no justification required):
(a) Sorting the elements of A:

(b) Computing max(A):

(c) Computing median(A), i.e., the element with rank (n + 1)/2:

P
(d) Computing 1≤i<n (ai+1 − ai ):

− aj )2 :
P
(e) Computing 1≤i<j≤n (ai

2. Given the set A and a positive integer t, consider the problem of determining whether
there is a subset of A that sums to t. Each value of A may be used at most once and
the values in the empty subset sum to 0.
(a) Let M be an n × t table where M [i, j] = 1 if there is a subset of {a1 , . . . , ai } that
sums to j and M [i, j] = 0 otherwise. Give a formula relating M [i, j] to other entries
of the table and justify your answer.

M [i, j] =

(b) Write an algorithm for determining whether there is a subset of A that sums to t.
What is the running time of your algorithm in terms of n and t?

3
Question 3 (Reduction and Formulas):
1. Briefly explain why, if you design a polynomial time algorithm for any NP complete
problem, then you have proved P = N P .

An instance of 3-sat has exactly 3 literals per clause and we want to determine if there is a
setting of the variables such that the formula is satisfied. A related problem is k-sat where
every clause has exactly k literals. For example, (x1 ∨ x̄2 ) ∧ (x3 ∨ x4 ) is an instance of 2-sat.
Using the fact that 3-sat is N P -complete and 2-sat is in P , indicate if each of the following
two statements are TRUE or FALSE and give a brief justification.

2. If P 6= N P then 3-sat ≤P 2-sat, i.e., any 3-sat instance φ can be transformed (in
polynomial time) into a 2-sat instance that is satisfiable iff φ is satisfiable.

3. If P 6= N P then 2-sat ≤P 3-sat.

We next consider a polynomial time reduction from k-sat to 3-sat for any k > 3. Given an
instance φ of k-sat we create an instance 3-sat as follows: for each clause C = (a1 ∨a2 ∨. . .∨ak )
(where ai are literals) of φ, we introduce k − 3 new variables y1 , . . . , yk−3 and replace C by

f (C) = (a1 ∨ a2 ∨ y1 ) ∧ (ȳ1 ∨ a3 ∨ y2 ) ∧ . . . ∧ (ȳk−4 ∨ ak−2 ∨ yk−3 ) ∧ (ȳk−3 ∨ ak−1 ∨ ak ) .

4. Show that if C is satisfied there is a setting of y1 , . . . , yk−3 such that f (C) is satisfied.

5. Show that if f (C) is satisfied then C is also satisfied.

4
Question 4 (Assigning Tasks): Suppose there are n tasks to be done and m < n people who
are available to do these tasks. Task i takes ti minutes to complete and assume that t1 ≥
t2 ≥ . . . ≥ tn > 0. Your goal is to assign the tasks to the m people such that everyone finishes
in the smallest amount of time. Let opt be the smallest value such that it is possible to
assign the tasks such that everyone finishes in ≤ opt time. For example, if n = 4, m = 3,
t1 = 4, t2 = 3, t3 = 2, and t4 = 2 then opt = 4 since we can assign the first task to the first
person, the second task to the second person, and the remaining tasks to the third person.

1. For arbitrary t1 , . . . , tn , explain why opt ≥ t1 ?

Pn
2. For arbitrary t1 , . . . , tn , explain why opt ≥ i=1 ti /m?

3. For arbitrary t1 , . . . , tn , explain why opt ≥ tm + tm+1 ?

Consider the algorithm which assigns the tasks in order (i.e., the longest task is assigned first)
and gives task i to the person who has currently been assigned the least number of minutes.

1. After we have assigned the first m tasks, show that everyone has been assigned at most
opt minutes of work.

2. After we have assigned the first n tasks, show that everyone has been assigned at most
1.5 × opt minutes of work. Hence, the algorithm is a 1.5 approximation.

5
Question 5 (Randomized Algorithm for Independent Set): Let G be an undirected graph
with n nodes and m edges where n ≤ 2m. Recall that an independent set of G is a subset U of
the vertices such that there does not exist an edge whose endpoints are both in U . Consider
the following randomized algorithm for finding an independent set:
n
Step 1. Delete each node (and its incident edges) with probability 1 − p where p = 2m .
Step 2. If there is an edge remaining, delete one of the endpoints (and its incident edges).
Repeat until there are no edges remaining.

Let U be the set of nodes that have not been deleted.

1. Argue that U is an independent set.

2. Let X be the number of nodes that remain after Step 1. What is the value of E [X]?
Justify your answer.

3. Let Y be the number of edges that remain after Step 1. What is the value of E [Y ]?
Justify your answer.

n2
4. Prove that the expected size of U is at least 4m . Hint: Bound |U | in terms of X and Y .

6
 n2
5. Extra Credit: Showing that the expected size of U is at least 4m , implies that every
n2
graph with n nodes and m edges has an independent set of size at least 4m . Why? Can
you use similar reasoning to show that if
 
n r
< 2(2)−1
r

then there exists a way to color the n2 edges of a complete graph on n nodes with

just two colors such that there is no clique of size r where every edge in the clique has
the same color. Hint: Consider coloring the edges randomly and compute the expected
number of cliques of size r where every edge has the same color.

7
8