CSE 326 Autumn 2000

Homework #1

DUE: FRIDAY, OCTOBER 6^th, in class (2:30pm)

1. Weiss #2.2. Note the use of “little o” notation in problem (b); see book for definition.

2. Weiss #2.7, part (a) only, examples (3) and (5) only.

3. Consider the following general recurrence T(1) ≤ d and T(n) ≤ aT(n/b) + cn for a time bound. Assume that b>1 (otherwise the recurrence is not well founded), a≥1, c≥1.

Show that:

If a < b then T(n) = O(n).
If a = b then T(n) = O(n log n).
If a > b then T(n) = O(n^{log_b a}) (n to the power log base b of a).

You may assume that n is a power of b in your argument. A very good argument would determine the constants and low order terms hidden in the big O notation, and show the bound by induction on n.

4. In class (either lecture 3 or 4) we discussed the stretchy array implementation of a stack. Suppose instead of doubling the size of the array when Push would otherwise cause an overflow, the array is increased in size by a constant amount:

maxsize = maxsize + 10

Give an amortized analysis (upper bound, big-O) of the cost of Push (averaged over a sequence of n pushes). Assume maxsize is initially 0. The analysis will consist of the following steps:

(a) How many stretches for n pushes?

(b) What is the total time to perform n pushes, counting both the regular pushes and those that cause a stretch? (Hint: recall the formula for evaluating an arithmetic series.)