## Description

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