diff options
| -rw-r--r-- | 0x01/README.md | 56 | ||||
| -rw-r--r-- | notes.md | 48 |
2 files changed, 104 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.) @@ -1395,3 +1395,51 @@ n^n 3125000000000003092243963814697472323387062050608712810316261079389878210275894062864994740260526805850873354374897838591668659178014794724456808448969682640589359820361298594587056678177036967084032 ┤ │ 0 ┼──────────────────────────────────────────────────────────────────────╯ ``` + + + +https://www.udemy.com/course/datastructurescncpp/learn/lecture/13319452#overview + +Asymptotic Notation Video + + +| 1 < lg n < n < n lg n < n^2 < n^3 < .... < 2^n < 3^n ... < n^n | + + | polynomial | | exponential | + + +1 : push into stack +lg n : AVL tree +n : max item in array +n log n : quick sort +n^2 : matrix, graph +2^n : exponential time complexities + +Don't start n from n = 0 or n = 1. +Starting value of n can be any starting value + +n 0 --|---- infinity + |------------ + + + +| n^3 | 2^n | +| --- | ---- | +| 2^3=8 | 2^2=4 | +| 10^3=1000 | 2^10=1024 | +| 11^3=1221 | 2^11=2048 | + + + +f(n) = n ---> O(n) +f(n) = n^2 ---> O(n^2) + +f(n) = n + sigma i ----- 1 + 2 + 3 + .... + n = ((n(n+1))/2) = O(n^2) + i=1 + +| lower bound | omega | +| upper bound | big-oh | +| tight bound | theta | + +Useful when you cannot get the exact polynomial for a function. |