RECITATION NOTES 15-451 Algorithms 09/12/12
* problem related to Thurs lecture last week.
* Problems 1.5,2 from last-week's notes if didn't get to them.
* getting tight upper/lower bounds for some problem (2 suggestions)
=======================================================================
Problem related to Thurs lecture:
We saw in lecture by a "stack of bricks" argument that a recurrence of
the form:
T(n) = n + T(a1 * n) + T(a2 * n) + ... + T(ak * n)
(for constants a1,...,ak) solves to O(n) so long as a1 + ... + ak < 1.
What about a recurrence like:
T(n) = n^2 + T(a1 * n) + T(a2 * n) + ... + T(ak * n)
or
T(n) = n^b + T(a1 * n) + T(a2 * n) + ... + T(ak * n)
What conditions on the ai do you need so that this gives O(n^b)?
[Answer we just need a1^b + ... + ak^b < 1. Let's define "r" to be
this quantity. Looking at the "stack of bricks" argument, each time
you move down one level, each brick gets replaced by something r times
its size. So, the sum of sizes of the bricks at each level is r times
the sum at the previous level. This means the total work down is a
decreasing geometric series.]
============================================================================
Problems 1.5, 2 from last week's notes if didn't discuss last time.
============================================================================
Upper/lower bounds in concrete models, Option A:
Here is a variation on the 20-questions game. Say I choose a
number between 1 and N and you want to guess it in as few questions as
possible (each time you make an incorrect guess, I'll tell you if it
is too high or too low). As we all know, the strategy for this
problem that minimizes the worst-case number of guesses is to do
binary search. But, what if you are only allowed ONE guess that is
too high? Can you still solve the problem in o(N) guesses? [If you
were not allowed *ANY* guesses that are too high, the only option you
would have would be to guess 1,2,3,... in order].
Any ideas?
[Another way to state the problem: you want to figure out how many
centimeters high you can drop an egg without it breaking, and you only
have two eggs...]
Here's a strategy: guess 1, sqrt(N), 2*sqrt(N),..., until you get to
some (i+1)*sqrt(N) that's too high. Now we know the number is between
[i*sqrt(N) and (i+1)*sqrt(N)] so we can finish it off in sqrt(N)
guesses. Total is at most 2*sqrt(N).
Can you show an Omega(sqrt(N)) lower bound for any deterministic algorithm?
What if the algorithm makes a guess g_i that is at least sqrt(N)
larger than any previous guess? What if the algorithm *never* makes
such a guess?
Want to try an upper/lower bound if you're allowed *two* guesses that
are too high?
[Ans: Theta(n^{1/3})]
=======================================================================
Option B:
More practice with lower bounds: lower bounds for quicksort variants
Last week we looked at two versions of quicksort: (1) pick leftmost
element as pivot, and (2) pick *random* element as pivot. We saw
there were inputs that could cause the 1st method to make Omega(n^2)
comparisons, but proved that for *any* input, expected time of 2nd
method is only O(n log n). But might ask: what about a more
sophisticated method for picking a pivot? E.g., unix qsort uses
"median of 3" rule: look at leftmost, rightmost, and middle element
and take their median, then use that as the pivot. Does that get rid
of the Omega(n^2) worst case?
Claim: Any deterministic algorithm that selects pivots by examining a
constant c number of elements and then choosing one of them as pivot will
still result in quicksort taking Omega(n^2) comparisons in the worst-case.
[So, this is a lower bound for a restricted class of algorithms]
Proof: Given some algorithm ALG that chooses pivots by examining <= c
elements, we will show that for any n, we (the adversary) can
construct an ordering of {1,...,n} that causes ALG to make n^2/c'
comparisons, for some constant c'.
Here is how we do it. Think of the array A as n boxes. We will
now simulate ALG on A, filling in the boxes as we go.
Set counter i=1. When ALG examines a box, put i in there, and then
increment i. Eventually, after examining <= c elements, ALG picks one
as a pivot and splits. Key invariant: all empty boxes will have
elements >= the current value of i. So, all empty boxes go
into the GREATER pile. Notice that since our procedure only
increments i, this invariant is actually correct, and this
holds true at every partition step. Since there are at least n-kc
empty boxes after kth partition step, the total number of comparisons
is at least:
(n-c) + (n-2c) + (n-3c) + ...
which is > n^2/c' for some constant c'. QED
One note: is this legal? I mean we came up with elements as we went
along. But the point is that since the alg is deterministic, it
will behave exactly the same way if you run it again on whatever
inputs we ended up putting in. (It was important that our decisions
were self-consistent though.)