Homework assignment 1
CSCI 3650
Summer 2001
Due: Monday May 21
These assignments are from Cormen/Leiserson/Rivest.
- Page 38 exercise 2-2.
- Page 39 exercise 2-4 a,b,d,e.
- Page 72 exercise 4-1. (Use the master theorem.)
- Page 73 exercise 4-2. (Requires thought, plus solving a recurrence.)
You can fill in the following table for problem 2-2. Since I will
not presume that you have a Greek font, I will make substitutions for
Greek letters.
| A |
B |
O |
OMEGA |
THETA |
| (lg n)k |
ne |
|
|
|
| nk |
cn |
|
|
|
| n1/2 |
nsin n |
|
|
|
| 2n |
2n/2 |
|
|
|
| nlg m |
mlg n |
|
|
|
| lg(n!) |
lg(nn) |
|
|
|