write out the assignment questions

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.)