COMP 212
Written Assignment 1
Due 1:10 pm, March 6, 2000
All problems are of equal value.

1.

(a)

What is the smallest value of n such that an algorithm with running time 10 n log n runs faster than an algorithm with running time n²?

(b)

Assume on inputs of size 1000 an algorithm with running time 5 n² takes one second to solve a problem on a given computer. How large of an input could the algorithm solve in one hour on the same computer?

2.

Rank the following functions by order of growth; that is, find an arrangement g₁, g₂, g₃, g₄, g₅ of the functions satisfying g₁ = O(g₂), g₂ = O(g₃), g₃ = O(g₄), g₄ = O(g₅).

$$n^2 ,\ \ ( \log n )^2 ,\ \ 2^{\log n} ,\ \ n^{ \log n} ,\ \ 2^n .$$

3.

Solve the following recurrences for the case of n being a power of 2, and C₁ = 1:

(a)

C_n = C_n/2 + n²

(b)

C_n = 2 C_n/2 + n²

4.

(a)

Sedgewick, pg 147, Problem 4.9.

(b)

Sedgewick, pg 147, Problem 4.10.

5.

(a)

Sedgewick, pg 254, Problem 5.86.

(b)

Sedgewick, pg 255, Problem 5.90.