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) = 9T(n/3) + n + 3011 (1 mark)
√ √
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(lgn), your algorithm must have a worst-case running time of o(nlgn).
3. Give an O(lgn)-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.
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 .
• 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.
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 (x0,y0) ∈ P with (x,y) 6= (x0,y0) for which both x ≤ x0 and y ≤ y0 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)}.
2
