Note: Whenever explanation is requested, the explanation is worth 80% of the points unless otherwise stated.
1. [5 pts] Is the following statement Always True, Never True, or Sometimes True?
“ f(n) + O(f(n)) = Θ(g(n)) for any non-negative functions f and g and positive n”
Please support your answer with an explanation, i.e., a proof or an example.
2. [10 pts] Please rank the following function by increasing order of growth and explain your answer.
3. [5 pts] Please compute the tightest asymptotic bound for f(n, n), where:
f(x, c) = Θ(x) for c ≤ 2
f(c, y) = Θ(y) for c ≤ 2
f(x, y) = Θ(x + y) + f(x2,y2)
Note: You can use any method, as long as it is correct and the derivation of the solution is provided.
4. [20 pts] Chief Eng. Montgomery Scott (aka Scotty) discovers many communication systems from various
spacecraft and satellites that have been left abandoned hundreds of years ago. After days of tinkering, he
found that an essential component in each of these communication systems is an error-correcting code,
which relies on multiplications of polynomials with an extremely high degree.
To test if a systems is working, Scotty would like to verify the polynomial multiplications in the system.
Verifying polynomial multiplications here means that, given three polynomials, he would like to know whether A(x) · B(x) = C(x). He knows that FFT
can verify polynomial multiplications in O(n log(n)).
But, since the polynomial order is often huge, Scotty would like to find a faster algorithm. He is even
willing to relax the requirements of the algorithms, such that it returns the correct answer with high
probability, rather than always returning the correct answer. To help Scotty develop this algorithm, please
answer the following questions:
(a) [5 pts] Describe a randomized algorithm that verifies A(x) · B(x) = C(x) in O(n) time and has the
following properties:
i. If A(x) · B(x) = C(x), the algorithm outputs True.
ii. If A(x)·B(x) , C(x), the algorithm outputs True or False, and the probability that the algorithm
outputs False is at least 1
2
.
(b) [5 pts] Show that the algorithm you developed in (a) indeed satisfies property-i and property-ii
above.
(c) [7 pts] Describe a randomized algorithm to verify A(x) · B(x) = C(x) that will return the correct
answer with probability at least (1−). Please explain how this property is satisfied by the algorithm.
This explanation is worth 50% of the points. Hint: The algorithm in (a) might be useful.
(d) [3 pts] Please derive the asymptotic upper bound of the running-time of the algorithm in (c) in terms
of n and 1
.
Page 1 of 2 – Algorithms – ( COMP3600/6466 )
5. [10 pts] Mr PQ said that he had created extremely efficient Extract-Max and Build-Heap operations for
Max-Heap data structures that rely on comparison operation (i.e., the heap data structure as discussed in
class). In particular, he claimed the following worst time complexity for his algorithms:
• Extract-Max runs in Θ(1) time (Recall: Extract-Max includes retrieving an element from the heap
and fixing the heap) AND
• Build-Heap runs in Θ(n) time
Could Mr PQ’s claim be True? Please explain why or why not.
6. [15 pts] Mr T would like to typeset n words neatly. Suppose each word consists of li (i ∈ [1, · · · , n])
characters and suppose monospaced font (all characters having the same width) is used. Each line can
hold at most C characters, the text is left-aligned, and the words cannot be split between lines. Mr T
knows that the nicest looking paragraph would be one with the minimum extra white space at the end of
each line. When a line consists of word-i to word-j (i, j ∈ [1, n]), the number of extra white space in that
line can be computed as E = C − (
Pj
k=i
lk) − (j − i). Mr T’s goal is to find the typeset that will minimize
the sum of extra white spaces over all lines. Please:
(a) [10 pts] Describe a dynamic programming algorithm for Mr T.
(b) [5 pts] Derive the time complexity of the algorithm you described in (a).
7. [10 pts] Suppose G(V, E,w) is an undirected weighted graph with V being the set of vertices, E being the
set of edges, and w being the weight. Please answer the following questions:
(a) [5 pts] Suppose T is a Minimum Spanning Tree of G. Is it True that any path in T between any
pairs of vertices v, v
0 ∈ V must be the shortest path in G? Please provide a proof if it is True and a
counter-example otherwise.
(b) [5 pts] Will the following pseudo-code returns the Minimum Spanning Tree of G? If the answer is
yes, please provide a proof. Otherwise, please provide a counter-example.
Algorithm 1 Algorithm-1(G(V, E,w))
1: T = ∅
2: for each edge e ∈ E, taken in arbitrary order do
3: if T ∪ e has no cycles then
4: T = T ∪ e
5: Return T
8. [5 pts] Consider a hash table T with m slots. Suppose T contains a single element, and this element has
key k. Ms Search has been searching for r keys that are different from k in hash table T. Assuming
T uses simple uniform hashing, is r
m
the probability that at least one of the r searches collide with the
slot containing key k? If this probability is correct, please provide a derivation to support it. Otherwise,
please provide the new probability and its derivation.
oOo That’s All Folks oOo
Page 2 of 2 – Algorithms – ( COMP3600/6466 )