Due Date: November 8th, 2005 at 2:00 PM
See course policy regarding late homework submissions
- Read Chapter 2 of the textbook in detail.
- Problems: You need to turn in a hard copy of your written
solutions to the following exercises
at the beginning of class on the day the homework is due.
Remember to show your work and explain your answers.
Correct answers without complete explanations won't receive full credit.
Incorrect answers with explanations may receive partial credit.
- Chapter 2: exercise 1.
- Chapter 2: exercise 2.
Solve execise 2 and add to it the following parts:
within 1 second?
within 1 minute?
within 1 day?
within 1 month?
within 1 year?
within 1 century?
That is, your solutions to this exercise should contain a table like the one
below together with explanations for each of the values you provide in your table.
| | 1 second | 1 minute | 1 hour | 1 day | 1 month | 1 year
| 1 century
|
| n2
| | | | | | |
|
| n3
| | | | | | |
|
| 100 n2
| | | | | | |
|
| n log n
| | | | | | |
|
| 2n
| | | | | | |
|
| 22n
| | | | | | |
|
- Chapter 2: exercise 3.
- Chapter 2: exercise 5.
- Chapter 2: exercise 6.
- Let f(n) and g(n) be two non-negative functions, and let max(x,y) be the
function that returns the maximum between its given arguments. Using the basic
definition of Θ-notation, prove that max(f(n),g(n)) = Θ(f(n) + g(n)).
- For each of the following statements, determine if the statement is true
or false, and in each case provide a detail explanation/proof of your
answer:
- Is 2n+1 = O(2n) ?
- Is 22n = O(2n) ?