CSE 326, Winter 1999: Homework 2
Due 1/22/99
For all program or data structure design problems such as the two below
you must provide pseudocode (see the manual)and an adequate explanation of
the methods. It is often helpful to include
small examples demonstrating the methods.
Staight pseudocode with no additional documentation is not enough.
- (10 points)
Consider the following general recurrence T(1) <= d and T(n) <= aT(n/b) + cn
for a time bound.
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.
- (10 points)
A recursive version of insertion sort on a list c1,c2,...,cN
can be defined as follows. If the list is empty there is nothing to do.
If the list in not empty then recursively sort c2,c3,...,cN then insert
c1 into it proper position in the sorted list. For example if the original
list is 5,8,2,3,7 then the recursive call returns 2,3,7,8 and then 5
is inserted into this list finally return 2,3,5,7,8.
-
Design a recursive program to do insertion sort where the items to
be sorted on in a linked list. Nodes have two fields data
and next.
-
Write a recurrence that describes the running time of the algorithm
and solve it.