Exercise 1        Name __________________        Score __/32
Document last modified: 

1. (4) In a spreadsheet, compute for 1≤n≤20: n*log₂n, n², n! and nⁿ

2. (4) Exercises 1.2-2, 1.2-3

Note that n is an integer and can be determined by simply calculating one algorithm's (steps or runtime) performance against the other.

1.2-2 Suppose we are comparing implementations of insertion sort and merge sort one the same machine. For inputs of size n, insertion sort runs in 8n² steps, while merge sort runs in 64n lg n steps. For which values of n does insertion sort beat merge sort?

1.2-3 What is the smallest value of n such that an algorithm whose running time is 100n² runs faster than an algorithm whose running time is 2ⁿ on the same machine?

3. (16) Problem 1-1 for 1 second, 1 minute and 1 hour.

For a function f(n) determine the largest problem size n that can be solved in time t, assuming that the algorithm to solve the problem takes f(n) microseconds.

Note for functions with inverses, such as:

f(n) = ^v n = 1,000,000 ms, the inverse ^v n ² = n = 1,000,000² =(10⁶)² = 10¹²

f(n) = log₂n = lg n = 1,000,000 ms, the inverse 2^{lg n} = n = 2^1,000,000

 

	1 second = 1,000,000 ųsec. = 106 ųsec.	1 minute = 60,000,000 ųsec.= 6*107 ųsec.	1 hour = 3,600,000,000 ųsec. = 36*108
lg n
n1/2
n
n lg n
n2
n3
2n
n!

Hints:

a) 1 second = 1,000,000 microseconds = 10⁶ microseconds

b) Row 5, column 1: for f(n) = n²=10⁶, (n²)^1/2 = (10⁶)^1/2, n=10³

c) If an inverse can be found as in Hint b, some might be more easily solved algebraically, others by calculation similar to Question 1 above.

d) n is an integer.

4. (3) Find a closed formula for: 1/(1*2) + 1/(2*3) + ... + 1/(n(n+1))

    Hint: Determine P(1), P(2), P(3), ... until a clear pattern is discernable.

5. (5) Use induction to prove your above result.

    Hint: Start with the Induction Hypothesis, the closed formula.