CSE 326 – Data Structures – Winter 2002

Homework #2 – Analysis of Algorithms

Due Friday, January 25th, 2002
Hand in hardcopy in class

Goals of this assignment:

• Gain experience with order of magnitude notation
• Practice analyzing non-recursive and recursive procedures
• Option: Perform an amortized analysis.

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, example (5) only.

3. Weiss #2.12.

4. Below are two recursive procedures for printing a list in reverse. Write down a recurrence relation for the running time T(n) of each. You do not have to solve the formula! (This is pseudo-code based on ordinary C. Here we are simply using a pointer to node to be the same as a list.)

struct node { string data; node * next; }

(a)

void PrintReverse1( node * list, int n ){

node * last = list;

if (n == 0) return;

for (int i = 1; i<n; i++) last = last->next;

cout << last->data << “ “;

PrintReverse( list, n-1 );

}

(b)

void PrintReverse2( node * list, int n ){

if (n == 0) return;

PrintReverse( list->next, n-1 );

cout << list->data << “ “;

}

CONTINUED ON OTHER SIDE OF PAGE
5. Consider the following general recurrence:

T(1) ≤ d

T(n) ≤ aT( n/b ) + cn

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.

6. The following is an optional bonus question. It is not required. Bonus points earned may be redeemed for valuable prizes later in the course.

In class 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 a lower-bound amortized analysis 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) What is the worst sequence of n operations the algorithm could see? How many stretches would be performed?

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

(c) What is the amortized time per push?