CS 4349 — Advanced Algorithm Design and Analysis, Homework 3
Question 1
a
Failing Substitution Proof:
has the solution Assume that . We must show that
b
Substitution Proof:
has the solution Assume that . We must show that
Question 2
a
The running time of randomized quicksort algorithm for A runs in . This can be seen simply through observing that in each recursive call of RANDOMIZED-PARTITION, a swap occurs between the selected pivot and every element.
Thus we must solve subproblems of sizes
b
A = before the execution of the algorithm.
Question 3
We must compute the expected number of inversions in A. Let be an indicator random variable. We define it as follows
by linearity of expectation. Note that we only take the pairs with
.
Question 4
COW, DOG, SEA, RUG, ROW, MOB, BOX, TAB, BAR, EAR, TAR, DIG, BIG, TEA, NOW, FOX
Looking at the ending digit:
SEA, TEA, MOB, TAB, DOG, RUG, DIG, BIG, BAR, EAR, TAR, COW, ROW, NOW, BOX, FOX
Now the middle digit:
TAB, BAR, EAR, TAR, SEA, TEA, DIG, BIG, MOB, DOG, COW, ROW, NOW, BOX, FOX, RUG
Finally, the beginning digit, leading to a sorted array:
BAR, BIG, BOX, COW, DIG, DOG, EAR, FOX, MOB, NOW, ROW, RUG, SEA, TAB, TAR, TEA
Question 5
We must pre-process the data similar to bin sort. Each bucket will contain the interval . Place element of value into bucket . Note that this may lead to a double insertion in adjacent bins, but this will not be an issue. This takes Now for the algorithm:
Return the size of bucket