COS 341, December 3, 1997Handout Number 21
About Final Exam and Homework Set Number 8
Announcement The Take-Home Final Exam will take place during January 6-8, 1998. The exam problems sheets can be picked up from the handout box outside the mailroom for the course, anytime after 3 pm on January 6, 1996 (Tuesday). You should hand in your solutions by noon January 8, 1996 (Thursday), to Ms. Sandy Barbu in Room 323 of the Computer Science Department. Pick any 24-hour period during the above allotted time to complete your exam.
In case you have troubles (such as finding the handout box) at exam time, seek help from Ms. Barbu. Send me e-mail (yao@cs.princeton.edu) if you have any questions.
The Exam is open-book, open-notes, but no collaboration.
Homework Set Number 8
Important This homework set is due on December 10, 1998 in class. No late homework will be accepted.
Special Problem 1
Show that the diameter of a graph on n vertices
can be found in time 
where
s(n) is the time needed to multiply two 
boolean matrices. (Since 
you can
omit the 
term in the abpve time bound.)
You only need to describe the modifications needed
in the method given in Handout No. 22.
Special Problem 2
Let c > 2 and 
.
Consider the
following recurrence relation for f(n)
when n are powers of 2:
Determine the asymptotic behavior of f(n) up
to a multiplicative factor. (That is, derive
a closed-form expression g(n), and prove
that 
.
Special Problem 3 Consider the following recurrence relation:
(a) Determine the asymptotic behavior of T(n) up
to a multiplicative factor.
(b) Repeat part (a) if the last line of
the recurrence is 
instead.
Special Problem 4 Let A[0:n-1] be an array of
distinct integers, where n>0. Consider the following code:
for ¯Assume that initially A[0:n-1] contains a random permutation of n distinct integers. Let X be the random variable corresponding to the number times the instruction z=A[i] is executed. Prove that
if ¯
z = A[i];
A[i]=A[i+1];
A[i+1]=z;
where 
are
the Harmonic numbers.
Special Problem 5
In an earlier homework sets, an expression p(n)
was derived for the probability for an NBA best-of-n
final series to last n games.
(a) Determine the asymptotic behavior of
p(n) of the following form:
find a closed-form g(n)
such that 
.
(b) Repeat part (a) with the requirement
strengthed to 
.
Special Problem 6 For all n>0, let
Use the Euler Summation Formula to determine the asymptotic behavior of f(n) for large n up to an additive term O(1). (That is, find a closed-form expression g(n) such that f(n) = g(n) + O(1).) Justify your answer.