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.
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.
(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.
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.
2
