diff options
Diffstat (limited to '0x01/README.md')
| -rw-r--r-- | 0x01/README.md | 56 |
1 files changed, 56 insertions, 0 deletions
diff --git a/0x01/README.md b/0x01/README.md index da94bc4..495a0f1 100644 --- a/0x01/README.md +++ b/0x01/README.md @@ -178,9 +178,65 @@ Submit your solutions to the following exercises and problems: ``` 1. Exercise 3.1-1 from the textbook (5 marks) + + Let `f(n)` and `g(n)` be asymptotically nonnegative functions. + Using the basic definition of theta-notation, + prove that `max(f(n), g(n))` = `theta(f(n) + g(n))`. + + + ```plaintext + max(f(n), g(n)) + ``` + 1. Problem 3-1 from the textbook (10 marks) + +Asymptotic behaviour of polynomials + +Let + +``` + d +p(n) = Σ ai n^i + i=0 +``` + +where `ad > 0`, be a degree-d polynomial in `n`, and let `k` be a constant. +Use the definitions of the asymptotic notations to prove the following +properties. + + a. If `k >= d`, then `p(n) = O(n^k)`. + b. If `k <= d`, then `p(n)` = `omega(n^k)`. + c. If `k = d`, then `p(n) = theta(n^k)`. + d. If `k > d`, then `p(n) = o(n^k)`. + e. If `k < d`, then `p(n) = w(n^k)`. + 1. Exercise 4.1-2 from the textbook (10 marks) + + What does `FIND-MAXIMUM-SUBARRAY` return when all elements of `A` are negative? + 1. Exercise 4.2-1 from the textbook (5 marks) + + Use Strassen's algorithm to compute the matrix product + + ```plaintext + |1 3||6 8| + |7 5||4 2| + ``` + + Show your work. + 1. Exercise 4.3-2 from the textbook (10 marks) + + Show that the solution of `T(n) = T([n/2]) + 1` is `O(lg n)` + 1. Exercise 4.4-7 from the textbook (10 marks) + + Draw the recursion tree for `T(n) = 4T([n/2]) + cn`, where `c` is a constant, + and provide a tight asymptotic bound on its solution. Verify your bound by the + substitution method. + 1. Exercise 4.5-3 from the textbook (10 marks) + + Use the master method to show that the solution to the binary-search + recurrence `T(n) = T(n/2) + theta(1)` is `T(n) = theta(lg n)`. (See Exercise + 2.3-5 for a description of binary search.) |