Algorithm Analysis Final Exam
CSI 3108-01, Fall 2020 Due at 3:00pm, Friday, December 18
This problem set consists of four written problems. The point breakdown is
as follows:
1 = 2 points
2 = 12 points
3 = 26 points (3a = 18, 3b = 8)
4 = 20 points
You are not allowed to collaborate with anyone on this problem set. Read
the final exam instructions posted on YSCEC.
When a problem asks you to design an algorithm, you must present a full
description of the algorithm, an analysis of its running time, and a proof of
its correctness, unless the problem says that you are allowed to skip one of
those parts. Your algorithm must be efficient unless the problem specifies
otherwise.
If you solve a problem by reducing to an algorithm from the textbook (ex-
cluding exercises) or lectures, then you do not need to re-derive the running
time or proof of correctness for the algorithm you are reducing to. However,
you must say which algorithm you are reducing to, and you must correctly
account for that algorithm’s running time when determining the overall run-
ning time of your own algorithm. You must also prove that your reduction
is correct, under the assumption that the algorithm you are reducing to is
correct.
You are also allowed to quote any theorem from the textbook (again, ex-
cluding exercises) or lectures, without re-deriving the proof of that theorem.
This, in particular, includes the NP-completeness of various problems from
the textbook (excluding exercises) or lectures.
If any corrections need to be made, we will post them on YSCEC. Regularly
check the course page on YSCEC.
Write your solution in English.
Good luck, and have a nice winter break!
한 학기 동안 수고 많으셨습니다.
(1) (2 points) Let f be a function defined on the nonnegative integers. We have f(0) =
f(1) = 1 and, for all n ≥ 2, f(n) = 2f(⌊n/2⌋) + f(⌈n/2⌉) + n⌊√n⌋. What is the asymp-
totic growth of f? Use big-theta notation. You do not need to provide any justification
for your answer.
(2) (12 points) Design an algorithm that, given a number k and a digraph G = (V,E)
where each edge e has an associated color ce ∈ Z, determines if there exists a subset of
edges F ⊆ E that satisifies the following properties.
• The number of edges |F | is at least k.
• The colors of the edges in F are distinct.
• For all vertex v ∈ V , at most one edge in F is incident from v.
For this problem, you do not need to prove the correctness of your algorithm; just present
a full description of your algorithm and analyze its running time. Your algorithm must
be efficient.
Example 1. Consider an instance defined by k = 3, V := {p, q, r, s, t, u}, E := {〈p, q〉,
〈r, s〉, 〈t, u〉} and edge colors c〈p,q〉 = 1, c〈r,s〉 = 1, c〈t,u〉 = 2. The answer is no because, in
order to satisfy |F | ≥ k, we must include all three edges in F , but then F would have
two edges of the same color, namely 〈p, q〉 and 〈r, s〉. If we modify the instance so that
k = 2, the correct answer is yes.
Example 2. Consider an instance defined by k = 1, V := {p, q, r}, E := {〈p, q〉, 〈p, r〉}
and edge colors c〈p,q〉 = 1, c〈p,r〉 = 2. The answer is yes because F = {〈p, q〉} satisifies the
given conditions. If we modify the instance so that k = 2, the answer is no.
(3) (26 points)
(3a) (18 points) Consider the following game. Let Z≥0 be the set of all nonnegative
integers.
We have n cards, each of which has a tuple written on it. Let (mi, ai) ∈ Z≥0×Z≥0 denote
the tuple on the i-th card. The goal of this game is to achieve as large score as possible.
We begin with the initial score of 0 points. A card with a tuple (m, a) can be played only
when the current score is at least m. When it is played, a is added to the current score.
Once we play a card, the card cannot be played again. The cards can be played in any
order, and we do not need to play all cards.
Design an algorithm that, given n and the tuples (m1, a1), · · · , (mn, an) written on the n
cards, determines the largest score we can achieve by playing some or all of these cards.
You need to also prove the correctness of your algorithm and analyze its running time.
Example. Consider an instance defined by n = 3, (m1, a1) = (99, 99), (m2, a2) = (2, 5),
and (m3, a3) = (0, 3). The correct answer is 8: you can achieve 8 points by playing the
third card and then the second.
(3b) (8 points) Now we revise the rule of the game slightly as follows: when a card with
a tuple (m, a) is played,
• if a > 0, a is added to the current score;
• if a = 0, the current score is doubled.
All other rules remain the same.
Design an algorithm that, given n and the tuples (m1, a1), · · · , (mn, an) written on the n
cards, determines the largest score we can achieve by playing some or all of these cards.
For this problem, you do not need to prove the correctness of your algorithm; just present
a full description of your algorithm and analyze its running time.
Your grade for this problem will depend on the asymptotic running time of your algorithm,
unlike other problems where you only need to give an efficient algorithm. Try to give an
asymptotically fast algorithm, and carefully analyze its running time.
Example. Consider an instance defined by n = 3, (m1, a1) = (0, 0) and (m2, a2) = (0, 1),
and (m3, a3) = (2, 1). The correct answer is 3: you can achieve 3 points by playing the
second card, the first card, and the third card in that order.
(4) (20 points) Given a finite set U , consider a collection of subsets of U . This collection
is initialized to be the collection of the |U | singletons, {{u} | u ∈ U}: for example, if
U = {a, b, c}, the initial collection is {{a}, {b}, {c}}.
An evolution is the following operation that can be performed on a collection: we pick two
subsets from the collection, take their union, and add it to the collection. We can choose
which two subsets to pick from the collection, but each time an evolution is performed,
we choose only two subsets.
Consider the following problem.
Problem 1 (Evolving Collection). Given a finite set U , a number k > 0, and a list
S1, . . . , Sm ⊆ U of m subsets of U , can we perform at most k evolutions, starting from
the collection of the singletons, so that all of S1, . . . , Sm are in the collection at the end?
For each evolution, we are free to choose the two subsets to pick from the collection.
Prove that Evolving Collection is NP-complete.
Example. Consider an instance defined by k = 4, U := {a, b, c, d},m = 3, S1 := {a, b, c},
S2 := {a, b, d}, and S3 := {a, b, c, d}. The answer is yes. The collection initially contains
four singletons:
{{a}, {b}, {c}, {d}}.
We perform the first evolution by picking {a} and {b}. Then the collection becomes:
{{a}, {b}, {c}, {d}, {a, b}}.
We then perform the second evolution by picking {c} and {a, b}. The collection becomes:
{{a}, {b}, {c}, {d}, {a, b}, {a, b, c}}.
Now we pick {d} and {a, b} to perform the third evolution, which yields
{{a}, {b}, {c}, {d}, {a, b}, {a, b, c}, {a, b, d}}.
Finally, we perform the fourth evolution by picking {d} and {a, b, c}. The collection
becomes:
{{a}, {b}, {c}, {d}, {a, b}, {a, b, c}, {a, b, d}, {a, b, c, d}}.
Note that, after performing these four evolutions, the collection contains all S1 = {a, b, c},
S2 = {a, b, d}, and S3 = {a, b, c, d}. Recall that k = 4. The correct answer is therefore
yes.
If we modify the instance so that k = 3, the answer is no because whichever two sets we
may choose for at most three evolution operations, we cannot make all S1, S2, and S3
included in the collection.

欢迎咨询51作业君