Design and Analysis of Algorithms Assignment 3

COMP3011: Design and Analysis of Algorithms
Assignment 3

1. Suppose randomized Quicksort is applied to an array A[1..n] of distinct numbers, where n ≥ 4.
a) What is the probability that the algorithm will compare the smallest number in A and the largest
number in A to each other at least once during its execution? Justify your answer. (1 mark)
b) What is the probability that the algorithm will compare the second smallest number in A and
the third smallest number in A to each other at least once during its execution? Justify your
answer. (1 mark)
2. In this question, we shall use the following definitions. Let G = (V, E) be a graph and let k be a
positive integer. A relaxed k-coloring of G is any partition of V into disjoint subsets V1, V2, . . . , Vk.
In a relaxed k-coloring of G, if x belongs to Vi then x is said to have the color i. Note that in
contrast to the other graph colorings we have seen earlier in the course, a relaxed k-coloring of G
allows two vertices that are connected by an edge to have the same color.
An edge {x, y} in E is called a good edge if x and y have different colors. Consider the following
maximization problem:
Input: An undirected graph G = (V, E).
Output: A relaxed 4-coloring of G with as many good edges as possible.
Prove that for any instance of this problem, if each vertex in V is assigned to one of V1, V2, V3, V4
chosen uniformly at random and independently of all other vertices, then the expected number of
good edges is at least 3
4
times the number of good edges in an optimal solution. (2 marks)
3. Do a literature search to find a published conference paper or journal article that uses the potential
method to analyze the time complexity of an algorithm, and summarize the result. In your answer
to this question, write the following:
• Bibliographic information (the names of the authors, the title of the paper/article, the conference or journal name, the volume and page numbers, and the year of publication).
• A short description of the problem considered and the result of the analysis.
• The definition of the potential function used.
The analysis that you choose should not be described in the textbook or the tutorials. You do not
need to include any calculations or technical details of the algorithm in your answer. (3 marks)
(Continued −→)
1
4. Two strings S1 and S2 are anagrams if S2 can be obtained by rearranging the characters of S1.
For example, LEMON and MELON are anagrams. Design a fast algorithm for the following problem
and analyze its time complexity.
Input: A string T and a string P, both over the alphabet {A, B, C, . . . , Z}.
Output: The set of shifts in T at which P or an anagram of P occurs, i.e., every integer
s ∈ {0, 1, . . . , |T| − |P|} such that T[(s + 1)..(s + |P|)] = P or T[(s + 1)..(s + |P|)] is an anagram
of P.
For example, if the input is T = LIMESANDLEMONS and P = MELON then the output is {8} because
T[9..13] is an anagram of P. To get full marks, the worst-case running time of your solution must
be O(|T| + |P|). (3 marks)
5. Describe an efficient algorithm for the following problem.
Input: Two strings T and P, where T contains no “?”-symbols and P contains exactly one
“?”-symbol.
Output: “YES” if there exists an integer s such that for each i ∈ {1, 2, . . . , |P|}, either P[i] =
T[s + i] or P[i] = “?” holds; “NO” otherwise.
For example, if T = STRENGTH and P = R?NG then the output should be “YES”, but if T =
STRENGTH and P = R?G then the output should be “NO”. You may use the linear-time algorithm
for the Exact String Matching Problem from the lectures as a procedure (you do not need to give
its pseudocode here).
Also, analyze the time complexity of your algorithm. To get full marks, its worst-case running
time must be O(|T| + |P|). (3 marks)
6. The efficient version of the rooted-trees representation of disjoint sets from Lecture 9 incorporates
a path compression heuristic in the procedure Find-Set. The procedure is defined as:
Rewrite the pseudocode so that the procedure does not use recursion. After running your modified
procedure, the x.p-values should have the same values as if the recursive Find-Set above had been
used. (2 marks)
2