# CSC 344 Homework 3

## Assigned 25 Feb, due 15 Mar

### Problems from the Levitin textbook

• 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.)

### Problems from Cormen, Leiserson, & Rivest's Introduction to Algorithms

• 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 saysChip B saysConclusion
B is goodA is goodEither both are good, or both are bad

1. Suppose more than half of the n chips are good. Describe an algorithm you could use to reduce the problem to one of at most approximately n/2 size, using approximately n/2 tests. (Note: the new problem must still satisfy the assumption that more than half of the chips are good, or it doesn't count as the same problem.)
2. Still assuming that more than half of the n chips are good, describe an algorithm to find exactly which chips are good, using θ(n) tests. (This will require stating and solving a recurrence.)
3. Assume that at least half of the chips are bad. Convince me (i.e. "prove") that under these circumstances, there is no way to tell which ones are good and which are bad. Hint: imagine that the bad chips are all controlled by a single malevolent demon who's trying to lead you to a wrong answer. Describe an algorithm this demon could use to fool you, no matter what algorithm you use.

• 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
```
1. Convince me that the algorithm correctly sorts the elements of A from position i to j inclusive.
2. Give and solve a recurrence for its worst-case run-time, writing the result in θ notation.
3. Compare this running time with that of the other sorting algorithms we've discussed in class. Is it a good algorithm?