# Exam Review

SOLUTIONS TO THE MIDTERM REVIEW HERE

## Longest Common Substring

Given two strings A and B, this will find the length of the longest common substring. (hit enter in the text box to force it to update). The arrows point in the direction of the subproblem used to calculate that cell.

TODO: pseudocode

Here’s approximately the code I used for the above table:

function LCS(X, Y)
var d = new Array(X.length+1);
var i, j;
for(i = 0; i < d.length; ++i) {
d[i] = new Array(Y.length+1);

d[i][0] = 0;
for(j = 0; j < d[i].length; ++j) {
d[0][j] = 0;
}
}

for(i = 0; i < X.length; i++) {
for(j = 0; j < Y.length; j++) {
if(a[i] == b[j]) {
d[i+1][j+1] = d[i][j] + 1;
} else if(d[i][j+1] >= d[i+1][j]) {
d[i+1][j+1] = d[i][j+1];
} else {
d[i+1][j+1] = d[i+1][j];
}
}
}


## Quicksort

For the following questions, assume that the pivot is always chosen to be the last element in the partition.

a. What kind of input causes worst case behavior?
b. What is the recurrence for this worst case behavior.
c. What is the solution to the worst-case recurrence?
d. Is there anyway to mitigate the worst-case?

Given that the pivot is always chosen to be the last element in the partition, the worst case is encountered for arrays that are already sorted.

The recurrence for the worst case is $T(n) = T(n-1) + \Theta(n)$, where $\Theta(n)$ is the time to partition.

To solve the recurrence, just unroll it a few steps: $$T(n) = T(n-1) + \Theta(n)$$ $$T(n) = T(n-2) + \Theta(n) + \Theta(n)$$ Continuing in this fashion yields $T(n) = \Theta(n^2)$.

The book suggests using the median of the first, middle, and last elements. Alternatively, one can average the first and last elements. Choosing a random element as the pivot also helps. There's a detailed discussion on the Wikipedia article.

## Asymptotic Notation

a. Formally prove the transitivity of $\Omega$, e.g. if $f \in \Omega(g)$ and $g \in \Omega(h)$ then $f \in \Omega(h)$.

Given:
(1) $f \in \Omega(g) \rightarrow c_1 g \leq f$ for $n \geq n_0$ and some $c_1$.
(2) $g \in \Omega(h) \rightarrow c_2 h \leq g$ for $n \geq n_1$ and some $c_2$.

Since $c_1$ is an arbitrary constant, without loss of generality we have $c_2 h \leq g \leq c_1 g$, which allows us to write $c_2 c_1 h \leq c_1 g \leq f$
Let $n_3 = \max(n_0, n_1)$, and $c_3 = c_2 c_1$, hence $c_3 h \leq f$ for $n \geq n_3$ which is the formal definition of $f \in \Omega(h)$.

b. For the general case (e.g. arbitrary $f$ and $g$), prove or disprove $f \not\in \omega(g) \rightarrow f \in O(g)$

Since $c_1 g \not\lt f$ for $n \geq n_0$, it must be that $f \leq c_1g$ for $n \geq n_0$ which, by definition, implies that $f \in O(g)$.

## Recurrences

Do not use the Master method for the following problems.

a. Show that if $T(n) = 3T(n/2) + n^2$, then $T(n) \in O(n^2)$.

Plugging in… remember that since $c$ is an arbitrary constant, it can consume other constants.

$T(n) \leq 3(cn^2/2) + n^2$

$T(n) \leq cn^2 + n^2$

$T(n) \leq cn^2$

Hence $T(n) \in O(n^2)$.

b. Show that if $T(n) = T(n/2) + 2^n$, then $T(n) \in O(2^n)$.

$T(n) \leq c2^n / 2 + 2^n$

$T(n) \leq c2^n$

Hence $T(n) \in O(2^n)$.

c. Prove $T(n) = 16T(n/4) + n \rightarrow T(n) \in O(n^2)$.

$T(n) \leq 16(cn^2 / 4) + n$

$T(n) \leq cn^2 + n$

Hence $T(n) \in O(n^2)$.

d. Prove $T(n) = 3T(n/3) + \sqrt{n} \rightarrow T(n) \in O(n)$.

$T(n) \leq 3(cn/3) + \sqrt{n}$

$T(n) \leq cn + \sqrt{n}$

Hence $T(n) \in O(n)$.