Carnegie Mellon University
School of Computer Science
Final Exam in CS15750: Algorithms and Data Structures
Date: Friday 9 May 2003 Instructor: Manuel Blum
Teaching Assistant: Ryan Williams
* This is a closed book examination: While calculators ARE allowed,
NO books, NO laptops, NO scratch paper are permitted.
* Do all your work including scratch work on the pages of this exam.
* This exam has 11 problems worth a total of 61 pts.
* All arguments in quotes are questionable. If you believe a given
answer but not the argument, then check that answer and extend,
correct or replace the given argument.
* Check as many answers as are correct. It may happen that no
answer is correct.
* If none of the given answers are correct, then insert your own
correct answer.
(1 pt) SOLUTION
Your name:______________________, __________________________
FAMILY (LAST) GIVEN (FIRST)
Your signature:_____________________________________________
Your email address:_________________________________________
(2 pts)
1. Meld the following two Binomial heaps into a single Binomial heap:
min
\
Heap 1 = 2* 1* 4*
 \
3* 5* *6

*7
min
\
Heap 2 = NIL 8* NIL

9*
min >1 _
\ \_
3 8 4
Meld of 1 and 2 = 2* NIL NIL  \
9 5 6

7
(20 pts total  2 pts each)
2. Which of the following operations are supported by
A = (classical) Binary Heaps.
B = Binomial Heaps.
C = Fibonacci Heaps. Answer
here:
heapify(a1,...,an) = create a heap on a given set of n
elements in O(n) steps. ABC
makeheap(a) = create a heap on 1 element in O(1) steps.
ABC
insert(a,H) = insert element a to heap H in O(1) amortized
steps. BC
insert(a,H) = insert element a to heap H in O(lg n) steps.
ABC
deletemin(H) = delete the minimum element of heap H in O(1)
steps. NONE
deletemin(H) = delete the minimum element from heap H in
O(1) amortized steps. NONE
deletemin(H) = delete the minimum element from heap H in
O(lg n) amortized steps. ABC
meld(H1,H2) = combine heaps H1 and H2 into one heap in
O(lg n) amortized steps. BC
delete(a,H) = remove element a from heap H in
O(lg n) amortized steps. ABC
decrement(a,,H) = decrease the value of the element a in H
by amount in amortized O(1) steps. C
(2 pts)
3. Do splay(1,T) on the Splay Tree T = 4* 1
/ \ \
(Do not ask the exam proctor what a 2* *5 > 2
splay tree is or how to solve this / \ \
problem: you are supposed to know.) 1* *3 4
/ \
3 5
(2 pts)
4. The elements 0,1,2,3,4,5,6,7,8,9 have the following priorities:
3 1 4 5 9 2 6 8 7 0. This means that 3 has highest priority and
0 has lowest priority.
Construct the treap of these elements with these priorities.
3
/ \
1 4
/ \ \
0 2 5
\
9
/
6
\
8
/
7
(4 pts)
5.Toss n balls uniformly at random into n cells.
Q. What is the expected number of empty cells? Answer(s) should be
correct asymptotically as n > infinity.
__
Check correct answers: /A \ Cross out incorrect answers: X A .
__ \__/
/A1\ n/e "The probability that a given cell is empty is
\__/ (11/n)^n ~ 1/e, so the expected number of empty cells is
asymptotically n/e."
X A2. n/(ln n) "By the coupon collectors problem, n(ln n) balls is needed
to put a ball in each of n cells. So if only n balls are tossed, the number
of empty cells will be n/(ln n)."
Q. What is the expected number of cells that contain exactly one ball?
A: The prob that a cell has exactly one ball is
nchoose1 * 1/n *(11/n)^(n1) ~ 1/e. Therefore the expected value is n/e
/
A.Select one: n/e \/. n/e^2 _X_. n/(ln n) _X_. other:_X__
Q. What is the expected number of cells that contain 2 or more balls?
__
/A1\. Asymptotic to something less than n/e.
\__/
X A2. n/e.
X A3. More than the number of cells that contain 0 or 1 ball(s).
(4 pts)
6.Cover time: Recall that cover time is defined to be the expected number
of steps to visit every vertex at least once, starting from the "worstcase"
vertex for which this time is largest.
Q. What is the cover time for a random walk on the undirected circle of
n nodes:
Circle = 1  2
/ \
n 3
\ /
....
X A1. O(n) "It takes 10*n steps to walk completely around the circle ten
times, which is more than enough time to cover the circle once."
X A2. O(n*ln n) "One must toss expected O(n*ln n) balls to get a ball in
each of n bins. A random walk on a circle is essentially equivalent to
tossing balls into bins."
__
/A3\. O(n^2) "For u,v at opposite ends of the circle, the
\__/ commute time is Cuv = O(n^2)."
[Cuv = 2*m*Ruv approx= 2(n)*n/4 ~ (n^2)/2, and in at most expected
3*Cuv/2 steps (expect to make 3 flips of a fair coin to get at least
1 H and at least 1 T), all vertices will be visited.]"
__
/A4\. O(n^3) "The cover time for any undir graph is O(n^3)"
\__/
(4 pts)
7. T or F: Every finite planar graph G = with no self loops
and no multiple edges between the same two nodes has at least one vertex of
degree at most 5.
_
/T\ "This is a consequence of an Euler theorem: VE+F=2 for
\_/ planar connected graphs."
X F "A typical hexagonal pattern of kitchen tiles  viewed as the nodes
of a graph  leads one to infer that one can draw a planar graph on a
sphere  the earth  so that every node has degree 6. In this graph,
the nodes correspond to hexagons. Two nodes are adjacent (joined by an edge)
if the corresponding hexagons share an edge:"
_ _ _ \/ \/ \/
_/ \_/ \_/ \ * * *
Kitchen / \_/ \_/ \_/ corres \/\/\/\
tile = \_/ \_/ \_/ \ ponding = *  *  * 
floor / \_/ \_/ \_/ graph /\/\/\/
\_/ \_/ \_/  *  *  *
\/\/\/\
* * *
/\ /\ /\
(4 pts)
8. Can every degree 3 graph (ie. a graph whose vertices all have degree 3)
be properly 4colored?
X No. "By the 4color theorem, all planar graphs can be properly 4colored
but nonplanar graphs in general need more colors and there exist nonplanar
degree 3 graphs."
X Yes. "Every graph of degree 3 is planar, and every planar graph can be
properly 4colored."
__
/YES\ Whatever 3 colors are used for the neighbors of a vertex
\___/ v, a 4th color remains to color v.
(10 pts)
9. A Tournament Graph problem:
Recall that a Tournament Graph (TG) is a directed graph with
n_choose_2 = n(n1)/2 edges such that for every pair of distinct vertices
i,j, exactly one of and is in E.
Q. Is there an efficient algorithm to decide if a TG has a Hamilton Cycle (HC)?
X A1. NO. "The Hamilton Cycle Problem is NPhard, so there is no known algorithm
to decide efficiently if a graph has a HC."
__
/A2\. YES. "The following algorithm (possibly modified)
\__/ decides HC of any given TG in poly(n+m) time."
BEWARE: This algorithm has some very serious errors !!
ALGORITHM
In O(n+m) time, check if there is a vertex of indegree
(or outdegree) 0. If so, return `NO HC'. Else
Construct a cycle C = v1 >v2 > ... >v1.
Until C is a HC, do:
For arbitrary vertex v not in C, look for two successive
vertices vi,vi+1 in C such that vi > v and v > vi+1.
If none such exist, return `NO HC'.
Else extend C to include v.
Return C.
__
/A3\. YES. "The above algorithm ( substantially modified)
\__/ decides if a given TG has an HC in O(n+m) time."
(4 pts)
10. We did a problem like this in class, but watch out as this one is (slightly)
different: n people each have a random bit on their forehead. Each can see the
bits on everyone else's forehead but not on their own. Each has to guess the bit
on his own forehead.
This problem is different in that there is no voting !!
Q. Is there a randomizing algorithm that takes as input the bits on everyone's
forehead except one's own and outputs one's own bit with a better than 50% chance
of guessing that bit correctly? Equivalently, can you improve your chances of
success by looking at the bits around you?
__
/A1\. NO "Your own bit is independent of the bits around you,
\__/ so no matter how you guess, the probability that you guess your own
bit correctly is 1/2."
X A2. YES "If you see more 1's than 0's then you should guess that your own bit
is 0 as the expected excess of 1's over 0's is 0.
X A3. YES "If you see more 1's than 0's, then you should guess that your own bit
is 1 as this will ensure that more people guess correctly than not.
X A4. YES "but the correct algorithm depends on n.
(4 pts)
11. Recall that f(n) ~ g(n) iff lim f(n)/g(n) = 1.
n > infinity
Q. Is (1  1/n)^(n ln n) ~ 1/n ?
___
/YES\ But the following argument needs to be corrected:
\___/(1  1/n)^n ~ 1/e so (1  1/n)^n(ln n) ~ 1/e^(ln n) ~ 1/n"
X NO Though the argument is correct, it does not disprove the
assertion.
"Even if f(n) ~ g(n), there is no guarantee that
f(n)^(ln n) ~ g(n)^(ln n). For example,
1 ~ 1  1/(ln n), but
1^(ln n) NOT ~ (1  1/(ln n))^(ln n) since
1^(ln n) ~ 1 while (1  1/(ln n))^(ln n) ~ 1/e."