Do problems 3.3.5-3.3.9 in the textbook. (Note that problem 3.3.8 is a programming problem.)
Do problem 3.4.8 in the textbook. Analyze your algorithm's worst-case run-time.
Extra credit: do problem 4.6.10 in the textbook. (Note that this solves the same problem as 3.3.8, but using the "quick-hull" algorithm rather than brute force. You may want to incorporate both as separate functions in one program, so you can easily test them side by side on the same inputs.)
Consider the recurrence T(n) = T(√n) + 1
with base case T(1) = T(2) = 0.
What restriction could you make on n
in order to ensure that all the values plugged into T are integers?
Solve this recurrence,
giving your answer in θ notation.
Hint:
use a change of variables to convert it into a more familiar form.
Solve the recurrence T(n) = T(αn) + T((1-α)n) + n,
where α is a constant strictly between 0 and 1/2. Give your
answer in θ notation; it may (or may not) depend on the value of
α.
Hint: use a recursion tree, like one of
the approaches we took to analyzing merge sort.
An electronic chip is designed in such a manner that any two chips can be connected to test one another; each chip reports whether the other one is good or bad. A good chip always reports correctly whether the other chip is good or bad, but a bad chip's report cannot be trusted. Thus there are four possible outcomes:
| Chip A says | Chip B says | Conclusion |
|---|---|---|
| B is good | A is good | Either both are good, or both are bad |
| B is good | A is bad | A (and possibly B) is bad |
| B is bad | A is good | B (and possibly A) is bad |
| B is bad | A is bad | At least one is bad |
Recall the merge operation, which takes two sorted lists and
combines them into a single sorted list containing all the elements of
both. Consider the merge-k operation, which takes
k sorted lists and combines them into one. Describe
an algorithm to do this in θ(n lg(k)) time.
Hint: use a heap to combine k things.
Consider the following sorting algorithm:
stooge-sort (A, i, j) {
if A[i] > A[j]
swap A[i] and A[j]
if i+1 ≥ j
return
let k = floor((j-i+1)/3) // one third the length, rounded down
stooge-sort (A, i, j-k) // sort first two thirds
stooge-sort (A, i+k, j) // sort last two thirds
stooge-sort (A, i, j-k) // sort first two thirds again