path: root/0x01/README.md

# Problem Set 1

* Weight: 10% of your final grade
* Due: after Unit 2

Save your answers to the exercises in Microsoft Word, plain text, or PDF files.
When you complete all the exercises of an assignment, zip them into a single file and submit it here.

Submit your solutions to the following exercises and problems:

1. Exercise 1.1-4
  * How are the shortest path and traveling-salesman problems given above similar?
  * How are they different?

    The shortest path problem is looking for an efficient solution that routes
    from point A to point B. The traveling-salesman problem is similar except
    that the sales person needs to visit multiple locations then return to the
    starting point in the most efficient way. These problems are similar because
    the shortest path from point A to B can be used to help determine a good
    enough solution for the traveling-salesman problem.

    Both of these problems are considered an NP-complete problems because it
    hasn't been proven if an efficient algorithm can or cannot exist.


1. Exercise 1.2-2 from the textbook (5 marks)
  * Suppose we are comparing implementations of insertion sort and merge sort on
    the same machine. For inputs of size n, insertion sort runs in 8n^2 steps,
    while merge sort runs in 64nlg(n) steps. For which values of n does
    insertion sort beat merge sort?

    The following program produces a result of '44'.

    ```golang
    func main() {
      fmt.Println("n,isort,msort")

      for n := 2.0; n < 1000.0; n++ {
        isort := 8 * math.Pow(n, 2)
        msort := 64 * (n * math.Log2(n))

        fmt.Printf("%v,%v,%v\n", n, isort, msort)
        if isort > msort {
          break
        }
      }
    }
    ```

    ``csv
    n,isort,msort
    2,32,128
    3,72,304.312800138462
    4,128,512
    5,200,743.0169903639559
    6,288,992.6256002769239
    7,392,1257.6950050818066
    8,512,1536
    9,648,1825.876800830772
    10,800,2126.033980727912
    11,968,2435.439859520657
    12,1152,2753.251200553848
    13,1352,3078.7658454933885
    14,1568,3411.390010163613
    15,1800,3750.614971784178
    16,2048,4096
    17,2312,4447.159571280369
    18,2592,4803.753601661543
    19,2888,5165.4798563474
    20,3200,5532.067961455824
    21,3528,5903.274616214654
    22,3872,6278.879719041314
    23,4232,6658.683199315923
    24,4608,7042.502401107696
    25,5000,7430.169903639559
    26,5408,7821.531690986777
    27,5832,8216.445603738473
    28,6272,8614.780020327225
    29,6728,9016.412726956773
    30,7200,9421.229943568356
    31,7688,9829.12547980756
    32,8192,10240
    33,8712,10653.760380085054
    34,9248,11070.319142560738
    35,9800,11489.593957956724
    36,10368,11911.507203323086
    37,10952,12335.985569809354
    38,11552,12762.9597126948
    39,12168,13192.363938280172
    40,12800,13624.135922911648
    41,13448,14058.216460117852
    42,14112,14494.549232429308
    43,14792,14933.080604940173
    44,15488,15373.759438082629
    ```


1. Exercise 2.1-3 from the textbook. (10 marks)

    Consider the searching problem:

    Input: A sequence of n numbers A = {a1, a2, ...., an} and a value v.
    Output: An index i such that v = A[i] or the special value NIL if v does not
    appear in A.

    Write pseudocode for linear search, which scans through the sequence,
    looking for v. Using a loop invariant, prove that your algorithm is correct.
    Make sure that your loop invariant fulfills the three necessary properties.

    ```plaintext
    i = 0
    for i < A.length and v != A[i]
      i = i + 1
      if i >= A.length
        return NIL

    return i
    ```

    * initialization: initialize `i` to first index of first element
    * maintenance: continue looping if `i` is less than size of `A` and `A[i]` is
      not equal to the target value `v`.
    * termination: terminate loop when the key matches the target value.


1. Exercise 2.2-3 from the textbook (10 marks)

    Consider linear search again (see Exercise 2.1-3). How many elements of the
    input sequence need to be checked on the average assuming that the element
    being searched for is equally likely to be any element in the array? How
    about in the worst case? What are the average-case and worst-case running
    times of linear search in O-notation? Justify your answers.

    How many elements of the input sequence need to be checked on the average, assuming that the element being searched for is equally likely to be any element in the array?

      Since there are `n` elements the average would be in the middle (.i.e. `𝚯(n/2)`).
      When we drop the lower order terms this becomes `𝚯(n)`. Hence, the term
      linear search.

    How about in the worst case?

      In the worst case you need to search check every element in the input.
      Because of this the worst case would be equal to the size of the input.
      i.e. `𝚯(n)`.

    What are the average-case and worst-case running times of linear search in 𝚯-notation?

      When we drop lower order terms, like constants then they are both `𝚯(n)`


1. Exercise 2.3-5 from the textbook (10 marks)

    Referring back to the searching problem (see Exercise 2.1-3), observe that
    if the sequence A is sorted, we can check the midpoint of the sequence
    against v and eliminate half of the sequence from further consideration. The
    binary search algorithm repeats this procedure, halving the size of the
    remaining portion of the sequence each time. Write pseudocode, either
    iterative or recursive, for binary search. Argue that the worst case running
    time of binary search is O(lg(n)).

      `BINARY-SEARCH(A, t, s, e)` where `A` is an array and `s`, and `r` are indices into the array such that `s < e` and `t` is the target value to find.

      ```plaintext
      BINARY-SEARCH(A, t, s, e)
        length = e - s
        if length == 1
          item = A[s]
        else
          mid = (length / 2) + s
          item = A[mid]

        if item == t
          return mid
        if item < t
          return BINARY-SEARCH(A, t, s, mid-1)
        else
          return BINARY-SEARCH(A, t, mid+1, e)
      ```

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

  Theta notation says:

  The function `f(n) = theta(g(n))`
  if there exists positive constants c1, c2 and n0
  such that `c1 * g(n) <= f(n) <= c2 * g(n)`.

  We know that n0 is greater than zero, so we can assume that `f(n)` is greater
  than or equal to 0 and the same for `g(n)`.

  If we can find positive constants c1, c2 that exist then we can prove this is true.

  Let's re-write this problem in a way that aligns with the definition of the
  theta notation.

  1. `c1 * g(n) <= f(n) <= c2 * g(n)`
  1. replace `g(n)` with `theta(f(n) + g(n))` and we get `c1 * (f(n) + g(n)) <= max(f(n), g(n)) <= c2 * (f(n) + g(n))`.
  1. c1, c2 and n0 must be greater than zero.
  1. We can try the constants c1 = 0.5 and c2 = 1 to see if this satisfies the constraints of the function.
  1. `0.5 * (f(n) + g(n)) <= max(f(n), g(n)) <= 1 * (f(n) + g(n))`
  1. reduces to `(f(n)+g(n))/2 <= max(f(n), g(n)) <= f(n)+g(n)`

  This satisfies the constraint because `1/2 * f(n) + g(n)` will always be
  less than `f(n) + g(n)`. So there exists a constant c1 = 0.5 and c2 = 1 that
  satisfies the equation.

  Now we can claim that `max(f(n), g(n))` is tightly bound and therefore
  max(f(n), g(n)) = theta(f(n) + g(n)) because we found c1 = 0.5 and c2 = 1
  that satisfies the theta notation equation.


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

    To prove this we need to use the big-oh formula which is:
    `f(n) = O(g(n))` if there exists positive constants c and n0
    such that `f(n) <= c * g(n)` where n > n0.

    `0 <= c * g(n)` when we replace `g(n)` with `ad * n^d` we get
    `0 <= c * ad * n^d` and if `k >= d` then we can write
    `0 <= c * ad * n^d <= c * ak * n^k`
    This can be reduced to
    `0 <= n^d <= n^k` and if we swap the polynomial back in we get
    `0 <= p(n) <= n^k` so we can say that `p(n) = O(n^k)`.

  b. If `k <= d`, then `p(n)` = `omega(n^k)`.

    To prove `omaga(n^k)` we need to refer to the omega formula which says:
    The function `f(n) = omega(g(n))` if there exists positive contstants c and n0
    such that `0 <= c * g(n) <= f(n)` for all `n >= n0`.

    If `k` is less than or equal to `d` then we can say that `n^k` will grow
    slower than or equal to `n^d` as `k` approaches `d`.

    We can try to fit this into the omega function definition.
    `0 <= c * g(n) <= f(n)` where `g(n)` = `ad * n^d` or
    `0 <= c * (ad * n^k) <= f(n)`. Since `k` <= `d` we can also say
    `0 <= c * (ad * n^k) <= c * (ad * n^d)`
    If we choose the constant 0.5 for `c` we can say
    `0 <= 0.5 * (ak * n^k) <= (ad * n^d)` which reduces to
    `0 <= 0.5 * (n^k) <= (n^d)`. Since `k` is less than `d` and
    `n^k` is cut in half by multiplying it with the constant 0.5 this
    satisfies the constraints of the equation so we can make the claim that this
    function is lower bound is `n^k` or `p(n) = omega(n^k)`.

  c. If `k = d`, then `p(n) = theta(n^k)`.

    To prove `theta(n^k)` we need the theta formula.
    The function `f(n) = theta(g(n))` if there exists positive constants c1, c2, and n0
    such that `0 <= c1 * g(n) <= f(n) <= c2 * g(n)` for all `n >= n0`

    We know that `k` is equal to `d` and `d` is the upper limit. So `k` is equal
    to the largest `d` value. With that knowledge we can say that the upper
    bound will be `n^k` and since `k` is constant it is also the lower bound.
    Now we can claim that this function is tightly bound to `n^k` or `p(n) = theta(n^k)`
    which is equivalent to `p(n) = theta(n^d)`.

  d. If `k > d`, then `p(n) = o(n^k)`.

    To prove this we need the little-oh formula which says:
    The function `f(n) = o(g(n))` for any positive constant `c > 0`,
    if there exists a constant `n0 > 0` such that `0 < f(n) < c * g(n)`
    for all `n >= n0`.

    This is similar to `a` without the equality.
    `0 < f(n) < c * g(n)`
    `0 < f(n) < c * (ad * n^d)`.
    If `k` is greater than `d` then we state the following:
    `0 < c * (ad * n^d) < c * (ak * n^k)`. `n^k` will always be greater than
    `n^d` because of the constraint `k > d` therefore any constant `c` will
    work. This allows us to claim that `p(n) = o(n^k)`.

  e. If `k < d`, then `p(n) = w(n^k)`.

    To provie this we need the little-omega formula which says:
    The function `f(n) = w(g(n))` for any positive constant `c > 0`,
    if there exists a constant `n0 > 0`
    such that `0 <= c * g(n) < f(n)` for all `n >= n0`

    We can try to fit the function into this formula.
    `0 <= c * g(n) < f(n)`
    `0 <= c * (ak * n^k) < f(n)`.
    Since `k` is less than `d` we can also say
    `0 <= c * (ak * n^k) < c * (ad * n^d) < f(n)`.
    This is enough to satisfy the constraints of the formula so that we can
    claim that `p(n) = w(n^k)` because any constant c greater than 0 will work.

1. Exercise 4.1-2 from the textbook (10 marks)

  Write pseudocode for the brute-force method of solving the maximum-subarray
  problem. Your procedure should run in `theta(n^2)` time.

  The following brute force solution uses a nested loop that yields a worst case
  of `n^2` iterations.

  ```
  FIND-MAXIMUM-SUBARRAY(A,low,high)
    l = low
    r = high
    total = -1
    for i = low to high
      sum = 0
      for j = i to high
        sum = sum + A[j]
        if sum > total
          total = sum
          l = i
          r = j
    return l, r, total
  ```

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.

  ```plaintext
  Strassens algorithm:

          n
  cij = sigma ai*k * bkj
         k=1

  c11 = a11 * b11 + a12 * b21
  c12 = a11 * b12 + a12 * b22
  c21 = a21 * b11 + a22 * b21
  c22 = a21 * b12 + a22 * b22

  A = |a11 a12| B = |b11 b12|
      |a21 a22|     |b21 b22|
  A = |1 3|     B = |6 8|
      |7 5|         |4 2|

  c11 = (1 * 6) + (3 * 4) = 18
  c12 = (1 * 8) + (3 * 2) = 14
  c21 = (7 * 6) + (5 * 4) = 62
  c22 = (7 * 8) + (5 * 2) = 66

  |c11 c12|
  |c21 c22|

  |18 14|
  |62 66|
  ```

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.

  `T(n) = 4T(n/2) + cn`

  4T tells me that there are 4 sub problems.
  The 4 sub problems can be broken down into sub problems and again and again
  until the sub problems approach a base case.

  ```plaintext
                            n
                            |
                ------------------------------
              /         /         \          \
            n/2        n/2         n/2        n/2
          / /\ \
        /  /  \  \
      n/4 n/4 n/4 n/4
      .
      .
      .
    n/2^i
  ```

  ```plaintext
         lg n
  T(n) = sigma  4i * c(n/2^i)
         i = 0

              lg n
       = cn * sigma 2^i
              i=0

       = cn * (2^(lg n+1) - 1) / (2 - 1)

       = cn * (2*2^(lg n) - 1)

       = cn * (2n - 1)

       = 2cn^2 - cn
  ```

  Upper bound

  ```plaintext
  T(n) = 2cn^2 - cn
       <= 2cn^2
       = O(n^2)
  ```

  Lower bound

  ```plaintext
  T(n) = 2cn^2 - cn
       = cn^2 + (cn^2 - cn)
       >= cn^2
       = sigma(n^2)
  ```

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

  The master method is `T(n) = aT(n/b) + f(n)` where `a >= 1` and `b > 1`.

  ```plaintext
  T(n) = aT(n/b) + f(n)
  T(n) = 1T(n/2) + f(n)
  a = 1, b = 2

  f(n) = theta(n^(lg 1)) = theta(1)
  T(n) = theta(lg n)
  ```