CS570
Analysis of Algorithms
Fall 2009
Exam II
Name: _____________________
Student ID: _________________
____Monday ____Friday 2-5 ____Friday 5-8 ____DEN
Maximum Received
Problem 1 20
Problem 2 20
Problem 3 20
Problem 4 20
Problem 5 20
Total 100
2 hr exam
Close book and notes
No calculator allowed
If a description of an algorithm is required, please limit your
description within 200 words, anything beyond 200 words will not be
considered. Proof/justification or complexity analysis will be considered
only if the algorithm is either correct or provided by the problem.
https://www.coursehero.com/file/8199443/Fall-2009-Exam2/
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/8199443/Fall-2009-Exam2/
1) 20 pts
Mark the following statements as TRUE or FALSE. No need to provide any
justification.
FALSE
If in a flow network all edge capacities are distinct, then there exists a unique min-cut.
FALSE
The Knapsack Problem describe in the textbook (0-1 Knapsack Problem) can be
solved in a running time that is a polynomial time with respect to the input size, i.e.
the number of objects (n).
TRUE
If a problem can be solved by dynamic programming, then it can always be solved by
exhaustive search.
TRUE
Given a graph G(V, E) and its residual graph Gf(V’, E’), then |V|=|V’| and 2|E|>=|E’|
FALSE
The Ford-Fulkerson Algorithm terminates when the source s is not reachable from the
sink t in the residual graph Gf.
FALSE
If you have non integer edge capacities, then you cannot have an integer max flow.
FALSE
If f is a maximum s-t flow in G, where s is the source and t is the sink, then for all
edges e out of s, we have f(e) = ce.
TRUE
If the edge costs are all even, then the max flow (min cut) is also even.
FALSE
If the edge costs are all odd, then the max flow (min cut) is also odd.
FALSE
If a problem can be solved using both the greedy method and dynamic programming,
greedy will always give you a lower time complexity.
https://www.coursehero.com/file/8199443/Fall-2009-Exam2/
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/8199443/Fall-2009-Exam2/
2) Total 20 pts
You are given an integer sequence with n integers, and no two of the n integers are
equal. And we assume any two integers in the sequence can be compared within
constant time.
(a) (10 pts) Give an 2( )O n algorithm to decide the length of the longest increasing
subsequence, and analyze the running time but no need to prove the correctness.
For example, the original sequence is {4, 2, 3, 6, 1, 9, 15, 10, 8, 11}, the longest
increasing subsequence is {2, 3, 6, 9, 10, 11} with length 6, so 6 is the answer
needed here.
We can use the solution for Longest Common Subsequence (LCS) here. We sort the
sequence in increasing order in ( log )O n n time and then do a LCS algorithm on the
original and the sorted sequences, and we get the result. So in total 2( )O n time.
Refer to the review session slides for details about the LCS algorithm.
Here we introduce another algorithm to solve this problem. Denote Opt(i) as the
optimal result (the maximum length) of the first i elements with i-th element chosen
in the subsequence (it may not be the optimal result for the first i-th element without
this constraint). Then we have
and ( ) ( )
( ) 1 max { ( )}, 1
j i num j num i
Opt i Opt j i
< < = + >
and we initialize Opt(1) as 1.
By solving forward, we get all the Opt(i). Just check all the i for the largest Opt(i)
and it would be the result. Time complexity is also 2( )O n since we solve each the n
Opt’s once and every time look at ( )O n Opt’s.
https://www.coursehero.com/file/8199443/Fall-2009-Exam2/
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/8199443/Fall-2009-Exam2/
(b) (10 pts) Give an 2( )O n approach to output a longest increasing subsequence. If
there are multiple choices you can output any one of them. Analyze the running time
but no need to prove the correctness.
Based on (a), we just add a pointer prev(i) to denote the j chosen in the step we
calculated Opt(i). Then after we find the largest Opt(i), we do a backward trace
to find the j=prev(i) so the previous number is num(j). And then we find prev(j),
and so on. Then we output them in forward order.
https://www.coursehero.com/file/8199443/Fall-2009-Exam2/
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/8199443/Fall-2009-Exam2/
3) 20 points
Given a sequence of numbers a1,…,an, we would like to select a subset S of {1,…,n} so that 𝑎𝑖𝑖∈𝑆
is maximized, subject to the constraint that for all i, if 𝑖 ∈ 𝑆 then i+1 ∉ S and i – 1 ∉ S. Give an O(n)
algorithm to solve this problem. Justify your algorithm and analyze its running time.
Solution:
Observation: the following constraints are equivalent:
∀𝑖, if 𝑖 ∈ S, then 𝑖 − 1 ∉ S and 𝑖 + 1 ∉ S ⇔ ∀𝑖, if 𝑖 ∈ S, then 𝑖 − 1 ∉ S
Let 𝑓0 𝑖 = max 𝑎𝑖 where 𝑆 ⊂ 1, 2, … , 𝑖 satisfies the above constraint and 𝑖∈S 𝑖 ∉ S.
Let 𝑓1 𝑖 = max 𝑎𝑖 where 𝑆 ⊂ 1, 2, … , 𝑖 satisfies the above constraint and 𝑖∈S 𝑖 ∈ S.
Let 𝑂𝑃𝑇 𝑖 = max 𝑎𝑖 where 𝑆 ⊂ 1, 2, … , 𝑖 satisfies the above constraint 𝑖∈S .
Clearly, f0(1) = 0 and f1(1) = a1 and OPT(1) = max (f0(1), f1(1)).
We have the following relations for 2 ≤ 𝑖 ≤ n,
𝑓0 𝑖 = 𝑂𝑃𝑇(𝑖 − 1)
𝑓1 𝑖 = 𝑎𝑖 + 𝑂𝑃𝑇(𝑖 − 2)
𝑂𝑃𝑇 𝑖 = max 𝑓0 𝑖 ,𝑓1 𝑖 = max(𝑂𝑃𝑇 𝑖 − 1 , 𝑎𝑖 + 𝑂𝑃𝑇(𝑖 − 2))
We can compute the values of f0, f1 and OPT(i) iteratively from 2 to n.
OPT(n) is the optimal 𝑎𝑖𝑖∈𝑆 .
Calculating each OPT(i) takes O(1). Thus, the running time of the algorithm is O(n).
https://www.coursehero.com/file/8199443/Fall-2009-Exam2/
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/8199443/Fall-2009-Exam2/
4) 20 points
Someone, say X, has two children who, unfortunately, dislike each other. The problem is so severe
that not only do they refuse to walk to school together, but in fact each one refuses to walk on any
street block (a street block is the portion of the street on one city block) that the other child has
stepped on that day. The children have no problem with their paths crossing at an intersection.
Fortunately both the X’s house and the school are on intersections, but beyond that he/she is not sure
if it is going to be possible to send both of his/her children to the same school. X has a map of his/her
town. Show how to formulate the problem of determining if both his/her children can go to the same
school as a maximum-flow problem.
Solution:
Create a vertex for each intersection, and if there is a street block between intersections u and v,
create directed edges (u, v) and (v, u). Set the capacity of each edge to 1. Let the source be the
intersection on which the X’s house sits, and let the sink be the intersection on which the school is
located. To solve the problem is to find a flow of value 2 that also has the property that f (u, v) is an
integer for all vertices u and v. Such a flow represents two edge-disjoint paths from the house to the
school.
https://www.coursehero.com/file/8199443/Fall-2009-Exam2/
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/8199443/Fall-2009-Exam2/
5) 20 points
The edge connectivity of an undirected graph is the minimum number k of edges that must be
removed to disconnect the graph. For example, the edge connectivity of a tree is 1, and the edge
connectivity of a cyclic chain of vertices is 2. Show how the edge connectivity of an undirected
graph G = (V, E) can be determined by running a maximum-flow algorithm on at most |V| flow
networks, each having O(|V|) vertices and O(|E|) edges.
Solution:
For any two vertices u and v in G, you can define a flow network Guv consisting of the directed
version of G with all edge capacities set to 1, s = u, and t = v. (Guv has O(|V|) vertices and O(|E|)
edges, as required. We want all capacities to be 1 so that the number of edges crossing a cut equals
the capacity of the cut.) Let fuv denote a maximum flow in Guv.
We claim that for any u ∈ V, the edge connectivity k equals min𝑣∈V−{u} |𝑓𝑢𝑣 |. We will show below
that this claim holds. Assuming that it holds, we can find k as follows:
EDGE-CONNECTIVITY(G)
select any vertex u ∈ V
for each vertex v ∈ 𝑉 − {𝑢}
do set up the flow network Guv as described above
find the maximum flow fuv on Guv
return the minimum of the | 𝑉 − 1 max-flow values: min𝑣∈V−{u} |𝑓𝑢𝑣 |
The claim follows from the max-flow min-cut theorem and how we choose capacities so that the
capacity of a cut is the number of edges crossing it. We prove that for any 𝑢 ∈ V,
𝑘 = min𝑣∈V−{u} |𝑓𝑢𝑣 | by showing separately that k is at least this minimum and that k is at most this
minimum.
1) Proof that 𝑘 ≥ min𝑣∈V−{u} |𝑓𝑢𝑣 |:
Let 𝑚 = min𝑣∈V−{u} |𝑓𝑢𝑣 |. Suppose we remove only 𝑚 − 1 edges from G. For any vertex v, by
max-flow min-cut theorem, u and v are still connected. (The max flow from u to v is at least m,
hence any cut separating u from v has capacity at least m, which means at least m edges cross any
such cut. Thus at least one edge is left crossing the cut when we remove 𝑚 − 1 edges.) Thus
every node is connected to u, which implies that the graph is still connected. So at least m edges
must be removed to disconnect the graph, i.e., 𝑘 ≥ min𝑣∈V−{u} |𝑓𝑢𝑣 |.
2) Proof that 𝑘 ≤ min𝑣∈V−{u} |𝑓𝑢𝑣 |:
Consider a vertex v with the minimum |𝑓𝑢𝑣 |. By the max-flow min-cut theorem, these is a cut of
capacity |𝑓𝑢𝑣 | separating u and v. Since all edge capacities are 1, exactly |𝑓𝑢𝑣 | edges cross this
cut. If these edges are removed, these is no path from u to v, and so our graph becomes
disconnected. Hence, 𝑘 ≤ min𝑣∈V−{u} |𝑓𝑢𝑣 |.
Concluding 1) and 2), the claim that 𝑘 = min𝑣∈V−{u} |𝑓𝑢𝑣 |, for any 𝑢 ∈V is true.
https://www.coursehero.com/file/8199443/Fall-2009-Exam2/
Th
is
stu
dy
re
so
ur
ce
w
as
sh
ar
ed
v
ia
C
ou
rs
eH
er
o.
co
m
Powered by TCPDF (www.tcpdf.org)
https://www.coursehero.com/file/8199443/Fall-2009-Exam2/
http://www.tcpdf.org