CPSC 320 Tutorial: Initial Sample Problems

1. Give and briefly justify good Θ bounds on the worst-case running time of each of these
pseudocode snippets sometimes dealing with an array A[1 . . . n] of length n.
(a) Repeated division
Function mystery1(n)
count ← 0
while n > 0:
count ← count + 1
n ← floor(n/2)
return count
This functions runs in Θ(log n) time, because the maximum number of times we can
divide n by 2 using integer division before reaching 1 is log2 n (the solution to the
equation 2x = n). One more iteration will lead to the terminating condition.
(b) Repeated squaring
Function mystery2(n)
i ← 2
count ← 0
while i < n:
count ← count + 1
i ← i * i
return count
x
If the loop iterates x times, then the final value of i is 22 , because i takes on the values
2, 22 , (22 )2 = 24 , (24 )2 = 28 , and so on. This means x ≈ log2 (log2 n). Thus the function
runs in Θ(log log n) time.

2. Show that there are instances of the Stable Matching problem with n employers and n co-op
students for which an exponential number of valid solutions exist. Hint: there is a straight-
forward construction with 2n/2 different valid solutions. The best lower bound known so far
(which we are NOT asking you to replicate) has approximately 2.28n valid solutions [1].
We construct an instance with 2n/2 different valid solutions for every even integer n as follows:
• Employers 1 and 2 have students 1 and 2 as their two top choices, in this order. Students
1 and 2 have employers 1 and 2 as their two top choices, in the opposite order. These
two employers and two students rank all other students/employers lower. That is, their
preference lists look like:
e1 : s1 , s2 , all other students
e2 : s2 , s1 , all other students
s1 : e2 , e1 , all other employers
s2 : e1 , e2 , all other employers
• Employers 3 and 4 have students 3 and 4 as their two top choices, in this order. Students
3 and 4 have employers 3 and 4 as their two top choices, in the opposite order. These
two employers and two students rank all other students/employers lower. That is, their
preference lists look like:
e3 : s3 , s4 , all other students
e4 : s4 , s3 , all other students
s3 : e4 , e3 , all other employers
s4 :Thisework
3 , e4is, licensed
all other employers
under a Creative Commons Attribution 4.0 International License. cb
For license purposes, the author is the University of British Columbia.
 • And so on for employers/students 5 and 6, for employers/students 7 and 8 up to employ-
ers/students n − 1 and n.

In every stable solution, we will either pair e1 with s1 and e2 with s2 (making both employers
happy), or we will pair e1 with s2 and e2 with s1 (making both students happy).
Similarly, we will either pair e3 with s3 and e4 with s4 (making both employers happy), or we
will pair e3 with s4 and e4 with s3 (making both students happy).
The same holds for employers/students 5 and 6, for employers/students 7 and 8 up to em-
ployers/students n − 1 and n. A valid solution will have one of two pairings for employ-
ers/students 1 and 2, one of two pairings for employers/students 3 and 4, etc. So there are
exactly 2 × 2 × · · · × 2 = 2n/2 valid solutions.

3. Finally, here is a fun problem that has nothing to do with Stable Matching. The evil king
Yéméchan has a cellar containing n bottles of expensive wine, and his guards have just caught
a spy working for the neighbouring king Yépamieu trying to poison Yéméchan’s wine. For-
tunately the spy only had time to poison one wine bottle. Unfortunately, the guards didn’t
see which one. To make matters worse, the poison the spy used was very deadly: one drop
diluted even a billion to one will suffice to kill someone. Even so, the poison takes a month
to kill that person. Design a scheme that allows king Yéméchan to determine exactly which
one of his wine bottles was poisoned in just one month’s time, while “hiring” (conscripting)
as few taste testers as possible.
Hints: (1) you are looking for a solution that will hire f (n)√testers in the worst case, where
f (n) ∈ o(n). So f (n) = n/2 does not work, but f (n) = n or f (n) = 17 would be fine
(except for the taste testers, of course). (2) think about binary representation.
King Yéméchan will number his n wine bottles from 0 to n − 1 arbitrarily, and hire ⌈log n⌉
taste testers. Taste tester #i will drink a mix of every wine bottle whose number, written in
binary, has its ith bit equal to 1.
After a month has elapsed, the king will check which one(s) of the taste tester survived (if
any). The poisoned bottle will be the bottle with number

b⌈log n⌉−1 . . . b1 b0

where bi is 1 if taste tester #i has died, and bi is 0 if taste tester #i is still alive (we assume
that no taste tester will die of anything other than the poison in the bottle during that month).

References
[1] Edward Thurber. Concerning the maximum number of stable matchings in the stable marriage
problem. Discrete Mathematics, 248:195–219, 04 2002.

This work is licensed under a Creative Commons Attribution 4.0 International License. cb
For license purposes, the author is the University of British Columbia.