# 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:

## Exercise 1.1-4

    How are the shortest path and traveling-salesman problems given above similar?

        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.

    How are they different?

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


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

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


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


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

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

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

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

## Exercise 4.3-2 from the textbook (10 marks)

Show that the solution of `T(n) = T([n/2]) + 1` is `O(lg n)`

Big O notation says:

> The function `f(n) = O(g(n))`,
> if there exists positive constants `c` and `n0`
> such that `0 <= f(n) <= c*g(n)` for all `n >= n0`.


```plaintext
For this equation `T(n) = T([n/2]) + 1` to be bounded by `O(lg n)`
we would have to prove that the following is true.

We can also use the substitution method to make a guess as the starting point.
Since we are trying to prove for `O(lg n)` we can start with this.

  0 <= f(n) <= c * lg(n/2) + 1

This isn't enough for us to make the proof so we can try to introduce `d` where
`d >= 1`. This allows us to rewrite the above as:

  0 <= f(n) <= c * lg(n/2) + 1 - d
  if d = 1 then we can drop the constant.
  0 <= f(n) <= c * lg(n/2)

This allows us to make the claim that this function is bounded by `O(lg n)`.
```

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

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