CPSC 320 Sample Final Examination December 2010
Name: Student ID: Signature:
– You have 2.5 hours to write the 8 questions on this exami- nation. A total of 100 marks are available.
– Justify all of your answers, except if the question says not to.
– No notes or electronic equipment are allowed, except for one 8.5 × 11 sheet of paper, handwritten.
– Keep your answers short. If you run out of space for a question, you have written too much.
– The number in square brackets to the left of the question number indicates the number of marks allocated for that question. Use these to help you determine how much time you should spend on each question.
– Use the back of the pages for your rough work.
–
UNIVERSITY REGULATIONS:
– Each candidate should be prepared to produce, upon request, his/her library card.
– No candidate shall be permitted to enter the examination room after the expiration of one half hour, or to leave during the first half hour of the examination.
– CAUTION: candidates guilty of any of the following, or similar, dishonest practices shall be immediately dismissed from the examination and shall be liable to disciplinary action.
1. Having at the place of writing, or making use of, any books, papers or memoranda, electronic equipment, or other memory aid or communication devices, other than those authorised by the examiners.
2. Speaking or communicating with other candidates.
3. Purposely exposing written papers to the view of other candidates. The plea of accident or forgetfulness shall not be received.
– Candidates must not destroy or mutilate any examination material; must hand in all examination papers; and must not take any examination material from the examination room without permission of the invigilator.
Question
Marks
1
2
3
4
5
6
7
8
Total
[10] 1.
page 2 out of 10
Answer each of the following questions with true or false. Give a short justification for each of your answers.
[5] a. 6n ∈ O(5n)
[5] b. 1.5n + n2 ∈ O(1.5n + n log n)
Short Answers
[3] a. Why is it important to know that a problem is NP-Complete?
[3] b. Explain why the following statement holds: “Finding the median of an un- ordered array is as difficult as finding the ith order statistics of that ar- ray, for an arbitrary i”. Hint: think of the implementations of algorithm RandomizedQuickSelect
[18] 2.
page 3 out of 10 [3] c. What is the main advantage of RandomizedQuickSelect over Select1?
[3] d. The Prim-Jarn ́ık algorithm associates a cost with each vertex that has not yet been added to the tree it constructs. What does this cost represent?
[3] e. Why does the Gale-Shapley (Stable Matching) algorithm discussed in class terminate after at most n2 iterations?
[3] f. When do we use amortized analysis?
[9] 3.
page 4 out of 10
A Computer Science researcher has designed a new data structure called a sheap that supports operations insert, findMinMax and extractMinMax, and decides to use amortized analysis to determine the worst-case running time of a sequence of n operations on an initially empty sheap. She defines a potential function Φ for sheaps, such that Φ(S) ≥ 0 for every sheap S, and such that Φ(S) = 0 if the sheap S is empty. After analyzing the running time of the three operations, she has learned that
• An insert operation on a sheap with n elements takes time log n, and increases the sheap’s potential by 2.
• A findMinMax operation on a sheap with n elements takes time x + √n, where x is the number of elements examined by the operation. The potential of the sheap goes down by x − 1.
• A extractMinMax operation starts by performing a findMinMax operation. The remainder of the extractMinMax operation takes time log n, and decreases the sheap’s potential by 1.
Give as tight a bound as possible on the worst-case running time of a sequence of n operations on an initially empty sheap.
[9] 4.
page 5 out of 10
For each of the following recurrence relations, determine whether or not the Master Theorem discussed in class can be used. If it can be used, apply it to derive the solution of the recurrence relation using O notation. If the Master Theorem can not be used, explain why briefly.
[3]a. T(n)=2T(⌊√n⌋)+n ifn≥2
[3]b. T(n)=9T(n/3)+2n2 1
ifn≥3 if n ≤ 2
1
if n ≤ 1
[3]c. T(n)=4T(⌊n/2⌋)+n2+odd(n) ifn≥2 whereodd(n)=1 ifnisodd 1 ifn≤1 0 ifniseven
[12] 5. Consider the following function:
page 6 out of 10
Algorithm HappyNewYear(A, p, r)
//
// A is an array, p and r are positions in the array.
//
mid ← ⌊ (p+r)/2 ⌋
x ← Christmas(A[p]) + Christmas(A[mid]) + Christmas(A[r]) if (n ≥ 2) then
x ← x + HappyNewYear(A, p+1, r-1) x ← x + HappyNewYear(A, p+1, r-1) x ← x + HappyNewYear(A, p+1, r-1) x ← x + HappyNewYear(A, p+1, r-1)
return x
[4] a. Let C(n) be the number of times that function Christmas will be called during the execution of the call HappyNewYear(A,p,r), where n = r − p + 1. Write a recurrence relation for C(n).
[8] b. Prove using the guess and test method that the solution of the recurrence relation you gave in part (a) is in O(2n).
[10] 6. The Disjoint Sets data structure
a. When we proved that the amortized cost of a find(N) operation is in O(log∗ n), the nodes on the path from N to its root where divided into two types. What were these, and how was the cost of traversing these nodes accounted for?
b. How did we prove that the total infusion of potential into the data structure, which happens when a union operation is performed, did not add more than n log∗ n units of potential?
page 7 out of 10
[15] 7.
page 8 out of 10
The CEO of a software company wants to keep his developers happy by giving them a bonus, but does not want to spend too much money. He thus wants to select as few developers as possible (these will get a bonus, and be happy), chosen so that every other developer likes at least one of those that get a bonus (and hence will be happy for him/her).
The CEO’s problem can be modeled using a graph G = (V,E): each node in the graph is a developer, and an edge (u,v) means that developer u likes developer v. The CEO is looking for a minimum subset W of the set V of vertices, where for every vertex u ∈/ W, there is an edge (u,w) where w ∈ W. This is called a minimum dominating set for the graph G.
[9] a.
Write a greedy algorithm that finds a subset W of V (it does need to be the subset with the fewest elements possible) with that property. Your mark will depend in part on the criterion you use to decide which vertex to add to W. You do not need to give pseudo-code, but you should indicate what data structure you are using to store the vertices that your algorithm has not dealt with yet.
[3] b.
[3] c.
What is the running time of the algorithm you described in part (a)?
The minimum dominating set problem does not satisfy the greedy choice prop- erty. Knowing this, what can you conclude about the algorithm you gave in part (a)?
[17] 8.
page 9 out of 10
Bill and Simon have been arguing about where to have lunch after the CPSC 320 final examination, and decide to solve the decision by playing a sequence of Poker games. The first person to win n games gets to choose where they will have lunch. Simon is a slighly better poker player, and has a 51% chance of winning any individual Poker game.
Let P(i,j) be the probability that Bill will be the first person to win n games, given that he only needs to win another i games (that is, Bill has won n − i games so far), and that Simon only needs to win another j games (that is, she has won n − j games so far). It can be proved that
P (i, j) = 0.49P (i − 1, j) + 0.51P (i, j − 1) (1) Bill is worried about his chances of winning, and asks you to use dynamic program-
ming does.
[3] a.
[3] b.
[3] c.
to compute the probability P(n,n) that he will win n games before Simon State how big a table you need to answer Bill’s question using dynamic pro-
gramming, and the meaning of each entry in the table.
Give one possible order that you can use to compute the entries in the table from part (a).
List all of the base cases that will be needed when you are computing the entries in the table from part (a). That is, list the cases where you can not use equation (1) to compute P (i, j), and the value of P (i, j) for each of them.
page 10 out of 10
[8] d. Write pseudo-code for an algorithm that uses dynamic programming to deter- mine the probability that Bill will win n Poker games before Simon does.