I never finished these. Consider checking out Alec Li’s notes and Jeffrey Shen’s final cheatsheet.

Asymptotic Bound #

Master Theorem #

$$\begin{aligned} T(n) &= \overbrace{a\cdot T\left(\frac n b\right)}^\text{Divide into $a$ parts $\sim\ b^{-1}$} + \overbrace{C \cdot n^d}^{\text{Combining Work}} \\ \text{Level 0: } & n^d \\ \text{Level 1: } & n^d \frac a {b^d} \\ \text{Level 2: } & n^d \left(\frac a {b^d}\right)^2 \\ & \vdots \\ \text{Level }k:\ & n^d \left(\frac a {b^d}\right)^k \qquad \text{(Base: } \frac n {b^k} \leq 1 \Longrightarrow k = \log_b n)\\ \text{Total Work:}\ & n^d \cdot \sum_{i=0}^k \left(\frac a {b^d}\right)^i \\ \therefore\ T(n) &= \begin{cases} \Theta (n^d) & \dfrac a {b^d} < 1\ \equiv\ d>\log_b a\\ \Theta (n^d \cdot \log n) & \dfrac a {b^d} = 1\ \equiv\ d= \log_b a \\ \Theta (n^{\log_b a}) & \dfrac a {b^d} > 1\ \equiv\ d < \log_b a \end{cases} \end{aligned}$$

Representation #

• $1 + p + p^2 + \cdots + p^k = \dfrac{p^{k+1}-1}{p-1}$

• Log facts

  • Change log base: $\log_b N = \dfrac{\log_a N}{\log_a b} \implies \log_a N = \log_b N \cdot \log_a b$
  • Represent $x$ using $\log$ of an arbitrary base: $x = b^{\log_b x}$
  • Expanding log division: $\log_a \left(\dfrac{x}{y}\right) = \log_a x - \log_a y$
  • Definitions:
    1. The power to which you need to raise 2 in order to obtain $N$
    2. Going backward, it can also be seen as the number of times you must halve N to get down to 1: $\lceil \log N \rceil$
    3. Number of bits in the binary representation of N: $\lceil \log(N+1)\rceil$
    4. Depth of a complete binary tree with N nodes: $\lfloor \log N \rfloor$
    5. $1 + \frac 1 2 + \frac 1 3 + \cdots + \frac 1 N = \ln N + \gamma$
  • Show $\log (n!) = \Theta (n \log n)$

    Upper: $$\begin{aligned}n! &< n^n\\ \log n! &< \log n^n \\ &=\mathcal O (\log n^n) \\ &=\mathcal O(n \log n) \end{aligned}$$

    Lower: $$\begin{aligned}n! &> \frac n 2 ^{\frac n 2}\\ \log n! &> \log (\frac n 2 ^{\frac n 2})\\ &=\Omega \left(\frac n 2 \log \frac n 2 \right)\\ &= \Omega (n \log n)\end{aligned}$$

• Fast Integer exponentiation using repeated squaring

  • Naive takes $\mathcal O(n)$ multiplies: $k^{n} = n\cdot n\cdot \dots n$
  • Base-2 decomp takes $\mathcal O(\lceil\log_2 k\rceil)$:
    • E.x. $k=71: 9^{71} = 9^{64} \cdot9^4\cdot9^2\cdot 9^1$
    • Use base-2 since $\log_{b} x = \log_{2} x / \log_{2} b$ is minimized when $b=2$.

• Show that in any base $b\ge 2$, the sum of any three single-digit numbers is at most two digits long.

  $$\begin{aligned} \text{[sum of 3 digits in base b]} &\leq \text{[2-digit number]}\\ \text{argmax } x_b + y_b + z_b &\leq b\cdot\alpha + \beta\\ 3(b-1) &\leq b^2-1 \qquad(1)\\ \text{Base:}\qquad\quad 3(2-1)&\leq 2^2 -1\\ 3 &\leq 3\ \Box \\ \text{Hyp: }\quad3(k+1-1)&\leq (k+1)^2 -1\\ 3k&\leq k^2+2k\\ k &\leq k^2\ \Box \end{aligned}$$

  • $(1)$: $k$ digits in base $b$ can represent every number in  $[0, b^k) \equiv [b^k-1]$

• Show that any binary integer is at most four times as long as the corresponding decimal integer.

  For any decimal (base-10) integer $x$ of length $n$, we know the number of bits to represent in base $b$ is $\lceil \log_b 10^n\rceil$; therefore… $$\begin{aligned} \text{[length in base-2]} &\leq 4\cdot \text{[length in base-10]}\\ \lceil \log_2 (x+1) \rceil &\leq 4\cdot \lceil \log_{10} (x+1) \rceil\\ \log_2 10^n &\leq 4\cdot \log_{10} 10^n\\ &\leq 4\cdot n\\ 2^{\log_2 10^n}&\leq 2^{4\cdot n}\\ 10^n &\leq 16^n\ \Box\end{aligned}$$

• Show that any d-ary tree with n nodes must have a depth of $Ω(\log n/ \log d)$

  $$\begin{aligned} n &= \sum_{i=1}^f d^i = d^1 + d^2+\dots+d^f\\ &= d^f-1\\ \log_d n+1 &= \log_d d^f\\ \log_dn+1 &= f\\ \Longrightarrow f &= \lfloor\log_d n\rfloor \\ &= \Omega \frac{\log n}{\log d}\end{aligned}$$

Fast Fourier Transform (FFT) #

Goal: efficiently multiply two polynomials $A(x), B(x)$, of degrees $d_a, d_b$, in $\mathcal O(n\log n)$ time

1. Selection: Find points (roots of unity) $x_0, x_1, \dots, x_{n-1}$
   • $n = 2^{\lceil \log_2 (d_a + d_b + 1) \rceil} \le 2^{\lceil \log_2 (2d + 1) \rceil} $ where $d := \text{max}(d_a, d_b)$
     • Final polynomial $C(x)$ has maximum degree of $2d$, so we evaluate at $2d+1$ points
   • Zero-pad $A(x), B(x)$ with $n - d_a, n-d_b$ zeros respectively
2. Evaluate two polynomials at a set of points : $\mathcal O(n \log n)$
3. Multiply the evaluated points (for every point $w$ evaluated, compute $C(w) = A(w) \cdot B(w)$ : $\mathcal O(n)$
4. Interpolate: Take the resulting points and recover the polynomial they define with IFFT: $\mathcal O(n \log n)$

• Exam tips
  • Use FFT as a blackbox algorithm for polynomial multiplication
    • Frame problem as a polynomial problem, e.x. through cross-correlation
  • Anything better than $\mathcal O (n\log n)$ i.e. $\mathcal O(n^2)$ can be done with FFT

Depth First Search (DFS) #

Graph Theory #

Dijkstra #

Shortest Paths #

Divide and Conquer (D&C) #

Minimum Spanning Tree (MST) #

Bellman-Ford #

Huffman Encoding #

Union Find #

Quickselect #