CS570
Analysis of Algorithms
Spring 2008
Final Exam (B)
Name: _____________________
Student ID: _________________
Section:__2:00-5:00 or __5:00-8:00
Maximum Received
Problem 1 20
Problem 2 15
Problem 3 15
Problem 4 20
Problem 5 10
Problem 6 20
Total 100
Note: The exam is closed book closed notes.
https://www.coursehero.com/file/8199447/Spring-2008-Final-B/
Th
is
stu
dy
re
so
ur
ce
w
as
sh
ar
ed
v
ia
C
ou
rs
eH
er
o.
co
m
https://www.coursehero.com/file/8199447/Spring-2008-Final-B/
1) 20 pts
Mark the following statements as TRUE, FALSE, or UNKNOWN. No need to
provide any justification.
[ TRUE/FALSE ]FALSE
In a flow network whose edges have capacity 1, the maximum flow always
corresponds to the maximum degree of a vertex in the network.
[ TRUE/FALSE ]FALSE
If all edge capacities of a flow network are unique, then the min cut is also unique.
[ TRUE/FALSE ]TRUE
A minimum weight edge in a graph G must be in one minimum spanning tree of G.
[ TRUE/FALSE ]TRUE
When the size of the input grows, any polynomial algorithm will eventually become
more efficient than any exponential one.
[ TRUE/FALSE/UNKNOWN ]FALSE
NP is the class of problems that are not solvable in polynomial time.
[ TRUE/FALSE/UNKNOWN ]FALSE
If a problem is not solvable in polynomial time, it is in the NP-Complete class.
[ TRUE/FALSE/UNKNOWN ]TRUE
Linear programming can be solved in polynomial time.
[ TRUE/FALSE ] FALSE
10
2 log 4n+3
+ 9
2 log 3n+21
is O(n).
[ TRUE/FALSE ]FALSE
f(n) = O(g(n)) implies g(n) = O(f(n)).
[ TRUE/FALSE ]FALSE
If X can be reduced in polynomial time to Y and Z can be reduced in polynomial time
to Y , then X can be reduced in polynomial time to Z.
https://www.coursehero.com/file/8199447/Spring-2008-Final-B/
Th
is
stu
dy
re
so
ur
ce
w
as
sh
ar
ed
v
ia
C
ou
rs
eH
er
o.
co
m
https://www.coursehero.com/file/8199447/Spring-2008-Final-B/
2) 15 pts
Suppose you are given a number x and an array A with n entries, each being a distinct
number. Also it is known that the sequence of values A[1],A[2], …,A[n] is unimodal.
In other words for some unknown index p between 1 and n, we have
A[1] < ...
the array).
Give a algorithm with running time O(log n) to determine if x belongs to A, if yes the
algorithm should return the index j such that A[j] = x. You should justify both the
correctness of your algorithm and the running time.
Solution:
The idea is to first find out p and then break A into two separated sorted arrays, then use
binary search on these two arrays to check if x is belong to A.
Let FindPeak() be the function of finding the peak in A . Then FindPeak(A [1 : n ]) works
as follows:
Look at A [n / 2], there are 3 cases:
(1) If A [n / 2 – 1] < A [n / 2] < A [n / 2] + 1, then the peak must come strictly after n / 2. Run FindPeak(A [n / 2 : n ]). (2) If A [n / 2 - 1] > A [n / 2] > A [n / 2] + 1, then the peak must come strictly before n /
2. Run FindPeak(A [1 : n / 2]).
(3) If A [n / 2 – 1] < A [n / 2] > A [n / 2] + 1, then the peak is A [n / 2], return n/2.
Now we know the peak index(p value). Then we can run binary search on A [1 : p ] and
A [p +1 : n ] to see if x belong to them because they are both sorted.
In the procedure of finding p, we halve the size of the array in each recurrence. The
running time T(n) satisfies T (n ) = T (n/2) + O(1) . Thus T (n) = O (log n). Also both
binary search has running time at most O (log n), so total running time is O (log n ).
https://www.coursehero.com/file/8199447/Spring-2008-Final-B/
Th
is
stu
dy
re
so
ur
ce
w
as
sh
ar
ed
v
ia
C
ou
rs
eH
er
o.
co
m
https://www.coursehero.com/file/8199447/Spring-2008-Final-B/
3) 15 pts
You are given two sequences a[1],…,a[m] and b[1],…,b[n]. You need to find their
longest common subsequence; that is, find a subsequence a[i1], …, a[ik] and
b[j1],…,b[jk], such that a[i1] = b[j1], …, a[ik] = b[jk] with k as large as possible. You
need to show the running time of your algorithm.
Solutions:
We use dynamic programming to solve this problem.
Notation X(i)= the prefix sequence
Let Z be a LCS of X and Y, |Z|=k.
If the last character of X and Y are different, Z is a LCS of either X(m-1) and Y(n) or
X(m) and Y(n-1).
If the last character of X and Y are the same, Z(k-1) is a LCS of X(m-1) and Y(n-1)
State Transition Equation:
The largest k is OPT(m, n).
Since computing each OPT(i, j) costs O(1), the running time is O(mn).
)()(
)()(
)}1,(),,1(max{
1)1,1(
),(
jyix
jyix
if
if
jiOPTjiOPT
jiOPT
jiOPT
https://www.coursehero.com/file/8199447/Spring-2008-Final-B/
Th
is
stu
dy
re
so
ur
ce
w
as
sh
ar
ed
v
ia
C
ou
rs
eH
er
o.
co
m
https://www.coursehero.com/file/8199447/Spring-2008-Final-B/
4) 20 pts
In Linear Programming, variables are allowed to be real numbers. Consider that you
are restricting variables to be only integers, keeping everything else the same. This is
called Integer Programming. Integer Programming is nothing but a Linear
Programming with the added constraint that variables be integers. Prove that integer
programming is NP-Hard
Solutions:
Proof by reduction from Satisfiability
Any SAT instance has boolean variables and clauses. Our Integer Programming problem
will have twice as many variables, one for each variable and its compliment, as well as
the following inequalities:
0 vi 1 and 0
vi 1
1 vi +
vi 1
for each clause C = {v1,
v2, … vi} : v1+
v2+…+ vi 1
1. Any SAT problem has a solution in IP.
In any SAT solution, a TRUE literal corresponds to a 1 in IP since, if the expression is
SATISFIED, at least one literal per clause is TRUE, so the inequality sum is > 1.
2. Any IP solution gives a SAT solution.
Given a solution to this IP instance, all variables will be 0 or 1. Set the literals
corresponding to 1 as TRUE and 0 as FALSE. No boolean variable and its complement
will both be true, so it is a legal assignment with also must satisfy the clauses.
Concluding 1 and 2, Satisfiability