write out the assignment questions

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.)
diff --git a/notes.md b/notes.md
index 74b0fbb..c1b4206 100644
--- a/notes.md
+++ b/notes.md
@@ -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.