Homework Set 4: Selection, Amortization, and Greed
CS326
1. The Oil of Olay Problem [25 points]
Exercise 9.3-9 in CLRS (Page 193). Before beginning this problem, argue why placing the
pipeline at the mean value of y might not necessarily give an optimal answer (i.e. provide
a counter example in which this strategy will break). “Showing an optimal location can be
determined in linear time” requires describing an algorithm that: i) runs in linear time; and
ii) is actually correct.
While you don’t need to show a formal proof of correctness, you should provide a clear
explanation for why your approach correctly returns an optimal answer.
2. Dynamic Arrays Revisited [40 points] A dynamically re-sizing array is an array that is
initially allocated at size 1, and every time you need to insert past the end of the array you
double its size and copy elements from the old array to the new array.
In class, we showed that n inserts into a dynamic array can be accomplished in O(n) using an
accounting argument where we pre-paid $3 for each insert, thus pre-paying for its doubling
and the doubling of one older element.
(a) Formally write the proof for this accounting
(b) Show the same bound using the potential method
(c) Does this O(n) bound on n operations hold if you include deletions? Why or why not?
(Credit will be given for solutions that prove that a bound does work with particular
array assumptions).
3. Amortizing Red-Black Trees [50 points]
CLRS Problem 17-4, parts a, c, d, e, f (In the back of the chapter)
4. Block Uh Oh [20 points] Dr. I Lai has a son in preschool, and she wants to spell out words
to him with alphabet blocks by picking up one block at a time to show to him. However,
somehow every block is covered in BabySlime, so they are very hard to pick up unless they
are in the ACME Block Washer. Unfortunately, the washer has only 5 spots. Picking up a
block from the washer costs one Happiness Point every time. Picking up a block from the
washer is free!
Dr. Lai would to spell out her favorite song, ”ALGORITHMS ARE THE BESTEST BEST
BEST YEAH”, with a minimal number of BabySlime interactions (so as many letters pulled
out of the block washer as possible). Note: Letters can be swapped into the block washer,
but putting a new block into the washer requires getting it from the table, which costs a
happiness point.
1
(a) Design an optimal Greedy Algorithm for placing blocks in the block holder. What is the
cost in happiness points?
(b) Generalize your algorithm to k blocks in the holder and a string of size k.
(c) Can you use a greedy algorithm if you don’t know the entire sequence ahead of time?
2








































学霸联盟