Design and Analysis of Algorithms Assignment 1

COMP3011: Design and Analysis of Algorithms
Assignment 1
1. Give asymptotic upper and lower bounds for T(n) in each of the following recurrences using
Θ-notation. Assume that T(n) is constant for sufficiently small values of n. Justify your answers.
a) T(n) = 9 T(n/3) + n + 3011 (1 mark)
b) T(n) = T(n/2) + 2 T(lg n) + n (2 marks)
c) T(n) = √
n · T(
√
n) + n (2 marks)
2. Consider the following problem:
Input: Two unsorted lists A and B of numbers.
Output: “YES” if some number belongs to both A and B; “NO” otherwise.
Let m be the length of A and let n be the length of B. Design a fast algorithm for the special
case of the problem where m is much smaller than n and analyze its time complexity. When
m = O(lg n), your algorithm must have a worst-case running time of o(n lg n).
Hint: Hashing is not needed here. If you decide to use hashing anyway, you have to explain how to
ensure that the correct answer is found within the allowed time, even in the worst case. (2 marks)
3. Give an O(lg n)-time algorithm for the following problem, justify why it works, and analyze its
time complexity.
Input: A sorted array A[1..n] of distinct integers.
Output: Any index i such that A[i] = i, if such an index exists; −1 otherwise.
For example, if the input is h−2020, −928, −1, 0, 5, 6, 330, 3011i then a valid output is 5. Alternatively, 6 would also be a valid output. (3 marks)
4. In this question, we shall use the definitions below.
• Let G = (V, E) be a graph and let k be a positive integer. A k-coloring of G is a partition
of V into disjoint subsets V1, V2, V3, . . . , Vk called color classes such that for any {x, y} ∈ E,
it holds that x and y belong to different color classes, i.e., x ∈ Vi and y ∈ Vj with i 6= j.
A minimum graph coloring of G is a k-coloring of G for the smallest possible integer k.
• For every positive integer n ≥ 3, define the cycle graph Cn as the graph (Vn, En), where
Vn = {x1, x2, . . . , xn} and En =

{x1, x2}, {x2, x3}, . . . , {xn−1, xn}, {xn, x1}
    
.
• The degree of a vertex x in graph, denoted by deg(x), is the number of neighbors of x.
(Continued −→)
1
The greedy graph coloring algorithm takes as input an undirected graph G = (V, E) and does the
following:
Fix any ordering hv1, v2, . . . , vni of V such that deg(vi) ≥ deg(vi+1) for every i ∈ {1, 2, . . . , n−1}.
for i = 1, 2, . . . , n
Assign vertex vi the smallest color not used by any of its neighbors.
Will applying the greedy graph coloring algorithm to Cn always compute a minimum graph coloring
of Cn when n is an odd integer? If your answer is “yes”, prove it. If your answer is “no”, give a
counterexample. (2 marks)
5. Suppose that P is a sequence of points in the plane. Any point (x, y) ∈ P is called maximal with
respect to P if there is no (x
0
, y0
) ∈ P with (x, y) 6= (x
0
, y0
) for which both x ≤ x
0 and y ≤ y
0 hold.
The set of all points in P that are maximal with respect to P is denoted by M(P). For example,
if P = h(3, 4), (5, 2.5), (1, 5), (4, 4), (2.8, 2)i then M(P) = {(1, 5), (4, 4), (5, 2.5)}.
Describe an O(nm)-time greedy algorithm that takes as input a sequence P of points in the plane
and outputs all points in M(P), where n = |P| and m = |M(P)|, by selecting one point from P
in each iteration and inserting it into the solution. State clearly how a point is selected in each
iteration and how P is updated. Prove the correctness of your algorithm and analyze its time
complexity to make sure it runs in O(nm) time. (3 marks)
2