# Problem Set 1: Introduction to Algorithms
###### tags: `MIT` `6.006` `algorithm`
:::success
- contributed by < `TYChan6028` >
- problem set: [Asymptotic complexity, recurrence relations, peak finding](https://ocw.mit.edu/courses/electrical-engineering-and-computer-science/6-006-introduction-to-algorithms-fall-2011/assignments/MIT6_006F11_ps1.pdf)
- course website: [MIT 6.006 Introduction to Algorithms, Fall 2011](https://ocw.mit.edu/courses/electrical-engineering-and-computer-science/6-006-introduction-to-algorithms-fall-2011/)
:::

## Problem 1-1. Asymptotic Practice
### a. Group 1:
\begin{eqnarray}
f_1(n) &=& n^{0.999999}\log n\\
&=& O(n^{0.999999}) \cdot O(n^{0.000001})\\
&=& O(n)
\end{eqnarray}

Since $\log n$ is asymptotically smaller than $n^c$ for all $c>0$, we can make the assumption that $c=0.000001$.

:::spoiler **Proof**: O(log n) < O(n^c)
:::warning
First, we know that $O(\log(\log n)) < O(\log n)$ because $O(\log n) < O(n)$. Therefore, there exists $N, c$ such that for all $n>N \land c>0$,
\begin{eqnarray}
\log(\log n) &<& c\log n\\
e^{\log(\log n)} &<& e^{c\log n} = e^{\log n^c}\\
\log n &<& n^c
\end{eqnarray}
*Reference*: [How to prove this: $\log n = O(n^c)$ [closed]](https://stackoverflow.com/questions/63381337/how-to-prove-this-log-n-onc)
:::

\begin{eqnarray}
f_2(n) &=& 10000000n=O(n)\\
f_3(n) &=& 1.000001^n=O(c^n)\\
f_4(n) &=& n^2=O(n^2)
\end{eqnarray}

Sorted in increasing order of asymptotic complexity, ==$f_1(n)<f_2(n)<f_4(n)<f_3(n)$==.

### b. Group 2:
\begin{eqnarray}
f_1(n) &=& 2^{2^{1000000}}=4^{1000000}=O(1)\\
f_2(n) &=& 2^{100000n}=O(2^n)\\
f_3(n) &=& {n\choose 2}=\frac{n!}{2!(n-2)!}\\
&=& \frac{n(n-1)}{2}\\
&=& O(n^2)\\
f_4(n) &=& n\sqrt{n}=O(n^{1.5})
\end{eqnarray}

Sorted in increasing order of asymptotic complexity, ==$f_1(n)<f_4(n)<f_3(n)<f_2(n)$==.
*Readings*: [Stirling's approximation for n!](https://en.wikipedia.org/wiki/Stirling%27s_approximation)

### c. Group 3:
\begin{eqnarray}
f_1(n) &=& n^{\sqrt{n}}=\sqrt{n}^{n}=O(\sqrt{n}^{n})\\
f_2(n) &=& 2^n=O(2^n)\\
f_3(n) &=& n^{10} \cdot 2^{n/2}=n^{10} \cdot (2^{1/2})^n=O(n^{10}) \cdot O(\sqrt{2}^n)=O(\sqrt{2}^n)\\
f_4(n) &=& \sum_{i=1}^{n}(i+1)=\sum_{i=1}^{n}i+\sum_{i=1}^{n}1=\frac{n(n+1)}{2}+n=O(n^2)
\end{eqnarray}

Sorted in increasing order of asymptotic complexity, ==$f_4(n)<f_3(n)<f_2(n)<f_1(n)$==.

:::danger
**Correction:** $f_4(n)<f_1(n)<f_3(n)<f_2(n)$
\begin{eqnarray}
f_1(n) &=& n^{\sqrt{n}}=n^{(n^{0.5})} \neq (n^n)^{0.5}=(n^{0.5})^n=\sqrt{n}^n\\
f_1(n) &=& n^{\sqrt{n}}=(2^{\lg n})^\sqrt{n}=2^{\sqrt{n}\lg n}\\
f_3(n) &=& n^{10} \cdot 2^{n/2}=(2^{\lg n})^{10} \cdot 2^{n/2}=2^{10\lg n+n/2}\\
&\because& O(2^{\sqrt{n}}) < O(\sqrt{2}^n)\\
&\Rightarrow& O(2^{\sqrt{n}\lg n}) < O(2^{10\lg n+n/2})\\
&\therefore& f_1(n) < f_3(n)
\end{eqnarray}
:::

## Problem 1-2. Recurrence Relation Resolution
### a.
For $c \leq 2$:
\begin{eqnarray}
T(x,c) &=& \Theta(x)\\
T(c,y) &=& \Theta(y)
\end{eqnarray}
The asymptotic complexity:
\begin{eqnarray}
T(x,y) &=& \Theta(x+y)+T(x/2,y/2)\\
&=& c(x+y)+T(x/2,y/2)\\
&=& c(x+y)+c(\frac{x+y}{2})+T(x/4,y/4)\\
&\vdots& \frac{x}{2^{i-1}} = 2 \Rightarrow x = 2^i \Rightarrow \lg x = i\\
&=& c(x+y)+c(\frac{x+y}{2})+\cdots+c(\frac{x+y}{2^{i-2}})+\Big[c(\frac{y}{2^{i-1}})+c(\frac{x}{2^{i-1}})\Big]\\
&=& c(x+y)(1+\frac{1}{2}+\cdots+\frac{1}{2^{i-1}})\\
&<& 2c(x+y)\\
&=& O(n)
\end{eqnarray}

Answer: ==2. $\Theta(n)$==

### b.
For $c \leq 2$:
\begin{eqnarray}
T(x,c) &=& \Theta(x)\\
T(c,y) &=& \Theta(y)
\end{eqnarray}
The asymptotic complexity:
\begin{eqnarray}
T(x,y) &=& \Theta(x)+T(x,y/2)\\
&=& cx+T(x,y/2)\\
&=& cx+cx+T(x,y/4)\\
&\vdots& \frac{y}{2^{i-1}} = 2 \Rightarrow y = 2^i \Rightarrow \lg y = i\\
&=& cx+cx+\cdots+cx+[cx]\\
&=& cn\cdot(\lg n-1)+cn\\
&=& O(n\lg n)
\end{eqnarray}

Answer: ==3. $\Theta(n\lg n)$==

### c.
For $c \leq 2$:
\begin{eqnarray}
T(x,c) &=& \Theta(x)\\
S(c,y) &=& \Theta(y)
\end{eqnarray}
The asymptotic complexity:
\begin{eqnarray}
T(x,y) &=& \Theta(x)+S(x,y/2)\\
&=& \Theta(x)+\Big[\Theta(y/2)+T(x/2,y/2)\Big]\\
&=& \Theta(x+y/2)+T(x/2,y/2)\\
&=& \Theta(x+y)+T(x/2,y/2)
\end{eqnarray}

Answer: ==2. $\Theta(n)$==

## Problem 1-3 & 1-4. Peak-Finding Correctness & Efficiency
### a. `algorithm1`

def algorithm1(problem, trace = None):
    # if it's empty, we're done 
    if problem.numRow <= 0 or problem.numCol <= 0:
        return None

    # the recursive subproblem will involve half the number of columns
    mid = problem.numCol // 2

    # information about the two subproblems
    (subStartR, subNumR) = (0, problem.numRow)
    (subStartC1, subNumC1) = (0, mid)
    (subStartC2, subNumC2) = (mid + 1, problem.numCol - (mid + 1))

    subproblems = []
    subproblems.append((subStartR, subStartC1, subNumR, subNumC1))
    subproblems.append((subStartR, subStartC2, subNumR, subNumC2))

    # get a list of all locations in the dividing column
    divider = crossProduct(range(problem.numRow), [mid])

    # find the maximum in the dividing column
    bestLoc = problem.getMaximum(divider, trace)

    # see if the maximum value we found on the dividing line has a better
    # neighbor (which cannot be on the dividing line, because we know that
    # this location is the best on the dividing line)
    neighbor = problem.getBetterNeighbor(bestLoc, trace)

    # this is a peak, so return it
    if neighbor == bestLoc:
        return bestLoc
   
    # otherwise, figure out which subproblem contains the neighbor, and
    # recurse in that half
    sub = problem.getSubproblemContaining(subproblems, neighbor)
    result = algorithm1(sub, trace)
    return problem.getLocationInSelf(sub, result)

#### 1. Correct?
==Yes==, `algorithm1` is correct.

#### 2. Worst-case runtime on a problem of size $n \times n$?
Important operations are listed below:

divider = crossProduct(range(problem.numRow), [mid])  # RUNTIME: O(n*1)

bestLoc = problem.getMaximum(divider, trace)  # RUNTIME: O(n)

neighbor = problem.getBetterNeighbor(bestLoc, trace)  # RUNTIME: O(1)

sub = problem.getSubproblemContaining(subproblems, neighbor)  # RUNTIME: O(1)

result = algorithm1(sub, trace)  # target

\begin{eqnarray}
T(n) &=& T(\frac{n}{2}) + O(n)\\
&=& T(\frac{n}{2}) + cn\\
&=& T(\frac{n}{4}) + c\frac{n}{2} + cn\\
&\vdots&\\
&=& T(1) + cn(1 + \frac{1}{2} + \dots + \frac{1}{2^{i-1}})\\
&=& O(n)
\end{eqnarray}

Worst-case runtime: ==2. $\Theta(n)$==

:::danger
**Correction:** $\Theta(n\log n)$
\begin{eqnarray}
T(n,m) &=& T(n,\frac{m}{2}) + O(n)\\
&=& T(n,\frac{m}{2}) + cn\\
&=& T(n,\frac{m}{4}) + cn + cn\\
&\vdots&\\
&=& O(n \log m)
\end{eqnarray}

Be careful when there are two independent variables in a given problem. They have to be considered separately. In this case, $O(n\log m)=O(n\log n)$ when $n \sim m$.
:::

### b. `algorithm2`

def algorithm2(problem, location=(0, 0), trace=None):
    # if it's empty, we're done
    if problem.numRow <= 0 or problem.numCol <= 0:
        return None

    nextLocation = problem.getBetterNeighbor(location, trace)

    if nextLocation == location:
        # there is no better neighbor, so return this peak
        return location
    else:
        # there is a better neighbor, so move to the neighbor and recurse
        return algorithm2(problem, nextLocation, trace)

#### 1. Correct?
==Yes==, `algorithm2` is correct.

#### 2. Worst-case runtime on a problem of size $n \times n$?
`getBetterNeighbor()` traverses through its neighbors one step at a time, selecting the largest neighbor as its next location. Consider a zig-zagged pattern (faster than the worst-case)

[[1, 0, 11, 12, 13],
 [2, 0, 10,  0, 14],
 [3, 0,  9,  0, 15],
 [4, 0,  8,  0, 16],
 [5, 6,  7,  0, 17]]

which takes $n\lceil \frac{m}{2} \rceil + \lfloor \frac{m}{2} \rfloor$ steps to find a peak, its time complexity is $O(nm)$. Therefore, the worst-case runtime for a problem of size $n \times n$ is ==5. $\Theta(n^2)$==.

### c. `algorithm3`

def algorithm3(problem, bestSeen=None, trace=None):
    # if it's empty, we're done
    if problem.numRow <= 0 or problem.numCol <= 0:
        return None

    midRow = problem.numRow // 2
    midCol = problem.numCol // 2

    # first, get the list of all subproblems
    subproblems = []

    (subStartR1, subNumR1) = (0, midRow)
    (subStartR2, subNumR2) = (midRow + 1, problem.numRow - (midRow + 1))
    (subStartC1, subNumC1) = (0, midCol)
    (subStartC2, subNumC2) = (midCol + 1, problem.numCol - (midCol + 1))

    subproblems.append((subStartR1, subStartC1, subNumR1, subNumC1))
    subproblems.append((subStartR1, subStartC2, subNumR1, subNumC2))
    subproblems.append((subStartR2, subStartC1, subNumR2, subNumC1))
    subproblems.append((subStartR2, subStartC2, subNumR2, subNumC2))

    # find the best location on the cross (the middle row combined with the
    # middle column)
    cross = []

    cross.extend(crossProduct([midRow], range(problem.numCol)))
    cross.extend(crossProduct(range(problem.numRow), [midCol]))

    crossLoc = problem.getMaximum(cross, trace)
    neighbor = problem.getBetterNeighbor(crossLoc, trace)

    # update the best we've seen so far based on this new maximum
    if bestSeen is None or problem.get(neighbor) > problem.get(bestSeen):
        bestSeen = neighbor

    # return if we can't see any better neighbors
    if neighbor == crossLoc:
        return crossLoc

    # figure out which subproblem contains the largest number we've seen so
    # far, and recurse
    sub = problem.getSubproblemContaining(subproblems, bestSeen)
    newBest = sub.getLocationInSelf(problem, bestSeen)
    result = algorithm3(sub, newBest, trace)
    return problem.getLocationInSelf(sub, result)

#### 1. Correct?
==Yes==, `algorithm3` is correct.

:::danger
**Correction:** `algorithm3` is incorrect.
Consider a possible $3 \times 3$ subproblem `sub` shown below:

    0 0 4 | 3
    0 0 0 | x
    0 1 0 | x ...
    ------- x
    x 2 x x x
       ...

In this case, `1` would be returned as a peak because `2` would be outside of `sub`'s dimensions when the recursive function call `algorithm3(sub, newBest, trace)` is made.
:::

#### 2. Worst-case runtime on a problem of size $n \times n$?
Important operations are listed below:

cross.extend(crossProduct([midRow], range(problem.numCol)))  # RUNTIME: O(m+m)
cross.extend(crossProduct(range(problem.numRow), [midCol]))  # RUNTIME: O(n+n)

crossLoc = problem.getMaximum(cross, trace)  # RUNTIME: O(n+m)

result = algorithm3(sub, newBest, trace)  # target

\begin{eqnarray}
T(n,m) &=& T(\frac{n}{2},\frac{m}{2}) + O(n+m)\\
&=& T(\frac{n}{2},\frac{m}{2}) + c(n+m)\\
&=& T(\frac{n}{4},\frac{m}{4}) + c(\frac{n+m}{2}) + c(n+m)\\
&\vdots&\\
&=& T(1) + c(n+m)(1+\frac{1}{2}+\dots+\frac{1}{2^{i-1}})\\
&<& 2c(n+m)\\
&=& O(n+m)
\end{eqnarray}

Worst-case runtime: ==2. $\Theta(n)$==

### d. `algorithm4`

def algorithm4(problem, bestSeen=None, rowSplit=True, trace=None):
    # if it's empty, we're done
    if problem.numRow <= 0 or problem.numCol <= 0:
        return None

    subproblems = []
    divider = []

    if rowSplit:
        # the recursive subproblem will involve half the number of rows
        mid = problem.numRow // 2

        # information about the two subproblems
        (subStartR1, subNumR1) = (0, mid)
        (subStartR2, subNumR2) = (mid + 1, problem.numRow - (mid + 1))
        (subStartC, subNumC) = (0, problem.numCol)

        subproblems.append((subStartR1, subStartC, subNumR1, subNumC))
        subproblems.append((subStartR2, subStartC, subNumR2, subNumC))

        # get a list of all locations in the dividing column
        divider = crossProduct([mid], range(problem.numCol))
    else:
        # the recursive subproblem will involve half the number of columns
        mid = problem.numCol // 2

        # information about the two subproblems
        (subStartR, subNumR) = (0, problem.numRow)
        (subStartC1, subNumC1) = (0, mid)
        (subStartC2, subNumC2) = (mid + 1, problem.numCol - (mid + 1))

        subproblems.append((subStartR, subStartC1, subNumR, subNumC1))
        subproblems.append((subStartR, subStartC2, subNumR, subNumC2))

        # get a list of all locations in the dividing column
        divider = crossProduct(range(problem.numRow), [mid])

    # find the maximum in the dividing row or column
    bestLoc = problem.getMaximum(divider, trace)
    neighbor = problem.getBetterNeighbor(bestLoc, trace)

    # update the best we've seen so far based on this new maximum
    if bestSeen is None or problem.get(neighbor) > problem.get(bestSeen):
        bestSeen = neighbor

    # return when we know we've found a peak
    if neighbor == bestLoc and problem.get(bestLoc) >= problem.get(bestSeen):
        return bestLoc

    # figure out which subproblem contains the largest number we've seen so
    # far, and recurse, alternating between splitting on rows and splitting
    # on columns
    sub = problem.getSubproblemContaining(subproblems, bestSeen)
    newBest = sub.getLocationInSelf(problem, bestSeen)
    result = algorithm4(sub, newBest, not rowSplit, trace)
    return problem.getLocationInSelf(sub, result)

#### 1. Correct?
==Yes==, `algorithm4` is correct.

#### 2. Worst-case runtime on a problem of size $n \times n$?
Important operations are listed below:

divider = crossProduct(...)  # RUNTIME: O(m) or O(n)

bestLoc = problem.getMaximum(divider, trace)  # RUNTIME: O(m) or O(n)

result = algorithm4(sub, newBest, not rowSplit, trace)  # target

\begin{eqnarray}
T(n,m) &=& T(\frac{n}{2},m) + O(m)\\
&=& T(\frac{n}{2},\frac{m}{2}) + O(n) + O(m)\\
&=& T(\frac{n}{2},\frac{m}{2}) + O(n+m)
\end{eqnarray}

Same as `algorithm3`, worst-case runtime: ==2. $\Theta(n)$==

## Problem 1-5. Peak-Finding Proof
Proof of correctness for the *most efficient correct algorithm*: `algorithm4`.

We wish to show that `algorithm4` will always return a peak, as long as the problem
is not empty. To that end, we wish to prove the following two statements:

#### 1. If the peak problem is not empty, then `algorithm4` will always return a location.
1. Say that we start with a problem of size $n \times m$. The recursive subproblem examined by `algorithm4` would have one of the following dimensions:
1. $\lfloor n/2 \rfloor \times m$
2. $(n - \lfloor n/2 \rfloor - 1) \times m$
3. $n \times \lfloor m/2 \rfloor$
4. $n \times (m - \lfloor m/2 \rfloor - 1)$
2. The number of rows / columns in the problem decreases with each recursive call as long as $n > 0$ or $m > 0$. So `algorithm4` either returns a location at some point, or eventually examines a subproblem with a non-positive number of rows / columns.
3. The only way for the number of rows / columns to become strictly negative, according to lines `15` & `30`, is to have $n = 0$ or $m = 0$ at some point. So if `algorithm4` doesn’t return a location, it must eventually examine an empty subproblem.
4. Just prior to `algorithm4` examining an empty subproblem, it must either examine a subproblem of size $n × 1$, $n × 2$, $1 × m$ or $2 × m$.
5. If the problem is of size $n × 1$ or $1 × m$, then calculating the maximum of the central row / column is equivalent to calculating the maximum of the entire problem. Hence, the maximum found must be a peak $\rightarrow$ returns location.
6. If the problem has dimensions $n × 2$ or $2 × m$, then there are two possibilities:
1. the maximum of the central row / column is a peak $\rightarrow$ returns location
2. found a strictly better neighbor in the other row / column $\rightarrow$ reduces to Step 5.
7. So `algorithm4` can never recurse into an empty subproblem, and therefore `algorithm4` must eventually return a location.

#### 2. If algorithm1 returns a location, it will be a peak in the original problem.
1. If `algorithm4` returns a location $(r_1,c_1)$, then that location must
1. have been a peak within some recursive subproblem
2. be the largest value seen yet
2. Assume, for the sake of contradiction, that $(r_1,c_1)$ is not a peak within the original problem.
1. As the location $(r_1, c_1)$ is passed up the chain of recursive calls, it must eventually reach a level where it stops being a peak.
2. At that level, there exists a location `neighbor` adjacent to the location $(r_1, c_1)$ such that $val(r_1, c_1) < val($`neighbor`$)$.
3. Since $(r_1, c_1)$ is the largest value seen yet, it must be that $val($`neighbor`$) \leq val(r_1, c_1)$.
4. Hence, we have the following chain of inequalities:
$val(r_1, c_1) < val($`neighbor`$) \leq val(r_1, c_1) \Longrightarrow val(r_1, c_1) < val(r_1, c_1)$
A contradiction.
3. Assume, for the sake of contradiction, that $(r_1,c_1)$ is not the largest value seen yet.
1. Let level $l_k$ be the level from which $val(r_1, c_1)$ was returned, then $l_k$ must be the last level of recursion.
2. Since the location $(r_1, c_1)$ is a peak on level $l_k$, it has the largest value in the dividing row / column. Therefore, the location `bestSeen` must be in either one of the subproblems.
3. We could then call `algorithm4` with the subproblem that contains location `bestSeen` and recurse one level deeper into level $l_{k+1}$. But level $l_k$ is the last level of recursion, hence we have a contradiction.
4. So `algorithm4` must return a location which is a peak within some recursive subproblem and the largest value seen yet, making it a peak in the original problem.

## Problem 1-6. Peak-Finding Counterexamples
#### `algorithm3`:

problemMatrix = [
    [0, 0, 9, 8, 0, 0, 0],
    [0, 0, 0, 0, 0, 0, 0],
    [0, 1, 0, 0, 0, 0, 0],
    [0, 2, 0, 0, 0, 0, 0],
    [0, 0, 0, 0, 0, 0, 0],
    [0, 0, 0, 0, 0, 0, 0],
    [0, 0, 0, 0, 0, 0, 0]
]