Time: 2hours 30mins
CS PhD Qualifying Exam
CODE: ……………………………………………………….. Grade: 1: … 2: … 3: … 4: … 5: … Total: …….
Solve all 5 (FIVE) problems in the exam books/sheets provided
Note: Be concise in describing your algorithms. If you use a known algorithm, then you can use it as a black-box (subroutine) without going into details of how that known algorithm works. Avoid useless ramblings about known algorithms, as that will be viewed negatively!
Definition (Little oh): For functions f(n),g(n), we say f(n) is o(g(n)), if and only if: lim f(n) = 0.
n→∞ g(n)
For example, logn is o(n), but n/2 is not o(n). Sometimes we say f(n) is asymptotically smaller than
g(n).
Definition (log base two): We define lg n to be the logarithm base two of n. For example, lg 2 is one,
and lg8 is 3.
Definition (Stirling’s approximation formula): For n factorial denoted by n!, the following approxi- mation can be used in this exam without proof: n! = (n/e)n, where e = 2.7182 . . ., and thus the following can then be derived: lg (n!) = n lg n − 1.44n.
Data Structures and Algorithms
Problem 1. (20 points)
You may assume that n lg n and n2 are both integer in this problem. You are given two sorted sequences stored in arrays A and B of nlgn and n2 keys respectively. We are interested in forming the union C = A∪B, i.e. an array C containing one copy of all the keys of A and B. Give a space and time efficient algorithm for solving this problem. (Time efficient means its running time cannot be asymptotically improved upon; space efficient means likewise for space requirements.) Justify your arguments.
Problem 2. (20 points)
We have two types of scales to weigh coins.
(1) A balance scale. One coin can be put on one side and another on the other side and the scale will tell us whether the two sides weigh the same or which side weighs more (or less) by pointing out the lightest coin. Thus if we have two coins a, b on either side, a function LIGHTEST(a,b) returns the coin that is lighter (i.e. a or b) or −1 if both weigh the same.
(2) A triple side scale. Such a scale also accepts only one coin on each side and points to the side of the MEDIAN(a,b,c). That is if three coins a,b,c are placed one per side, and they are a < b < c, MEDIAN(a,b,c) will return b, i.e. the scale will point towards b.
From now on we call a scale by its function: LIGHTEST and MEDIAN. We have n coins c1,...,cn all with different weights.
(a) Give a short argument that one cannot use just the MEDIAN scale to distinguish between the lightest and heaviest of n > 1 coins; however the LIGHTEST scale can do so.
(b) If you know the lighest coin L (i.e. the index l such that cl = L), show how you can determine for two arbitrary coins a and b (other than L) which one is lighter by using only MEDIAN and not LIGHTEST. (c) For the n coins c1, . . . , cn use o(n lg n) calls to MEDIAN to determine the lightest and heaviest coins L and H. Your algorithm need only return the L and H; it does not need to clearly identify which of
the two is the lightest and which one is the heaviest.
Problem 3. (20 points)
You are given two Binary Search Trees T1, T2 with n1 and n2 keys respectively, where n = n1 + n2. Build a balanced binary search T of the n keys of T1,T2 in worst-case linear time. Prove your claims. (You may create an AVL or red-black tree, or just a regular binary search tree that is balanced.)
Problem 4. (20 points) √
Given two sequences of numbers X = ⟨x1,…,xn⟩ and Y = ⟨y1,…,yn⟩ he must find the m ≤
values of the sums xi + yj , 1 ≤ i, j ≤ n in SORTED ORDER (smallest to largest). One may assume that m ≤ √n but one must not assume that m is a constant. The proposed algorithm should have worst-case running time that is o(n lg n).
Example. If X = ⟨−2,−3,−1,0,100,290,300,4⟩ and Y = ⟨−200,−189,−18,−100,11,1,10,−7⟩ and m = 3 then the answer is ⟨301, 310, 311⟩. Note that 301 can result either as the sum of 290 + 11 or 300+1.
The fifth problem is on the following page
n largest
Problem 5. (20 points)
We have a directed graph G = (V, E) enhanced with weight values on its edges i.e. G = (V, E, w). For an edge (i, j) ∈ E, the weight w(i, j) is a real number greater than 0 and less than 1.
For a given source vertex s we want to determine B(s, u) where B(s, u) is the maximum product-weight of any path from s to u. Thus we want to maximize tj=1 w(vj−1,vj) for every path v0 = s,v1,…,vt−1,vt = u from s to every u other than s. Give an algorithm that solves this problem and analyze its worst-case running time.