$$\lim_{x \to a} f(x) = L$$ means: For every $\varepsilon > 0$, there exists $\delta > 0$ such that $$0 < |x - a| < \delta \implies |f(x) - L| < \varepsilon$$

$$\lim_{x \to 0} \frac{\sin x}{x} = 1$$ $$\lim_{x \to 0} \frac{1 - \cos x}{x} = 0$$ $$\lim_{x \to 0} \frac{e^x - 1}{x} = 1$$ $$\lim_{x \to \infty} \left(1 + \frac{1}{x}\right)^x = e$$

If $\lim_{x \to a} f(x) = \lim_{x \to a} g(x) = 0$ or $\pm\infty$, then: $$\lim_{x \to a} \frac{f(x)}{g(x)} = \lim_{x \to a} \frac{f'(x)}{g'(x)}$$ (provided the right side exists)

$$f'(x) = \lim_{h \to 0} \frac{f(x + h) - f(x)}{h}$$ Alternative notation: $\frac{df}{dx}$, $\frac{d}{dx}f(x)$, $D_x f$

Power Rule: $\frac{d}{dx}(x^n) = nx^{n-1}$ Product Rule: $(fg)' = f'g + fg'$ Quotient Rule: $\left(\frac{f}{g}\right)' = \frac{f'g - fg'}{g^2}$ Chain Rule: $\frac{d}{dx}f(g(x)) = f'(g(x)) \cdot g'(x)$

$$\frac{d}{dx}(\sin x) = \cos x \qquad \frac{d}{dx}(\cos x) = -\sin x$$ $$\frac{d}{dx}(e^x) = e^x \qquad \frac{d}{dx}(\ln x) = \frac{1}{x}$$ $$\frac{d}{dx}(\tan x) = \sec^2 x \qquad \frac{d}{dx}(\arctan x) = \frac{1}{1+x^2}$$

$$\int_a^b f(x)\,dx = \lim_{n \to \infty} \sum_{i=1}^n f(x_i^*) \Delta x$$ where $\Delta x = \frac{b-a}{n}$ and $x_i^* \in [x_{i-1}, x_i]$

Part 1: If $F(x) = \int_a^x f(t)\,dt$, then $F'(x) = f(x)$ Part 2: If $F'(x) = f(x)$, then $$\int_a^b f(x)\,dx = F(b) - F(a)$$

Substitution: $\int f(g(x))g'(x)\,dx = \int f(u)\,du$ Integration by Parts: $\int u\,dv = uv - \int v\,du$ Partial Fractions: Decompose rational functions

$$\int x^n\,dx = \frac{x^{n+1}}{n+1} + C \quad (n \neq -1)$$ $$\int \frac{1}{x}\,dx = \ln|x| + C$$ $$\int e^x\,dx = e^x + C$$ $$\int \sin x\,dx = -\cos x + C$$ $$\int \frac{1}{\sqrt{1-x^2}}\,dx = \arcsin x + C$$

A sequence $\{a_n\}$ converges to $L$ if: $$\lim_{n \to \infty} a_n = L$$ Common limits: $$\lim_{n \to \infty} \frac{1}{n} = 0 \qquad \lim_{n \to \infty} \sqrt[n]{n} = 1$$ $$\lim_{n \to \infty} \left(1 + \frac{1}{n}\right)^n = e$$

Geometric Series: $\sum_{n=0}^{\infty} ar^n = \frac{a}{1-r}$ if $|r| < 1$ p-Series: $\sum_{n=1}^{\infty} \frac{1}{n^p}$ converges if $p > 1$ Ratio Test: If $\lim_{n \to \infty} \left|\frac{a_{n+1}}{a_n}\right| = L$ then series converges if $L < 1$

$$f(x) = \sum_{n=0}^{\infty} \frac{f^{(n)}(a)}{n!}(x-a)^n$$ Common Taylor series: $$e^x = \sum_{n=0}^{\infty} \frac{x^n}{n!}$$ $$\sin x = \sum_{n=0}^{\infty} \frac{(-1)^n x^{2n+1}}{(2n+1)!}$$ $$\ln(1+x) = \sum_{n=1}^{\infty} \frac{(-1)^{n+1} x^n}{n}$$

Critical points: $f'(x) = 0$ or $f'(x)$ undefined Second derivative test: - If $f''(c) > 0$: local minimum at $x = c$ - If $f''(c) < 0$: local maximum at $x = c$ - If $f''(c) = 0$: test inconclusive

If variables $x$ and $y$ are related by an equation and vary with time $t$: $$\frac{dy}{dt} = \frac{dy}{dx} \cdot \frac{dx}{dt}$$ Example: Area of circle $A = \pi r^2$ $$\frac{dA}{dt} = 2\pi r \frac{dr}{dt}$$

Arc length: $L = \int_a^b \sqrt{1 + (f'(x))^2}\,dx$ Surface area (revolution about x-axis): $$S = 2\pi \int_a^b f(x)\sqrt{1 + (f'(x))^2}\,dx$$

$$\frac{\partial f}{\partial x} = \lim_{h \to 0} \frac{f(x+h,y) - f(x,y)}{h}$$ Mixed partials theorem (Clairaut): $$\frac{\partial^2 f}{\partial x \partial y} = \frac{\partial^2 f}{\partial y \partial x}$$ (if both are continuous)

$$\nabla f = \left( \frac{\partial f}{\partial x}, \frac{\partial f}{\partial y}, \frac{\partial f}{\partial z} \right)$$ Directional derivative: $$D_{\mathbf{u}} f = \nabla f \cdot \mathbf{u}$$ Maximum rate of change: $|\nabla f|$

If $z = f(x,y)$ where $x = g(t)$ and $y = h(t)$: $$\frac{dz}{dt} = \frac{\partial z}{\partial x}\frac{dx}{dt} + \frac{\partial z}{\partial y}\frac{dy}{dt}$$ General form: $$\frac{\partial z}{\partial t} = \sum_{i} \frac{\partial z}{\partial x_i}\frac{\partial x_i}{\partial t}$$

$$\iint_R f(x,y) \, dA = \int_a^b \int_{c(x)}^{d(x)} f(x,y) \, dy \, dx$$ Fubini's Theorem: For continuous $f$, $$\int_a^b \int_c^d f(x,y) \, dy \, dx = \int_c^d \int_a^b f(x,y) \, dx \, dy$$

$$\iint_R f(x,y) \, dx \, dy = \iint_S f(x(u,v), y(u,v)) |J| \, du \, dv$$ Jacobian: $J = \frac{\partial(x,y)}{\partial(u,v)} = \begin{vmatrix} \frac{\partial x}{\partial u} & \frac{\partial x}{\partial v} \\ \frac{\partial y}{\partial u} & \frac{\partial y}{\partial v} \end{vmatrix}$

Cylindrical: $\begin{cases} x = r\cos\theta \\ y = r\sin\theta \\ z = z \end{cases}$ $dV = r \, dr \, d\theta \, dz$ Spherical: $\begin{cases} x = \rho\sin\phi\cos\theta \\ y = \rho\sin\phi\sin\theta \\ z = \rho\cos\phi \end{cases}$ $dV = \rho^2\sin\phi \, d\rho \, d\phi \, d\theta$

$$\int_C \mathbf{F} \cdot d\mathbf{r} = \int_a^b \mathbf{F}(\mathbf{r}(t)) \cdot \mathbf{r}'(t) \, dt$$ Conservative field: $\nabla \times \mathbf{F} = \mathbf{0}$ If $\mathbf{F} = \nabla f$: $\int_C \mathbf{F} \cdot d\mathbf{r} = f(B) - f(A)$

$$\oint_C (P \, dx + Q \, dy) = \iint_D \left( \frac{\partial Q}{\partial x} - \frac{\partial P}{\partial y} \right) dA$$ Area formula: $A = \frac{1}{2} \oint_C (x \, dy - y \, dx)$

$$\text{div } \mathbf{F} = \nabla \cdot \mathbf{F} = \frac{\partial P}{\partial x} + \frac{\partial Q}{\partial y} + \frac{\partial R}{\partial z}$$ $$\text{curl } \mathbf{F} = \nabla \times \mathbf{F} = \begin{vmatrix} \mathbf{i} & \mathbf{j} & \mathbf{k} \\ \frac{\partial}{\partial x} & \frac{\partial}{\partial y} & \frac{\partial}{\partial z} \\ P & Q & R \end{vmatrix}$$

$$\frac{dy}{dx} = f(x)g(y)$$ Solution method: $$\int \frac{dy}{g(y)} = \int f(x) \, dx$$

$$\frac{dy}{dx} + P(x)y = Q(x)$$ Integrating factor: $\mu(x) = e^{\int P(x) \, dx}$ Solution: $y = \frac{1}{\mu(x)}\left[\int \mu(x)Q(x) \, dx + C\right]$

$$M(x,y) \, dx + N(x,y) \, dy = 0$$ Exact if: $\frac{\partial M}{\partial y} = \frac{\partial N}{\partial x}$ Solution: Find $F(x,y)$ where $\frac{\partial F}{\partial x} = M$ and $\frac{\partial F}{\partial y} = N$

$$ay'' + by' + cy = 0$$ Characteristic equation: $ar^2 + br + c = 0$ Solutions: - If $r_1 \neq r_2$: $y = c_1e^{r_1x} + c_2e^{r_2x}$ - If $r_1 = r_2 = r$: $y = (c_1 + c_2x)e^{rx}$ - If $r = \alpha \pm \beta i$: $y = e^{\alpha x}(c_1\cos(\beta x) + c_2\sin(\beta x))$

For $ay'' + by' + cy = f(x)$: - If $f(x) = e^{\alpha x}$: try $y_p = Ae^{\alpha x}$ - If $f(x) = \text{polynomial}$: try polynomial of same degree - If $f(x) = \sin(\alpha x)$ or $\cos(\alpha x)$: try $y_p = A\cos(\alpha x) + B\sin(\alpha x)$

For $y'' + P(x)y' + Q(x)y = f(x)$ If $y_1, y_2$ are homogeneous solutions: $$y_p = -y_1\int\frac{y_2f}{W}dx + y_2\int\frac{y_1f}{W}dx$$ Wronskian: $W = y_1y_2' - y_2y_1'$

$$\mathcal{L}\{f(t)\} = F(s) = \int_0^{\infty} e^{-st}f(t) \, dt$$ Properties: - $\mathcal{L}\{af + bg\} = a\mathcal{L}\{f\} + b\mathcal{L}\{g\}$ - $\mathcal{L}\{f'\} = sF(s) - f(0)$ - $\mathcal{L}\{f''\} = s^2F(s) - sf(0) - f'(0)$

$$\mathcal{L}\{1\} = \frac{1}{s}$$ $$\mathcal{L}\{t^n\} = \frac{n!}{s^{n+1}}$$ $$\mathcal{L}\{e^{at}\} = \frac{1}{s-a}$$ $$\mathcal{L}\{\sin(at)\} = \frac{a}{s^2+a^2}$$ $$\mathcal{L}\{\cos(at)\} = \frac{s}{s^2+a^2}$$

$$\mathbf{x}' = A\mathbf{x} + \mathbf{b}$$ Solution: $\mathbf{x}(t) = e^{At}\mathbf{x}_0 + \int_0^t e^{A(t-\tau)}\mathbf{b}(\tau) \, d\tau$ Matrix exponential: $e^{At} = \sum_{n=0}^{\infty} \frac{A^n t^n}{n!}$

If $A\mathbf{v} = \lambda\mathbf{v}$, then $\mathbf{x} = \mathbf{v}e^{\lambda t}$ is a solution General solution: $$\mathbf{x} = c_1\mathbf{v}_1e^{\lambda_1 t} + c_2\mathbf{v}_2e^{\lambda_2 t} + \cdots$$

Vectors $\mathbf{v}_1, \mathbf{v}_2, \ldots, \mathbf{v}_n$ are linearly independent if: $$c_1\mathbf{v}_1 + c_2\mathbf{v}_2 + \cdots + c_n\mathbf{v}_n = \mathbf{0} \implies c_1 = c_2 = \cdots = c_n = 0$$ Matrix form: $A\mathbf{x} = \mathbf{0}$ has only trivial solution

Basis: linearly independent set that spans the space $\dim(V) = $ number of vectors in any basis If $\dim(V) = n$, then any $n$ linearly independent vectors form a basis

$$A\mathbf{v} = \lambda\mathbf{v} \quad (\mathbf{v} \neq \mathbf{0})$$ Characteristic polynomial: $\det(A - \lambda I) = 0$ Eigenspace: $E_{\lambda} = \{\mathbf{v} : A\mathbf{v} = \lambda\mathbf{v}\} = \text{null}(A - \lambda I)$

$$A = PDP^{-1}$$ where $D$ is diagonal $P = [\mathbf{v}_1 \, \mathbf{v}_2 \, \cdots \, \mathbf{v}_n]$ (eigenvectors) $D = \text{diag}(\lambda_1, \lambda_2, \ldots, \lambda_n)$ (eigenvalues) $A^k = PD^k P^{-1}$

$$\text{tr}(A) = \lambda_1 + \lambda_2 + \cdots + \lambda_n$$ $$\det(A) = \lambda_1 \times \lambda_2 \times \cdots \times \lambda_n$$ If $A$ symmetric: all eigenvalues real, eigenvectors orthogonal

$$\langle \mathbf{u}, \mathbf{v} \rangle = \mathbf{u}^T\mathbf{v} = u_1v_1 + u_2v_2 + \cdots + u_nv_n$$ $$\|\mathbf{v}\| = \sqrt{\langle \mathbf{v}, \mathbf{v} \rangle} = \sqrt{v_1^2 + v_2^2 + \cdots + v_n^2}$$ Cauchy-Schwarz: $|\langle \mathbf{u}, \mathbf{v} \rangle| \leq \|\mathbf{u}\| \|\mathbf{v}\|$

$$\mathbf{u}_1 = \mathbf{v}_1$$ $$\mathbf{u}_2 = \mathbf{v}_2 - \text{proj}_{\mathbf{u}_1}\mathbf{v}_2$$ $$\mathbf{u}_3 = \mathbf{v}_3 - \text{proj}_{\mathbf{u}_1}\mathbf{v}_3 - \text{proj}_{\mathbf{u}_2}\mathbf{v}_3$$ where $\text{proj}_{\mathbf{u}}\mathbf{v} = \frac{\langle \mathbf{v}, \mathbf{u} \rangle}{\langle \mathbf{u}, \mathbf{u} \rangle}\mathbf{u}$

Normal equation: $A^T A\hat{\mathbf{x}} = A^T\mathbf{b}$ Solution: $\hat{\mathbf{x}} = (A^T A)^{-1}A^T\mathbf{b}$ If $A$ has orthonormal columns: $\hat{\mathbf{x}} = A^T\mathbf{b}$

$\neg$ (NOT), $\land$ (AND), $\lor$ (OR), $\rightarrow$ (IMPLIES), $\leftrightarrow$ (IFF) De Morgan's Laws: $$\neg(P \land Q) \equiv \neg P \lor \neg Q$$ $$\neg(P \lor Q) \equiv \neg P \land \neg Q$$ $P \rightarrow Q \equiv \neg P \lor Q$

$\forall x \, P(x)$: "for all $x$, $P(x)$" $\exists x \, P(x)$: "there exists $x$ such that $P(x)$" $$\neg\forall x \, P(x) \equiv \exists x \, \neg P(x)$$ $$\neg\exists x \, P(x) \equiv \forall x \, \neg P(x)$$

Direct proof: $P \rightarrow Q$ Contrapositive: $\neg Q \rightarrow \neg P$ Contradiction: Assume $\neg Q$ and derive contradiction Induction: Base case + inductive step

$A \cup B = \{x : x \in A \text{ or } x \in B\}$ $A \cap B = \{x : x \in A \text{ and } x \in B\}$ $A - B = \{x : x \in A \text{ and } x \notin B\}$ $A^c = \{x : x \notin A\}$ $|A \cup B| = |A| + |B| - |A \cap B|$

Reflexive: $\forall x \, (x,x) \in R$ Symmetric: $\forall x,y \, ((x,y) \in R \rightarrow (y,x) \in R)$ Transitive: $\forall x,y,z \, ((x,y) \in R \land (y,z) \in R \rightarrow (x,z) \in R)$ Equivalence relation: reflexive + symmetric + transitive

Injective (one-to-one): $\forall x,y \, (f(x) = f(y) \rightarrow x = y)$ Surjective (onto): $\forall y \, \exists x \, (f(x) = y)$ Bijective: injective + surjective $|A| = |B|$ iff $\exists$ bijection $f: A \rightarrow B$

Addition Principle: $|A \cup B| = |A| + |B|$ if $A \cap B = \emptyset$ Multiplication Principle: $|A \times B| = |A| \times |B|$ Pigeonhole Principle: If $n$ objects in $m$ boxes and $n > m$, then some box contains $> 1$ object

$$P(n,r) = \frac{n!}{(n-r)!} \text{ (permutations)}$$ $$C(n,r) = \binom{n}{r} = \frac{n!}{r!(n-r)!} \text{ (combinations)}$$ Binomial theorem: $(x+y)^n = \sum_{k=0}^n \binom{n}{k} x^k y^{n-k}$ Stars and bars: $\binom{n+k-1}{k-1}$

$$|A_1 \cup A_2 \cup \cdots \cup A_n| =$$ $$\sum |A_i| - \sum |A_i \cap A_j| + \sum |A_i \cap A_j \cap A_k| - \cdots$$ $$+ (-1)^{n+1}|A_1 \cap \cdots \cap A_n|$$

$$G(x) = \sum_{n=0}^{\infty} a_n x^n = a_0 + a_1x + a_2x^2 + \cdots$$ Fibonacci: $F(x) = \frac{x}{1 - x - x^2}$ Geometric: $\frac{1}{1-x} = \sum_{n=0}^{\infty} x^n$

$$E(x) = \sum_{n=0}^{\infty} a_n \frac{x^n}{n!}$$ $e^x = \sum_{n=0}^{\infty} \frac{x^n}{n!}$ Useful for problems with labels/arrangements

$$a_n = c_1a_{n-1} + c_2a_{n-2} + \cdots + c_ka_{n-k}$$ Characteristic equation: $r^k - c_1r^{k-1} - \cdots - c_k = 0$ If roots distinct: $a_n = A_1r_1^n + A_2r_2^n + \cdots$

For $T(n) = aT(n/b) + f(n)$: Case 1: $f(n) = O(n^{\log_b a - \varepsilon}) \Rightarrow T(n) = \Theta(n^{\log_b a})$ Case 2: $f(n) = \Theta(n^{\log_b a}) \Rightarrow T(n) = \Theta(n^{\log_b a} \log n)$ Case 3: $f(n) = \Omega(n^{\log_b a + \varepsilon}) \Rightarrow T(n) = \Theta(f(n))$

If $f(a)f(b) < 0$, then $\exists c \in (a,b): f(c) = 0$ Algorithm: 1. $c = \frac{a + b}{2}$ 2. If $f(a)f(c) < 0$: $b = c$, else $a = c$ 3. Repeat until $|b - a| < $ tolerance Convergence: $O(\log_2((b-a)/\varepsilon))$

$$x_{n+1} = x_n - \frac{f(x_n)}{f'(x_n)}$$ Quadratic convergence when $f'(\text{root}) \neq 0$ May fail if $f'(x_n) \approx 0$ or poor initial guess

$$x_{n+1} = x_n - f(x_n)\frac{x_n - x_{n-1}}{f(x_n) - f(x_{n-1})}$$ Approximates derivative using secant line Superlinear convergence: $\varphi = \frac{1+\sqrt{5}}{2} \approx 1.618$

$$P(x) = \sum_{i=0}^n y_i L_i(x)$$ where $L_i(x) = \prod_{j=0, j \neq i}^n \frac{x - x_j}{x_i - x_j}$ Unique polynomial of degree $\leq n$ through $n+1$ points

$$P(x) = f[x_0] + f[x_0,x_1](x-x_0) + f[x_0,x_1,x_2](x-x_0)(x-x_1) + \cdots$$ $f[x_i,x_{i+1}] = \frac{f[x_{i+1}] - f[x_i]}{x_{i+1} - x_i}$ More efficient for adding new points

Cubic spline: $S(x) = a_i + b_i(x-x_i) + c_i(x-x_i)^2 + d_i(x-x_i)^3$ Conditions: - $S(x_i) = y_i$ - $S'(x_i^-) = S'(x_i^+)$ - $S''(x_i^-) = S''(x_i^+)$

Composite Trapezoidal: $$\int_a^b f(x)\,dx \approx \frac{h}{2}[f(x_0) + 2f(x_1) + \cdots + 2f(x_{n-1}) + f(x_n)]$$ Error: $O(h^2)$ Composite Simpson's: $$\int_a^b f(x)\,dx \approx \frac{h}{3}[f(x_0) + 4f(x_1) + 2f(x_2) + 4f(x_3) + \cdots + f(x_n)]$$ Error: $O(h^4)$

$$\int_{-1}^1 f(x)\,dx \approx \sum_{i=1}^n w_i f(x_i)$$ Optimal choice of points $x_i$ and weights $w_i$ $n$-point Gauss rule exact for polynomials of degree $\leq 2n-1$

$$y_{n+1} = y_n + h \cdot f(x_n, y_n)$$ First-order accuracy: $O(h)$ Simple but may be unstable for large $h$

RK4 (Fourth-order): $$k_1 = hf(x_n, y_n)$$ $$k_2 = hf(x_n + h/2, y_n + k_1/2)$$ $$k_3 = hf(x_n + h/2, y_n + k_2/2)$$ $$k_4 = hf(x_n + h, y_n + k_3)$$ $$y_{n+1} = y_n + \frac{k_1 + 2k_2 + 2k_3 + k_4}{6}$$

$$z = x + iy = re^{i\theta} = r(\cos\theta + i\sin\theta)$$ $|z| = \sqrt{x^2 + y^2} = r$ $\arg(z) = \theta = \arctan(y/x)$ $z^* = x - iy = re^{-i\theta}$ (complex conjugate)

$$z_1z_2 = r_1r_2e^{i(\theta_1+\theta_2)}$$ $$\frac{z_1}{z_2} = \frac{r_1}{r_2}e^{i(\theta_1-\theta_2)}$$ De Moivre's theorem: $z^n = r^n e^{in\theta}$ $n$th roots: $z^{1/n} = r^{1/n} e^{i(\theta+2\pi k)/n}$, $k = 0,1,\ldots,n-1$

$$e^z = e^x(\cos y + i\sin y)$$ $$\sin z = \frac{e^{iz} - e^{-iz}}{2i}$$ $$\cos z = \frac{e^{iz} + e^{-iz}}{2}$$ $\log z = \ln|z| + i(\arg z + 2\pi n)$

$$f(z) = \sum_{n=0}^{\infty} a_n(z - z_0)^n$$ Radius of convergence: $R = \frac{1}{\limsup_{n \to \infty} |a_n|^{1/n}}$ Convergent for $|z - z_0| < R$

Simple pole at $z_0$: $$\text{Res}(f, z_0) = \lim_{z \to z_0} (z - z_0)f(z)$$ Pole of order $n$: $$\text{Res}(f, z_0) = \frac{1}{(n-1)!} \lim_{z \to z_0} \frac{d^{n-1}}{dz^{n-1}}[(z-z_0)^n f(z)]$$

Walk: sequence of vertices $v_0, v_1, \ldots, v_k$ Trail: walk with distinct edges Path: walk with distinct vertices Connected: path exists between any two vertices Distance $d(u,v)$: length of shortest path from $u$ to $v$

Eulerian path: uses every edge exactly once Exists iff graph connected and $\leq 2$ odd-degree vertices Eulerian cycle: closed Eulerian path Exists iff graph connected and all vertices even degree Hamiltonian path: visits every vertex exactly once

$\chi(G) = $ minimum number of colors needed $\chi(K_n) = n$ $\chi(C_n) = 2$ if $n$ even, $3$ if $n$ odd $\chi(\text{bipartite graph}) = 2$ Four Color Theorem: $\chi(\text{planar graph}) \leq 4$

Brooks' Theorem: If $G$ connected, not complete, not odd cycle, then $\chi(G) \leq \Delta(G)$ where $\Delta(G) = $ maximum degree

For integers $a, b$ with $b > 0$: $$a = qb + r \text{ where } 0 \leq r < b$$ $q = $ quotient, $r = $ remainder $a \equiv r \pmod{b}$

$$\gcd(a, b) = \gcd(b, a \bmod b)$$ Extended Euclidean Algorithm: $$\gcd(a, b) = ax + by$$ for some integers $x, y$ Time complexity: $O(\log \min(a, b))$

$$\gcd(a, b) \times \text{lcm}(a, b) = ab$$ If $\gcd(a, n) = 1$ and $\gcd(b, n) = 1$, then $\gcd(ab, n) = 1$ Bézout's identity: $\gcd(a, b) = ax + by$

$a \equiv b \pmod{n}$ iff $n \mid (a - b)$ Properties: $(a + b) \bmod n = ((a \bmod n) + (b \bmod n)) \bmod n$ $(a \times b) \bmod n = ((a \bmod n) \times (b \bmod n)) \bmod n$ Reflexive: $a \equiv a \pmod{n}$ Symmetric: $a \equiv b \implies b \equiv a \pmod{n}$ Transitive: $a \equiv b, b \equiv c \implies a \equiv c \pmod{n}$

$a^{-1} \pmod{n}$ exists iff $\gcd(a, n) = 1$ Finding inverse: use Extended Euclidean Algorithm $ax + ny = 1 \implies ax \equiv 1 \pmod{n} \implies a^{-1} \equiv x \pmod{n}$ Fermat's Little Theorem: If $p$ prime, $\gcd(a, p) = 1$: $$a^{-1} \equiv a^{p-2} \pmod{p}$$

Trial division: test divisibility up to $\sqrt{n}$ Time: $O(\sqrt{n})$ Sieve of Eratosthenes: find all primes $\leq n$ Time: $O(n \log \log n)$ Miller-Rabin: probabilistic primality test Time: $O(k \log^3 n)$ for $k$ rounds

Prime Number Theorem: $$\pi(n) \approx \frac{n}{\ln(n)}$$ where $\pi(n) = $ number of primes $\leq n$ There are infinitely many primes

$$\varphi(n) = |\{k : 1 \leq k \leq n, \gcd(k, n) = 1\}|$$ $\varphi(p) = p - 1$ for prime $p$ $\varphi(p^k) = p^k - p^{k-1} = p^{k-1}(p - 1)$ If $\gcd(m, n) = 1$: $\varphi(mn) = \varphi(m)\varphi(n)$

If $\gcd(a, n) = 1$, then: $$a^{\varphi(n)} \equiv 1 \pmod{n}$$ Fermat's Little Theorem (special case): If $p$ prime and $\gcd(a, p) = 1$: $$a^{p-1} \equiv 1 \pmod{p}$$

$f(n) = O(g(n))$ if $\exists c > 0, n_0$ such that $f(n) \leq c \cdot g(n)$ for all $n \geq n_0$ Upper bound: $f$ grows no faster than $g$ $f(n) = \Omega(g(n))$ if $g(n) = O(f(n))$ Lower bound: $f$ grows at least as fast as $g$ $f(n) = \Theta(g(n))$ if $f(n) = O(g(n))$ and $f(n) = \Omega(g(n))$ Tight bound: $f$ and $g$ grow at same rate

$$O(1) < O(\log n) < O(n) < O(n \log n) < O(n^2) < O(n^3) < O(2^n) < O(n!)$$ Logarithmic: binary search, balanced tree operations Linear: linear search, single loop Linearithmic: merge sort, heap sort Quadratic: nested loops, simple sorting Exponential: brute force subsets Factorial: brute force permutations

Prerequisite: sorted array Algorithm: ``` while low ≤ high: mid = (low + high) / 2 if arr[mid] == target: return mid elif arr[mid] < target: low = mid + 1 else: high = mid - 1 ``` Time: $O(\log n)$, Space: $O(1)$

Average case: $O(1)$ for search, insert, delete Worst case: $O(n)$ if many collisions Load factor $\alpha = \frac{n}{m}$ (items/buckets) Keep $\alpha < 0.75$ for good performance Collision resolution: chaining, open addressing

A problem has optimal substructure if optimal solution contains optimal solutions to subproblems Examples: shortest paths, matrix chain multiplication, optimal binary search trees, edit distance

Recursive algorithm solves same subproblems repeatedly Memoization: top-down approach, store results Tabulation: bottom-up approach, fill table Fibonacci: naive $O(2^n)$, DP $O(n)$

Select maximum number of non-overlapping activities Greedy strategy: sort by finish time, always pick earliest finishing activity Time: $O(n \log n)$

Optimal prefix-free binary codes Greedy strategy: repeatedly merge two nodes with minimum frequency Time: $O(n \log n)$

P: problems solvable in polynomial time NP: problems verifiable in polynomial time NP-Complete: hardest problems in NP NP-Hard: at least as hard as NP-Complete $P \subseteq NP$, but $P = NP$? is open question

Problem $A$ reduces to $B$ ($A \leq_p B$) if $A$ can be solved using polynomial number of calls to $B$ If $A \leq_p B$ and $B \in P$, then $A \in P$ Used to prove NP-completeness

Encryption: $E(x) = (x + k) \bmod 26$ Decryption: $D(y) = (y - k) \bmod 26$ Key space: 26 possible keys Vulnerable to frequency analysis

Encryption: $E(x) = (ax + b) \bmod 26$ Decryption: $D(y) = a^{-1}(y - b) \bmod 26$ Requirement: $\gcd(a, 26) = 1$ Key space: $\varphi(26) \times 26 = 12 \times 26 = 312$

Encryption: $C_i = (M_i + K_{i \bmod \text{keylen}}) \bmod 26$ Polyalphabetic substitution Broken by Kasiski examination and index of coincidence

Public: prime $p$, generator $g$ Alice: chooses $a$, sends $g^a \bmod p$ Bob: chooses $b$, sends $g^b \bmod p$ Shared secret: $K = g^{ab} \bmod p$ Security based on discrete log problem

Key Generation: Choose prime $p$, generator $g$, private key $x$ Public key: $y = g^x \bmod p$ Encryption of $M$: Choose random $k$, send $(g^k \bmod p, M \cdot y^k \bmod p)$ Decryption: $M = c_2 \cdot (c_1^x)^{-1} \bmod p$

Pre-image resistance: given $h$, hard to find $x$ with $H(x) = h$ Second pre-image resistance: given $x$, hard to find $x' \neq x$ with $H(x) = H(x')$ Collision resistance: hard to find $x, x'$ with $H(x) = H(x')$ Birthday paradox: expect collision after $\sqrt{2^n}$ inputs for $n$-bit hash

Digital signatures: sign hash instead of message Password storage: store $H(\text{password} + \text{salt})$ Proof of work: find nonce with $H(\text{block} + \text{nonce}) < \text{target}$ Data integrity: compare hash values

Signing: $S = H(M)^d \bmod n$ Verification: check if $S^e \equiv H(M) \pmod{n}$ Must use padding (PSS) to prevent attacks

Parameters: prime $p$, $q \mid (p-1)$, generator $g$ Private key: $x$, Public key: $y = g^x \bmod p$ Signing $M$: $k = $ random, $r = (g^k \bmod p) \bmod q$ $s = k^{-1}(H(M) + xr) \bmod q$ Signature: $(r, s)$ Verification: check if $r = ((g^{H(M)s^{-1}} \cdot y^{rs^{-1}}) \bmod p) \bmod q$

Minimize: $\mathbf{c}^T \mathbf{x}$ Subject to: $A\mathbf{x} = \mathbf{b}$, $\mathbf{x} \geq \mathbf{0}$ Can convert any LP to standard form: - $\max f \rightarrow \min(-f)$ - inequality $\rightarrow$ equality (add slack variables) - unrestricted variable $\rightarrow$ difference of non-negative variables

1. Start at basic feasible solution (vertex of polytope) 2. Check optimality conditions 3. If not optimal, move to adjacent vertex that improves objective 4. Repeat until optimal or unbounded Worst case: exponential Average case: polynomial

First-order condition: $\nabla f(\mathbf{x}^*) = \mathbf{0}$ Second-order condition: $\nabla^2 f(\mathbf{x}^*)$ positive definite Gradient descent: $\mathbf{x}_{k+1} = \mathbf{x}_k - \alpha_k \nabla f(\mathbf{x}_k)$ Newton's method: $\mathbf{x}_{k+1} = \mathbf{x}_k - [\nabla^2 f(\mathbf{x}_k)]^{-1} \nabla f(\mathbf{x}_k)$

KKT conditions for $\min f(\mathbf{x})$ subject to $g(\mathbf{x}) \leq \mathbf{0}$, $h(\mathbf{x}) = \mathbf{0}$: $\nabla f(\mathbf{x}^*) + \sum_i \lambda_i \nabla g_i(\mathbf{x}^*) + \sum_j \mu_j \nabla h_j(\mathbf{x}^*) = \mathbf{0}$ $g_i(\mathbf{x}^*) \leq 0$, $h_j(\mathbf{x}^*) = 0$ $\lambda_i \geq 0$, $\lambda_i g_i(\mathbf{x}^*) = 0$ (complementary slackness)

Convex set: $\forall \mathbf{x}, \mathbf{y} \in S, \forall \lambda \in [0,1]: \lambda\mathbf{x} + (1-\lambda)\mathbf{y} \in S$ Convex function: $f(\lambda\mathbf{x} + (1-\lambda)\mathbf{y}) \leq \lambda f(\mathbf{x}) + (1-\lambda)f(\mathbf{y})$ Properties: - Local minimum = global minimum - First-order condition sufficient for optimality

Barrier method: replace constraints $g(\mathbf{x}) \leq \mathbf{0}$ with penalty terms $-t \sum_i \log(-g_i(\mathbf{x}))$ As $t \to \infty$, solution approaches constrained optimum Polynomial time complexity for convex problems

1. Solve LP relaxation 2. If solution integer, update best bound 3. If not integer, branch on fractional variable 4. Recursively solve subproblems 5. Prune if bound worse than current best NP-hard in general, but practical for many instances

Add linear constraints (cuts) that remove fractional solutions but preserve all integer solutions Gomory cuts: derived from optimal LP tableau Problem-specific cuts often more effective

$$\lim_{x \to a} f(x) = L$$ means: For every $\varepsilon > 0$, there exists $\delta > 0$ such that $$0 < |x - a| < \delta \implies |f(x) - L| < \varepsilon$$

$$\lim_{x \to 0} \frac{\sin x}{x} = 1$$ $$\lim_{x \to 0} \frac{1 - \cos x}{x} = 0$$ $$\lim_{x \to 0} \frac{e^x - 1}{x} = 1$$ $$\lim_{x \to \infty} \left(1 + \frac{1}{x}\right)^x = e$$

If $\lim_{x \to a} f(x) = \lim_{x \to a} g(x) = 0$ or $\pm\infty$, then: $$\lim_{x \to a} \frac{f(x)}{g(x)} = \lim_{x \to a} \frac{f'(x)}{g'(x)}$$ (provided the right side exists)

$$f'(x) = \lim_{h \to 0} \frac{f(x + h) - f(x)}{h}$$ Alternative notation: $\frac{df}{dx}$, $\frac{d}{dx}f(x)$, $D_x f$

Power Rule: $\frac{d}{dx}(x^n) = nx^{n-1}$ Product Rule: $(fg)' = f'g + fg'$ Quotient Rule: $\left(\frac{f}{g}\right)' = \frac{f'g - fg'}{g^2}$ Chain Rule: $\frac{d}{dx}f(g(x)) = f'(g(x)) \cdot g'(x)$

$$\frac{d}{dx}(\sin x) = \cos x \qquad \frac{d}{dx}(\cos x) = -\sin x$$ $$\frac{d}{dx}(e^x) = e^x \qquad \frac{d}{dx}(\ln x) = \frac{1}{x}$$ $$\frac{d}{dx}(\tan x) = \sec^2 x \qquad \frac{d}{dx}(\arctan x) = \frac{1}{1+x^2}$$

$$\int_a^b f(x)\,dx = \lim_{n \to \infty} \sum_{i=1}^n f(x_i^*) \Delta x$$ where $\Delta x = \frac{b-a}{n}$ and $x_i^* \in [x_{i-1}, x_i]$

Part 1: If $F(x) = \int_a^x f(t)\,dt$, then $F'(x) = f(x)$ Part 2: If $F'(x) = f(x)$, then $$\int_a^b f(x)\,dx = F(b) - F(a)$$

Substitution: $\int f(g(x))g'(x)\,dx = \int f(u)\,du$ Integration by Parts: $\int u\,dv = uv - \int v\,du$ Partial Fractions: Decompose rational functions

$$\int x^n\,dx = \frac{x^{n+1}}{n+1} + C \quad (n \neq -1)$$ $$\int \frac{1}{x}\,dx = \ln|x| + C$$ $$\int e^x\,dx = e^x + C$$ $$\int \sin x\,dx = -\cos x + C$$ $$\int \frac{1}{\sqrt{1-x^2}}\,dx = \arcsin x + C$$

A sequence $\{a_n\}$ converges to $L$ if: $$\lim_{n \to \infty} a_n = L$$ Common limits: $$\lim_{n \to \infty} \frac{1}{n} = 0 \qquad \lim_{n \to \infty} \sqrt[n]{n} = 1$$ $$\lim_{n \to \infty} \left(1 + \frac{1}{n}\right)^n = e$$

Geometric Series: $\sum_{n=0}^{\infty} ar^n = \frac{a}{1-r}$ if $|r| < 1$ p-Series: $\sum_{n=1}^{\infty} \frac{1}{n^p}$ converges if $p > 1$ Ratio Test: If $\lim_{n \to \infty} \left|\frac{a_{n+1}}{a_n}\right| = L$ then series converges if $L < 1$

$$f(x) = \sum_{n=0}^{\infty} \frac{f^{(n)}(a)}{n!}(x-a)^n$$ Common Taylor series: $$e^x = \sum_{n=0}^{\infty} \frac{x^n}{n!}$$ $$\sin x = \sum_{n=0}^{\infty} \frac{(-1)^n x^{2n+1}}{(2n+1)!}$$ $$\ln(1+x) = \sum_{n=1}^{\infty} \frac{(-1)^{n+1} x^n}{n}$$

Critical points: $f'(x) = 0$ or $f'(x)$ undefined Second derivative test: - If $f''(c) > 0$: local minimum at $x = c$ - If $f''(c) < 0$: local maximum at $x = c$ - If $f''(c) = 0$: test inconclusive

If variables $x$ and $y$ are related by an equation and vary with time $t$: $$\frac{dy}{dt} = \frac{dy}{dx} \cdot \frac{dx}{dt}$$ Example: Area of circle $A = \pi r^2$ $$\frac{dA}{dt} = 2\pi r \frac{dr}{dt}$$

Arc length: $L = \int_a^b \sqrt{1 + (f'(x))^2}\,dx$ Surface area (revolution about x-axis): $$S = 2\pi \int_a^b f(x)\sqrt{1 + (f'(x))^2}\,dx$$

$$\frac{\partial f}{\partial x} = \lim_{h \to 0} \frac{f(x+h,y) - f(x,y)}{h}$$ Mixed partials theorem (Clairaut): $$\frac{\partial^2 f}{\partial x \partial y} = \frac{\partial^2 f}{\partial y \partial x}$$ (if both are continuous)

$$\nabla f = \left( \frac{\partial f}{\partial x}, \frac{\partial f}{\partial y}, \frac{\partial f}{\partial z} \right)$$ Directional derivative: $$D_{\mathbf{u}} f = \nabla f \cdot \mathbf{u}$$ Maximum rate of change: $|\nabla f|$

If $z = f(x,y)$ where $x = g(t)$ and $y = h(t)$: $$\frac{dz}{dt} = \frac{\partial z}{\partial x}\frac{dx}{dt} + \frac{\partial z}{\partial y}\frac{dy}{dt}$$ General form: $$\frac{\partial z}{\partial t} = \sum_{i} \frac{\partial z}{\partial x_i}\frac{\partial x_i}{\partial t}$$

$$\iint_R f(x,y) \, dA = \int_a^b \int_{c(x)}^{d(x)} f(x,y) \, dy \, dx$$ Fubini's Theorem: For continuous $f$, $$\int_a^b \int_c^d f(x,y) \, dy \, dx = \int_c^d \int_a^b f(x,y) \, dx \, dy$$

$$\iint_R f(x,y) \, dx \, dy = \iint_S f(x(u,v), y(u,v)) |J| \, du \, dv$$ Jacobian: $J = \frac{\partial(x,y)}{\partial(u,v)} = \begin{vmatrix} \frac{\partial x}{\partial u} & \frac{\partial x}{\partial v} \\ \frac{\partial y}{\partial u} & \frac{\partial y}{\partial v} \end{vmatrix}$

Cylindrical: $\begin{cases} x = r\cos\theta \\ y = r\sin\theta \\ z = z \end{cases}$ $dV = r \, dr \, d\theta \, dz$ Spherical: $\begin{cases} x = \rho\sin\phi\cos\theta \\ y = \rho\sin\phi\sin\theta \\ z = \rho\cos\phi \end{cases}$ $dV = \rho^2\sin\phi \, d\rho \, d\phi \, d\theta$

$$\int_C \mathbf{F} \cdot d\mathbf{r} = \int_a^b \mathbf{F}(\mathbf{r}(t)) \cdot \mathbf{r}'(t) \, dt$$ Conservative field: $\nabla \times \mathbf{F} = \mathbf{0}$ If $\mathbf{F} = \nabla f$: $\int_C \mathbf{F} \cdot d\mathbf{r} = f(B) - f(A)$

$$\oint_C (P \, dx + Q \, dy) = \iint_D \left( \frac{\partial Q}{\partial x} - \frac{\partial P}{\partial y} \right) dA$$ Area formula: $A = \frac{1}{2} \oint_C (x \, dy - y \, dx)$

$$\text{div } \mathbf{F} = \nabla \cdot \mathbf{F} = \frac{\partial P}{\partial x} + \frac{\partial Q}{\partial y} + \frac{\partial R}{\partial z}$$ $$\text{curl } \mathbf{F} = \nabla \times \mathbf{F} = \begin{vmatrix} \mathbf{i} & \mathbf{j} & \mathbf{k} \\ \frac{\partial}{\partial x} & \frac{\partial}{\partial y} & \frac{\partial}{\partial z} \\ P & Q & R \end{vmatrix}$$

$$\frac{dy}{dx} = f(x)g(y)$$ Solution method: $$\int \frac{dy}{g(y)} = \int f(x) \, dx$$

$$\frac{dy}{dx} + P(x)y = Q(x)$$ Integrating factor: $\mu(x) = e^{\int P(x) \, dx}$ Solution: $y = \frac{1}{\mu(x)}\left[\int \mu(x)Q(x) \, dx + C\right]$

$$M(x,y) \, dx + N(x,y) \, dy = 0$$ Exact if: $\frac{\partial M}{\partial y} = \frac{\partial N}{\partial x}$ Solution: Find $F(x,y)$ where $\frac{\partial F}{\partial x} = M$ and $\frac{\partial F}{\partial y} = N$

$$ay'' + by' + cy = 0$$ Characteristic equation: $ar^2 + br + c = 0$ Solutions: - If $r_1 \neq r_2$: $y = c_1e^{r_1x} + c_2e^{r_2x}$ - If $r_1 = r_2 = r$: $y = (c_1 + c_2x)e^{rx}$ - If $r = \alpha \pm \beta i$: $y = e^{\alpha x}(c_1\cos(\beta x) + c_2\sin(\beta x))$

For $ay'' + by' + cy = f(x)$: - If $f(x) = e^{\alpha x}$: try $y_p = Ae^{\alpha x}$ - If $f(x) = \text{polynomial}$: try polynomial of same degree - If $f(x) = \sin(\alpha x)$ or $\cos(\alpha x)$: try $y_p = A\cos(\alpha x) + B\sin(\alpha x)$

For $y'' + P(x)y' + Q(x)y = f(x)$ If $y_1, y_2$ are homogeneous solutions: $$y_p = -y_1\int\frac{y_2f}{W}dx + y_2\int\frac{y_1f}{W}dx$$ Wronskian: $W = y_1y_2' - y_2y_1'$

$$\mathcal{L}\{f(t)\} = F(s) = \int_0^{\infty} e^{-st}f(t) \, dt$$ Properties: - $\mathcal{L}\{af + bg\} = a\mathcal{L}\{f\} + b\mathcal{L}\{g\}$ - $\mathcal{L}\{f'\} = sF(s) - f(0)$ - $\mathcal{L}\{f''\} = s^2F(s) - sf(0) - f'(0)$

$$\mathcal{L}\{1\} = \frac{1}{s}$$ $$\mathcal{L}\{t^n\} = \frac{n!}{s^{n+1}}$$ $$\mathcal{L}\{e^{at}\} = \frac{1}{s-a}$$ $$\mathcal{L}\{\sin(at)\} = \frac{a}{s^2+a^2}$$ $$\mathcal{L}\{\cos(at)\} = \frac{s}{s^2+a^2}$$

$$\mathbf{x}' = A\mathbf{x} + \mathbf{b}$$ Solution: $\mathbf{x}(t) = e^{At}\mathbf{x}_0 + \int_0^t e^{A(t-\tau)}\mathbf{b}(\tau) \, d\tau$ Matrix exponential: $e^{At} = \sum_{n=0}^{\infty} \frac{A^n t^n}{n!}$

If $A\mathbf{v} = \lambda\mathbf{v}$, then $\mathbf{x} = \mathbf{v}e^{\lambda t}$ is a solution General solution: $$\mathbf{x} = c_1\mathbf{v}_1e^{\lambda_1 t} + c_2\mathbf{v}_2e^{\lambda_2 t} + \cdots$$

Vectors $\mathbf{v}_1, \mathbf{v}_2, \ldots, \mathbf{v}_n$ are linearly independent if: $$c_1\mathbf{v}_1 + c_2\mathbf{v}_2 + \cdots + c_n\mathbf{v}_n = \mathbf{0} \implies c_1 = c_2 = \cdots = c_n = 0$$ Matrix form: $A\mathbf{x} = \mathbf{0}$ has only trivial solution

Basis: linearly independent set that spans the space $\dim(V) = $ number of vectors in any basis If $\dim(V) = n$, then any $n$ linearly independent vectors form a basis

$$A\mathbf{v} = \lambda\mathbf{v} \quad (\mathbf{v} \neq \mathbf{0})$$ Characteristic polynomial: $\det(A - \lambda I) = 0$ Eigenspace: $E_{\lambda} = \{\mathbf{v} : A\mathbf{v} = \lambda\mathbf{v}\} = \text{null}(A - \lambda I)$

$$A = PDP^{-1}$$ where $D$ is diagonal $P = [\mathbf{v}_1 \, \mathbf{v}_2 \, \cdots \, \mathbf{v}_n]$ (eigenvectors) $D = \text{diag}(\lambda_1, \lambda_2, \ldots, \lambda_n)$ (eigenvalues) $A^k = PD^k P^{-1}$

$$\text{tr}(A) = \lambda_1 + \lambda_2 + \cdots + \lambda_n$$ $$\det(A) = \lambda_1 \times \lambda_2 \times \cdots \times \lambda_n$$ If $A$ symmetric: all eigenvalues real, eigenvectors orthogonal

$$\langle \mathbf{u}, \mathbf{v} \rangle = \mathbf{u}^T\mathbf{v} = u_1v_1 + u_2v_2 + \cdots + u_nv_n$$ $$\|\mathbf{v}\| = \sqrt{\langle \mathbf{v}, \mathbf{v} \rangle} = \sqrt{v_1^2 + v_2^2 + \cdots + v_n^2}$$ Cauchy-Schwarz: $|\langle \mathbf{u}, \mathbf{v} \rangle| \leq \|\mathbf{u}\| \|\mathbf{v}\|$

$$\mathbf{u}_1 = \mathbf{v}_1$$ $$\mathbf{u}_2 = \mathbf{v}_2 - \text{proj}_{\mathbf{u}_1}\mathbf{v}_2$$ $$\mathbf{u}_3 = \mathbf{v}_3 - \text{proj}_{\mathbf{u}_1}\mathbf{v}_3 - \text{proj}_{\mathbf{u}_2}\mathbf{v}_3$$ where $\text{proj}_{\mathbf{u}}\mathbf{v} = \frac{\langle \mathbf{v}, \mathbf{u} \rangle}{\langle \mathbf{u}, \mathbf{u} \rangle}\mathbf{u}$

Normal equation: $A^T A\hat{\mathbf{x}} = A^T\mathbf{b}$ Solution: $\hat{\mathbf{x}} = (A^T A)^{-1}A^T\mathbf{b}$ If $A$ has orthonormal columns: $\hat{\mathbf{x}} = A^T\mathbf{b}$

$\neg$ (NOT), $\land$ (AND), $\lor$ (OR), $\rightarrow$ (IMPLIES), $\leftrightarrow$ (IFF) De Morgan's Laws: $$\neg(P \land Q) \equiv \neg P \lor \neg Q$$ $$\neg(P \lor Q) \equiv \neg P \land \neg Q$$ $P \rightarrow Q \equiv \neg P \lor Q$

$\forall x \, P(x)$: "for all $x$, $P(x)$" $\exists x \, P(x)$: "there exists $x$ such that $P(x)$" $$\neg\forall x \, P(x) \equiv \exists x \, \neg P(x)$$ $$\neg\exists x \, P(x) \equiv \forall x \, \neg P(x)$$

Direct proof: $P \rightarrow Q$ Contrapositive: $\neg Q \rightarrow \neg P$ Contradiction: Assume $\neg Q$ and derive contradiction Induction: Base case + inductive step

$A \cup B = \{x : x \in A \text{ or } x \in B\}$ $A \cap B = \{x : x \in A \text{ and } x \in B\}$ $A - B = \{x : x \in A \text{ and } x \notin B\}$ $A^c = \{x : x \notin A\}$ $|A \cup B| = |A| + |B| - |A \cap B|$

Reflexive: $\forall x \, (x,x) \in R$ Symmetric: $\forall x,y \, ((x,y) \in R \rightarrow (y,x) \in R)$ Transitive: $\forall x,y,z \, ((x,y) \in R \land (y,z) \in R \rightarrow (x,z) \in R)$ Equivalence relation: reflexive + symmetric + transitive

Injective (one-to-one): $\forall x,y \, (f(x) = f(y) \rightarrow x = y)$ Surjective (onto): $\forall y \, \exists x \, (f(x) = y)$ Bijective: injective + surjective $|A| = |B|$ iff $\exists$ bijection $f: A \rightarrow B$

Addition Principle: $|A \cup B| = |A| + |B|$ if $A \cap B = \emptyset$ Multiplication Principle: $|A \times B| = |A| \times |B|$ Pigeonhole Principle: If $n$ objects in $m$ boxes and $n > m$, then some box contains $> 1$ object

$$P(n,r) = \frac{n!}{(n-r)!} \text{ (permutations)}$$ $$C(n,r) = \binom{n}{r} = \frac{n!}{r!(n-r)!} \text{ (combinations)}$$ Binomial theorem: $(x+y)^n = \sum_{k=0}^n \binom{n}{k} x^k y^{n-k}$ Stars and bars: $\binom{n+k-1}{k-1}$

$$|A_1 \cup A_2 \cup \cdots \cup A_n| =$$ $$\sum |A_i| - \sum |A_i \cap A_j| + \sum |A_i \cap A_j \cap A_k| - \cdots$$ $$+ (-1)^{n+1}|A_1 \cap \cdots \cap A_n|$$

$$G(x) = \sum_{n=0}^{\infty} a_n x^n = a_0 + a_1x + a_2x^2 + \cdots$$ Fibonacci: $F(x) = \frac{x}{1 - x - x^2}$ Geometric: $\frac{1}{1-x} = \sum_{n=0}^{\infty} x^n$

$$E(x) = \sum_{n=0}^{\infty} a_n \frac{x^n}{n!}$$ $e^x = \sum_{n=0}^{\infty} \frac{x^n}{n!}$ Useful for problems with labels/arrangements

$$a_n = c_1a_{n-1} + c_2a_{n-2} + \cdots + c_ka_{n-k}$$ Characteristic equation: $r^k - c_1r^{k-1} - \cdots - c_k = 0$ If roots distinct: $a_n = A_1r_1^n + A_2r_2^n + \cdots$

For $T(n) = aT(n/b) + f(n)$: Case 1: $f(n) = O(n^{\log_b a - \varepsilon}) \Rightarrow T(n) = \Theta(n^{\log_b a})$ Case 2: $f(n) = \Theta(n^{\log_b a}) \Rightarrow T(n) = \Theta(n^{\log_b a} \log n)$ Case 3: $f(n) = \Omega(n^{\log_b a + \varepsilon}) \Rightarrow T(n) = \Theta(f(n))$

If $f(a)f(b) < 0$, then $\exists c \in (a,b): f(c) = 0$ Algorithm: 1. $c = \frac{a + b}{2}$ 2. If $f(a)f(c) < 0$: $b = c$, else $a = c$ 3. Repeat until $|b - a| < $ tolerance Convergence: $O(\log_2((b-a)/\varepsilon))$

$$x_{n+1} = x_n - \frac{f(x_n)}{f'(x_n)}$$ Quadratic convergence when $f'(\text{root}) \neq 0$ May fail if $f'(x_n) \approx 0$ or poor initial guess

$$x_{n+1} = x_n - f(x_n)\frac{x_n - x_{n-1}}{f(x_n) - f(x_{n-1})}$$ Approximates derivative using secant line Superlinear convergence: $\varphi = \frac{1+\sqrt{5}}{2} \approx 1.618$

$$P(x) = \sum_{i=0}^n y_i L_i(x)$$ where $L_i(x) = \prod_{j=0, j \neq i}^n \frac{x - x_j}{x_i - x_j}$ Unique polynomial of degree $\leq n$ through $n+1$ points

$$P(x) = f[x_0] + f[x_0,x_1](x-x_0) + f[x_0,x_1,x_2](x-x_0)(x-x_1) + \cdots$$ $f[x_i,x_{i+1}] = \frac{f[x_{i+1}] - f[x_i]}{x_{i+1} - x_i}$ More efficient for adding new points

Cubic spline: $S(x) = a_i + b_i(x-x_i) + c_i(x-x_i)^2 + d_i(x-x_i)^3$ Conditions: - $S(x_i) = y_i$ - $S'(x_i^-) = S'(x_i^+)$ - $S''(x_i^-) = S''(x_i^+)$

Composite Trapezoidal: $$\int_a^b f(x)\,dx \approx \frac{h}{2}[f(x_0) + 2f(x_1) + \cdots + 2f(x_{n-1}) + f(x_n)]$$ Error: $O(h^2)$ Composite Simpson's: $$\int_a^b f(x)\,dx \approx \frac{h}{3}[f(x_0) + 4f(x_1) + 2f(x_2) + 4f(x_3) + \cdots + f(x_n)]$$ Error: $O(h^4)$

$$\int_{-1}^1 f(x)\,dx \approx \sum_{i=1}^n w_i f(x_i)$$ Optimal choice of points $x_i$ and weights $w_i$ $n$-point Gauss rule exact for polynomials of degree $\leq 2n-1$

$$y_{n+1} = y_n + h \cdot f(x_n, y_n)$$ First-order accuracy: $O(h)$ Simple but may be unstable for large $h$

RK4 (Fourth-order): $$k_1 = hf(x_n, y_n)$$ $$k_2 = hf(x_n + h/2, y_n + k_1/2)$$ $$k_3 = hf(x_n + h/2, y_n + k_2/2)$$ $$k_4 = hf(x_n + h, y_n + k_3)$$ $$y_{n+1} = y_n + \frac{k_1 + 2k_2 + 2k_3 + k_4}{6}$$

$$z = x + iy = re^{i\theta} = r(\cos\theta + i\sin\theta)$$ $|z| = \sqrt{x^2 + y^2} = r$ $\arg(z) = \theta = \arctan(y/x)$ $z^* = x - iy = re^{-i\theta}$ (complex conjugate)

$$z_1z_2 = r_1r_2e^{i(\theta_1+\theta_2)}$$ $$\frac{z_1}{z_2} = \frac{r_1}{r_2}e^{i(\theta_1-\theta_2)}$$ De Moivre's theorem: $z^n = r^n e^{in\theta}$ $n$th roots: $z^{1/n} = r^{1/n} e^{i(\theta+2\pi k)/n}$, $k = 0,1,\ldots,n-1$

$$e^z = e^x(\cos y + i\sin y)$$ $$\sin z = \frac{e^{iz} - e^{-iz}}{2i}$$ $$\cos z = \frac{e^{iz} + e^{-iz}}{2}$$ $\log z = \ln|z| + i(\arg z + 2\pi n)$

$$f(z) = \sum_{n=0}^{\infty} a_n(z - z_0)^n$$ Radius of convergence: $R = \frac{1}{\limsup_{n \to \infty} |a_n|^{1/n}}$ Convergent for $|z - z_0| < R$

Simple pole at $z_0$: $$\text{Res}(f, z_0) = \lim_{z \to z_0} (z - z_0)f(z)$$ Pole of order $n$: $$\text{Res}(f, z_0) = \frac{1}{(n-1)!} \lim_{z \to z_0} \frac{d^{n-1}}{dz^{n-1}}[(z-z_0)^n f(z)]$$

Walk: sequence of vertices $v_0, v_1, \ldots, v_k$ Trail: walk with distinct edges Path: walk with distinct vertices Connected: path exists between any two vertices Distance $d(u,v)$: length of shortest path from $u$ to $v$

Eulerian path: uses every edge exactly once Exists iff graph connected and $\leq 2$ odd-degree vertices Eulerian cycle: closed Eulerian path Exists iff graph connected and all vertices even degree Hamiltonian path: visits every vertex exactly once

$\chi(G) = $ minimum number of colors needed $\chi(K_n) = n$ $\chi(C_n) = 2$ if $n$ even, $3$ if $n$ odd $\chi(\text{bipartite graph}) = 2$ Four Color Theorem: $\chi(\text{planar graph}) \leq 4$

Brooks' Theorem: If $G$ connected, not complete, not odd cycle, then $\chi(G) \leq \Delta(G)$ where $\Delta(G) = $ maximum degree

For integers $a, b$ with $b > 0$: $$a = qb + r \text{ where } 0 \leq r < b$$ $q = $ quotient, $r = $ remainder $a \equiv r \pmod{b}$

$$\gcd(a, b) = \gcd(b, a \bmod b)$$ Extended Euclidean Algorithm: $$\gcd(a, b) = ax + by$$ for some integers $x, y$ Time complexity: $O(\log \min(a, b))$

$$\gcd(a, b) \times \text{lcm}(a, b) = ab$$ If $\gcd(a, n) = 1$ and $\gcd(b, n) = 1$, then $\gcd(ab, n) = 1$ Bézout's identity: $\gcd(a, b) = ax + by$

$a \equiv b \pmod{n}$ iff $n \mid (a - b)$ Properties: $(a + b) \bmod n = ((a \bmod n) + (b \bmod n)) \bmod n$ $(a \times b) \bmod n = ((a \bmod n) \times (b \bmod n)) \bmod n$ Reflexive: $a \equiv a \pmod{n}$ Symmetric: $a \equiv b \implies b \equiv a \pmod{n}$ Transitive: $a \equiv b, b \equiv c \implies a \equiv c \pmod{n}$

$a^{-1} \pmod{n}$ exists iff $\gcd(a, n) = 1$ Finding inverse: use Extended Euclidean Algorithm $ax + ny = 1 \implies ax \equiv 1 \pmod{n} \implies a^{-1} \equiv x \pmod{n}$ Fermat's Little Theorem: If $p$ prime, $\gcd(a, p) = 1$: $$a^{-1} \equiv a^{p-2} \pmod{p}$$

Trial division: test divisibility up to $\sqrt{n}$ Time: $O(\sqrt{n})$ Sieve of Eratosthenes: find all primes $\leq n$ Time: $O(n \log \log n)$ Miller-Rabin: probabilistic primality test Time: $O(k \log^3 n)$ for $k$ rounds

Prime Number Theorem: $$\pi(n) \approx \frac{n}{\ln(n)}$$ where $\pi(n) = $ number of primes $\leq n$ There are infinitely many primes

$$\varphi(n) = |\{k : 1 \leq k \leq n, \gcd(k, n) = 1\}|$$ $\varphi(p) = p - 1$ for prime $p$ $\varphi(p^k) = p^k - p^{k-1} = p^{k-1}(p - 1)$ If $\gcd(m, n) = 1$: $\varphi(mn) = \varphi(m)\varphi(n)$

If $\gcd(a, n) = 1$, then: $$a^{\varphi(n)} \equiv 1 \pmod{n}$$ Fermat's Little Theorem (special case): If $p$ prime and $\gcd(a, p) = 1$: $$a^{p-1} \equiv 1 \pmod{p}$$

$f(n) = O(g(n))$ if $\exists c > 0, n_0$ such that $f(n) \leq c \cdot g(n)$ for all $n \geq n_0$ Upper bound: $f$ grows no faster than $g$ $f(n) = \Omega(g(n))$ if $g(n) = O(f(n))$ Lower bound: $f$ grows at least as fast as $g$ $f(n) = \Theta(g(n))$ if $f(n) = O(g(n))$ and $f(n) = \Omega(g(n))$ Tight bound: $f$ and $g$ grow at same rate

$$O(1) < O(\log n) < O(n) < O(n \log n) < O(n^2) < O(n^3) < O(2^n) < O(n!)$$ Logarithmic: binary search, balanced tree operations Linear: linear search, single loop Linearithmic: merge sort, heap sort Quadratic: nested loops, simple sorting Exponential: brute force subsets Factorial: brute force permutations

Prerequisite: sorted array Algorithm: ``` while low ≤ high: mid = (low + high) / 2 if arr[mid] == target: return mid elif arr[mid] < target: low = mid + 1 else: high = mid - 1 ``` Time: $O(\log n)$, Space: $O(1)$

Average case: $O(1)$ for search, insert, delete Worst case: $O(n)$ if many collisions Load factor $\alpha = \frac{n}{m}$ (items/buckets) Keep $\alpha < 0.75$ for good performance Collision resolution: chaining, open addressing

A problem has optimal substructure if optimal solution contains optimal solutions to subproblems Examples: shortest paths, matrix chain multiplication, optimal binary search trees, edit distance

Recursive algorithm solves same subproblems repeatedly Memoization: top-down approach, store results Tabulation: bottom-up approach, fill table Fibonacci: naive $O(2^n)$, DP $O(n)$

Select maximum number of non-overlapping activities Greedy strategy: sort by finish time, always pick earliest finishing activity Time: $O(n \log n)$

Optimal prefix-free binary codes Greedy strategy: repeatedly merge two nodes with minimum frequency Time: $O(n \log n)$

P: problems solvable in polynomial time NP: problems verifiable in polynomial time NP-Complete: hardest problems in NP NP-Hard: at least as hard as NP-Complete $P \subseteq NP$, but $P = NP$? is open question

Problem $A$ reduces to $B$ ($A \leq_p B$) if $A$ can be solved using polynomial number of calls to $B$ If $A \leq_p B$ and $B \in P$, then $A \in P$ Used to prove NP-completeness

Encryption: $E(x) = (x + k) \bmod 26$ Decryption: $D(y) = (y - k) \bmod 26$ Key space: 26 possible keys Vulnerable to frequency analysis

Encryption: $E(x) = (ax + b) \bmod 26$ Decryption: $D(y) = a^{-1}(y - b) \bmod 26$ Requirement: $\gcd(a, 26) = 1$ Key space: $\varphi(26) \times 26 = 12 \times 26 = 312$

Encryption: $C_i = (M_i + K_{i \bmod \text{keylen}}) \bmod 26$ Polyalphabetic substitution Broken by Kasiski examination and index of coincidence

Public: prime $p$, generator $g$ Alice: chooses $a$, sends $g^a \bmod p$ Bob: chooses $b$, sends $g^b \bmod p$ Shared secret: $K = g^{ab} \bmod p$ Security based on discrete log problem

Key Generation: Choose prime $p$, generator $g$, private key $x$ Public key: $y = g^x \bmod p$ Encryption of $M$: Choose random $k$, send $(g^k \bmod p, M \cdot y^k \bmod p)$ Decryption: $M = c_2 \cdot (c_1^x)^{-1} \bmod p$

Pre-image resistance: given $h$, hard to find $x$ with $H(x) = h$ Second pre-image resistance: given $x$, hard to find $x' \neq x$ with $H(x) = H(x')$ Collision resistance: hard to find $x, x'$ with $H(x) = H(x')$ Birthday paradox: expect collision after $\sqrt{2^n}$ inputs for $n$-bit hash

Digital signatures: sign hash instead of message Password storage: store $H(\text{password} + \text{salt})$ Proof of work: find nonce with $H(\text{block} + \text{nonce}) < \text{target}$ Data integrity: compare hash values

Signing: $S = H(M)^d \bmod n$ Verification: check if $S^e \equiv H(M) \pmod{n}$ Must use padding (PSS) to prevent attacks

Parameters: prime $p$, $q \mid (p-1)$, generator $g$ Private key: $x$, Public key: $y = g^x \bmod p$ Signing $M$: $k = $ random, $r = (g^k \bmod p) \bmod q$ $s = k^{-1}(H(M) + xr) \bmod q$ Signature: $(r, s)$ Verification: check if $r = ((g^{H(M)s^{-1}} \cdot y^{rs^{-1}}) \bmod p) \bmod q$

Minimize: $\mathbf{c}^T \mathbf{x}$ Subject to: $A\mathbf{x} = \mathbf{b}$, $\mathbf{x} \geq \mathbf{0}$ Can convert any LP to standard form: - $\max f \rightarrow \min(-f)$ - inequality $\rightarrow$ equality (add slack variables) - unrestricted variable $\rightarrow$ difference of non-negative variables

1. Start at basic feasible solution (vertex of polytope) 2. Check optimality conditions 3. If not optimal, move to adjacent vertex that improves objective 4. Repeat until optimal or unbounded Worst case: exponential Average case: polynomial

First-order condition: $\nabla f(\mathbf{x}^*) = \mathbf{0}$ Second-order condition: $\nabla^2 f(\mathbf{x}^*)$ positive definite Gradient descent: $\mathbf{x}_{k+1} = \mathbf{x}_k - \alpha_k \nabla f(\mathbf{x}_k)$ Newton's method: $\mathbf{x}_{k+1} = \mathbf{x}_k - [\nabla^2 f(\mathbf{x}_k)]^{-1} \nabla f(\mathbf{x}_k)$

KKT conditions for $\min f(\mathbf{x})$ subject to $g(\mathbf{x}) \leq \mathbf{0}$, $h(\mathbf{x}) = \mathbf{0}$: $\nabla f(\mathbf{x}^*) + \sum_i \lambda_i \nabla g_i(\mathbf{x}^*) + \sum_j \mu_j \nabla h_j(\mathbf{x}^*) = \mathbf{0}$ $g_i(\mathbf{x}^*) \leq 0$, $h_j(\mathbf{x}^*) = 0$ $\lambda_i \geq 0$, $\lambda_i g_i(\mathbf{x}^*) = 0$ (complementary slackness)

Convex set: $\forall \mathbf{x}, \mathbf{y} \in S, \forall \lambda \in [0,1]: \lambda\mathbf{x} + (1-\lambda)\mathbf{y} \in S$ Convex function: $f(\lambda\mathbf{x} + (1-\lambda)\mathbf{y}) \leq \lambda f(\mathbf{x}) + (1-\lambda)f(\mathbf{y})$ Properties: - Local minimum = global minimum - First-order condition sufficient for optimality

Barrier method: replace constraints $g(\mathbf{x}) \leq \mathbf{0}$ with penalty terms $-t \sum_i \log(-g_i(\mathbf{x}))$ As $t \to \infty$, solution approaches constrained optimum Polynomial time complexity for convex problems

1. Solve LP relaxation 2. If solution integer, update best bound 3. If not integer, branch on fractional variable 4. Recursively solve subproblems 5. Prune if bound worse than current best NP-hard in general, but practical for many instances

Add linear constraints (cuts) that remove fractional solutions but preserve all integer solutions Gomory cuts: derived from optimal LP tableau Problem-specific cuts often more effective

$$\lim_{x \to a} f(x) = L$$ means: For every $\varepsilon > 0$, there exists $\delta > 0$ such that $$0 < |x - a| < \delta \implies |f(x) - L| < \varepsilon$$

$$\lim_{x \to 0} \frac{\sin x}{x} = 1$$ $$\lim_{x \to 0} \frac{1 - \cos x}{x} = 0$$ $$\lim_{x \to 0} \frac{e^x - 1}{x} = 1$$ $$\lim_{x \to \infty} \left(1 + \frac{1}{x}\right)^x = e$$

If $\lim_{x \to a} f(x) = \lim_{x \to a} g(x) = 0$ or $\pm\infty$, then: $$\lim_{x \to a} \frac{f(x)}{g(x)} = \lim_{x \to a} \frac{f'(x)}{g'(x)}$$ (provided the right side exists)

$$f'(x) = \lim_{h \to 0} \frac{f(x + h) - f(x)}{h}$$ Alternative notation: $\frac{df}{dx}$, $\frac{d}{dx}f(x)$, $D_x f$

Power Rule: $\frac{d}{dx}(x^n) = nx^{n-1}$ Product Rule: $(fg)' = f'g + fg'$ Quotient Rule: $\left(\frac{f}{g}\right)' = \frac{f'g - fg'}{g^2}$ Chain Rule: $\frac{d}{dx}f(g(x)) = f'(g(x)) \cdot g'(x)$

$$\frac{d}{dx}(\sin x) = \cos x \qquad \frac{d}{dx}(\cos x) = -\sin x$$ $$\frac{d}{dx}(e^x) = e^x \qquad \frac{d}{dx}(\ln x) = \frac{1}{x}$$ $$\frac{d}{dx}(\tan x) = \sec^2 x \qquad \frac{d}{dx}(\arctan x) = \frac{1}{1+x^2}$$

$$\int_a^b f(x)\,dx = \lim_{n \to \infty} \sum_{i=1}^n f(x_i^*) \Delta x$$ where $\Delta x = \frac{b-a}{n}$ and $x_i^* \in [x_{i-1}, x_i]$

Part 1: If $F(x) = \int_a^x f(t)\,dt$, then $F'(x) = f(x)$ Part 2: If $F'(x) = f(x)$, then $$\int_a^b f(x)\,dx = F(b) - F(a)$$

Substitution: $\int f(g(x))g'(x)\,dx = \int f(u)\,du$ Integration by Parts: $\int u\,dv = uv - \int v\,du$ Partial Fractions: Decompose rational functions

$$\int x^n\,dx = \frac{x^{n+1}}{n+1} + C \quad (n \neq -1)$$ $$\int \frac{1}{x}\,dx = \ln|x| + C$$ $$\int e^x\,dx = e^x + C$$ $$\int \sin x\,dx = -\cos x + C$$ $$\int \frac{1}{\sqrt{1-x^2}}\,dx = \arcsin x + C$$

A sequence $\{a_n\}$ converges to $L$ if: $$\lim_{n \to \infty} a_n = L$$ Common limits: $$\lim_{n \to \infty} \frac{1}{n} = 0 \qquad \lim_{n \to \infty} \sqrt[n]{n} = 1$$ $$\lim_{n \to \infty} \left(1 + \frac{1}{n}\right)^n = e$$

Geometric Series: $\sum_{n=0}^{\infty} ar^n = \frac{a}{1-r}$ if $|r| < 1$ p-Series: $\sum_{n=1}^{\infty} \frac{1}{n^p}$ converges if $p > 1$ Ratio Test: If $\lim_{n \to \infty} \left|\frac{a_{n+1}}{a_n}\right| = L$ then series converges if $L < 1$

$$f(x) = \sum_{n=0}^{\infty} \frac{f^{(n)}(a)}{n!}(x-a)^n$$ Common Taylor series: $$e^x = \sum_{n=0}^{\infty} \frac{x^n}{n!}$$ $$\sin x = \sum_{n=0}^{\infty} \frac{(-1)^n x^{2n+1}}{(2n+1)!}$$ $$\ln(1+x) = \sum_{n=1}^{\infty} \frac{(-1)^{n+1} x^n}{n}$$

Critical points: $f'(x) = 0$ or $f'(x)$ undefined Second derivative test: - If $f''(c) > 0$: local minimum at $x = c$ - If $f''(c) < 0$: local maximum at $x = c$ - If $f''(c) = 0$: test inconclusive

If variables $x$ and $y$ are related by an equation and vary with time $t$: $$\frac{dy}{dt} = \frac{dy}{dx} \cdot \frac{dx}{dt}$$ Example: Area of circle $A = \pi r^2$ $$\frac{dA}{dt} = 2\pi r \frac{dr}{dt}$$

Arc length: $L = \int_a^b \sqrt{1 + (f'(x))^2}\,dx$ Surface area (revolution about x-axis): $$S = 2\pi \int_a^b f(x)\sqrt{1 + (f'(x))^2}\,dx$$

$$\frac{\partial f}{\partial x} = \lim_{h \to 0} \frac{f(x+h,y) - f(x,y)}{h}$$ Mixed partials theorem (Clairaut): $$\frac{\partial^2 f}{\partial x \partial y} = \frac{\partial^2 f}{\partial y \partial x}$$ (if both are continuous)

$$\nabla f = \left( \frac{\partial f}{\partial x}, \frac{\partial f}{\partial y}, \frac{\partial f}{\partial z} \right)$$ Directional derivative: $$D_{\mathbf{u}} f = \nabla f \cdot \mathbf{u}$$ Maximum rate of change: $|\nabla f|$

If $z = f(x,y)$ where $x = g(t)$ and $y = h(t)$: $$\frac{dz}{dt} = \frac{\partial z}{\partial x}\frac{dx}{dt} + \frac{\partial z}{\partial y}\frac{dy}{dt}$$ General form: $$\frac{\partial z}{\partial t} = \sum_{i} \frac{\partial z}{\partial x_i}\frac{\partial x_i}{\partial t}$$

$$\iint_R f(x,y) \, dA = \int_a^b \int_{c(x)}^{d(x)} f(x,y) \, dy \, dx$$ Fubini's Theorem: For continuous $f$, $$\int_a^b \int_c^d f(x,y) \, dy \, dx = \int_c^d \int_a^b f(x,y) \, dx \, dy$$

$$\iint_R f(x,y) \, dx \, dy = \iint_S f(x(u,v), y(u,v)) |J| \, du \, dv$$ Jacobian: $J = \frac{\partial(x,y)}{\partial(u,v)} = \begin{vmatrix} \frac{\partial x}{\partial u} & \frac{\partial x}{\partial v} \\ \frac{\partial y}{\partial u} & \frac{\partial y}{\partial v} \end{vmatrix}$

Cylindrical: $\begin{cases} x = r\cos\theta \\ y = r\sin\theta \\ z = z \end{cases}$ $dV = r \, dr \, d\theta \, dz$ Spherical: $\begin{cases} x = \rho\sin\phi\cos\theta \\ y = \rho\sin\phi\sin\theta \\ z = \rho\cos\phi \end{cases}$ $dV = \rho^2\sin\phi \, d\rho \, d\phi \, d\theta$

$$\int_C \mathbf{F} \cdot d\mathbf{r} = \int_a^b \mathbf{F}(\mathbf{r}(t)) \cdot \mathbf{r}'(t) \, dt$$ Conservative field: $\nabla \times \mathbf{F} = \mathbf{0}$ If $\mathbf{F} = \nabla f$: $\int_C \mathbf{F} \cdot d\mathbf{r} = f(B) - f(A)$

$$\oint_C (P \, dx + Q \, dy) = \iint_D \left( \frac{\partial Q}{\partial x} - \frac{\partial P}{\partial y} \right) dA$$ Area formula: $A = \frac{1}{2} \oint_C (x \, dy - y \, dx)$

$$\text{div } \mathbf{F} = \nabla \cdot \mathbf{F} = \frac{\partial P}{\partial x} + \frac{\partial Q}{\partial y} + \frac{\partial R}{\partial z}$$ $$\text{curl } \mathbf{F} = \nabla \times \mathbf{F} = \begin{vmatrix} \mathbf{i} & \mathbf{j} & \mathbf{k} \\ \frac{\partial}{\partial x} & \frac{\partial}{\partial y} & \frac{\partial}{\partial z} \\ P & Q & R \end{vmatrix}$$

$$\frac{dy}{dx} = f(x)g(y)$$ Solution method: $$\int \frac{dy}{g(y)} = \int f(x) \, dx$$

$$\frac{dy}{dx} + P(x)y = Q(x)$$ Integrating factor: $\mu(x) = e^{\int P(x) \, dx}$ Solution: $y = \frac{1}{\mu(x)}\left[\int \mu(x)Q(x) \, dx + C\right]$

$$M(x,y) \, dx + N(x,y) \, dy = 0$$ Exact if: $\frac{\partial M}{\partial y} = \frac{\partial N}{\partial x}$ Solution: Find $F(x,y)$ where $\frac{\partial F}{\partial x} = M$ and $\frac{\partial F}{\partial y} = N$

$$ay'' + by' + cy = 0$$ Characteristic equation: $ar^2 + br + c = 0$ Solutions: - If $r_1 \neq r_2$: $y = c_1e^{r_1x} + c_2e^{r_2x}$ - If $r_1 = r_2 = r$: $y = (c_1 + c_2x)e^{rx}$ - If $r = \alpha \pm \beta i$: $y = e^{\alpha x}(c_1\cos(\beta x) + c_2\sin(\beta x))$

For $ay'' + by' + cy = f(x)$: - If $f(x) = e^{\alpha x}$: try $y_p = Ae^{\alpha x}$ - If $f(x) = \text{polynomial}$: try polynomial of same degree - If $f(x) = \sin(\alpha x)$ or $\cos(\alpha x)$: try $y_p = A\cos(\alpha x) + B\sin(\alpha x)$

For $y'' + P(x)y' + Q(x)y = f(x)$ If $y_1, y_2$ are homogeneous solutions: $$y_p = -y_1\int\frac{y_2f}{W}dx + y_2\int\frac{y_1f}{W}dx$$ Wronskian: $W = y_1y_2' - y_2y_1'$

$$\mathcal{L}\{f(t)\} = F(s) = \int_0^{\infty} e^{-st}f(t) \, dt$$ Properties: - $\mathcal{L}\{af + bg\} = a\mathcal{L}\{f\} + b\mathcal{L}\{g\}$ - $\mathcal{L}\{f'\} = sF(s) - f(0)$ - $\mathcal{L}\{f''\} = s^2F(s) - sf(0) - f'(0)$

$$\mathcal{L}\{1\} = \frac{1}{s}$$ $$\mathcal{L}\{t^n\} = \frac{n!}{s^{n+1}}$$ $$\mathcal{L}\{e^{at}\} = \frac{1}{s-a}$$ $$\mathcal{L}\{\sin(at)\} = \frac{a}{s^2+a^2}$$ $$\mathcal{L}\{\cos(at)\} = \frac{s}{s^2+a^2}$$

$$\mathbf{x}' = A\mathbf{x} + \mathbf{b}$$ Solution: $\mathbf{x}(t) = e^{At}\mathbf{x}_0 + \int_0^t e^{A(t-\tau)}\mathbf{b}(\tau) \, d\tau$ Matrix exponential: $e^{At} = \sum_{n=0}^{\infty} \frac{A^n t^n}{n!}$

If $A\mathbf{v} = \lambda\mathbf{v}$, then $\mathbf{x} = \mathbf{v}e^{\lambda t}$ is a solution General solution: $$\mathbf{x} = c_1\mathbf{v}_1e^{\lambda_1 t} + c_2\mathbf{v}_2e^{\lambda_2 t} + \cdots$$

Vectors $\mathbf{v}_1, \mathbf{v}_2, \ldots, \mathbf{v}_n$ are linearly independent if: $$c_1\mathbf{v}_1 + c_2\mathbf{v}_2 + \cdots + c_n\mathbf{v}_n = \mathbf{0} \implies c_1 = c_2 = \cdots = c_n = 0$$ Matrix form: $A\mathbf{x} = \mathbf{0}$ has only trivial solution

Basis: linearly independent set that spans the space $\dim(V) = $ number of vectors in any basis If $\dim(V) = n$, then any $n$ linearly independent vectors form a basis

$$A\mathbf{v} = \lambda\mathbf{v} \quad (\mathbf{v} \neq \mathbf{0})$$ Characteristic polynomial: $\det(A - \lambda I) = 0$ Eigenspace: $E_{\lambda} = \{\mathbf{v} : A\mathbf{v} = \lambda\mathbf{v}\} = \text{null}(A - \lambda I)$

$$A = PDP^{-1}$$ where $D$ is diagonal $P = [\mathbf{v}_1 \, \mathbf{v}_2 \, \cdots \, \mathbf{v}_n]$ (eigenvectors) $D = \text{diag}(\lambda_1, \lambda_2, \ldots, \lambda_n)$ (eigenvalues) $A^k = PD^k P^{-1}$

$$\text{tr}(A) = \lambda_1 + \lambda_2 + \cdots + \lambda_n$$ $$\det(A) = \lambda_1 \times \lambda_2 \times \cdots \times \lambda_n$$ If $A$ symmetric: all eigenvalues real, eigenvectors orthogonal

$$\langle \mathbf{u}, \mathbf{v} \rangle = \mathbf{u}^T\mathbf{v} = u_1v_1 + u_2v_2 + \cdots + u_nv_n$$ $$\|\mathbf{v}\| = \sqrt{\langle \mathbf{v}, \mathbf{v} \rangle} = \sqrt{v_1^2 + v_2^2 + \cdots + v_n^2}$$ Cauchy-Schwarz: $|\langle \mathbf{u}, \mathbf{v} \rangle| \leq \|\mathbf{u}\| \|\mathbf{v}\|$

$$\mathbf{u}_1 = \mathbf{v}_1$$ $$\mathbf{u}_2 = \mathbf{v}_2 - \text{proj}_{\mathbf{u}_1}\mathbf{v}_2$$ $$\mathbf{u}_3 = \mathbf{v}_3 - \text{proj}_{\mathbf{u}_1}\mathbf{v}_3 - \text{proj}_{\mathbf{u}_2}\mathbf{v}_3$$ where $\text{proj}_{\mathbf{u}}\mathbf{v} = \frac{\langle \mathbf{v}, \mathbf{u} \rangle}{\langle \mathbf{u}, \mathbf{u} \rangle}\mathbf{u}$

Normal equation: $A^T A\hat{\mathbf{x}} = A^T\mathbf{b}$ Solution: $\hat{\mathbf{x}} = (A^T A)^{-1}A^T\mathbf{b}$ If $A$ has orthonormal columns: $\hat{\mathbf{x}} = A^T\mathbf{b}$

$\neg$ (NOT), $\land$ (AND), $\lor$ (OR), $\rightarrow$ (IMPLIES), $\leftrightarrow$ (IFF) De Morgan's Laws: $$\neg(P \land Q) \equiv \neg P \lor \neg Q$$ $$\neg(P \lor Q) \equiv \neg P \land \neg Q$$ $P \rightarrow Q \equiv \neg P \lor Q$

$\forall x \, P(x)$: "for all $x$, $P(x)$" $\exists x \, P(x)$: "there exists $x$ such that $P(x)$" $$\neg\forall x \, P(x) \equiv \exists x \, \neg P(x)$$ $$\neg\exists x \, P(x) \equiv \forall x \, \neg P(x)$$

Direct proof: $P \rightarrow Q$ Contrapositive: $\neg Q \rightarrow \neg P$ Contradiction: Assume $\neg Q$ and derive contradiction Induction: Base case + inductive step

$A \cup B = \{x : x \in A \text{ or } x \in B\}$ $A \cap B = \{x : x \in A \text{ and } x \in B\}$ $A - B = \{x : x \in A \text{ and } x \notin B\}$ $A^c = \{x : x \notin A\}$ $|A \cup B| = |A| + |B| - |A \cap B|$

Reflexive: $\forall x \, (x,x) \in R$ Symmetric: $\forall x,y \, ((x,y) \in R \rightarrow (y,x) \in R)$ Transitive: $\forall x,y,z \, ((x,y) \in R \land (y,z) \in R \rightarrow (x,z) \in R)$ Equivalence relation: reflexive + symmetric + transitive

Injective (one-to-one): $\forall x,y \, (f(x) = f(y) \rightarrow x = y)$ Surjective (onto): $\forall y \, \exists x \, (f(x) = y)$ Bijective: injective + surjective $|A| = |B|$ iff $\exists$ bijection $f: A \rightarrow B$

Addition Principle: $|A \cup B| = |A| + |B|$ if $A \cap B = \emptyset$ Multiplication Principle: $|A \times B| = |A| \times |B|$ Pigeonhole Principle: If $n$ objects in $m$ boxes and $n > m$, then some box contains $> 1$ object

$$P(n,r) = \frac{n!}{(n-r)!} \text{ (permutations)}$$ $$C(n,r) = \binom{n}{r} = \frac{n!}{r!(n-r)!} \text{ (combinations)}$$ Binomial theorem: $(x+y)^n = \sum_{k=0}^n \binom{n}{k} x^k y^{n-k}$ Stars and bars: $\binom{n+k-1}{k-1}$

$$|A_1 \cup A_2 \cup \cdots \cup A_n| =$$ $$\sum |A_i| - \sum |A_i \cap A_j| + \sum |A_i \cap A_j \cap A_k| - \cdots$$ $$+ (-1)^{n+1}|A_1 \cap \cdots \cap A_n|$$

$$G(x) = \sum_{n=0}^{\infty} a_n x^n = a_0 + a_1x + a_2x^2 + \cdots$$ Fibonacci: $F(x) = \frac{x}{1 - x - x^2}$ Geometric: $\frac{1}{1-x} = \sum_{n=0}^{\infty} x^n$

$$E(x) = \sum_{n=0}^{\infty} a_n \frac{x^n}{n!}$$ $e^x = \sum_{n=0}^{\infty} \frac{x^n}{n!}$ Useful for problems with labels/arrangements

$$a_n = c_1a_{n-1} + c_2a_{n-2} + \cdots + c_ka_{n-k}$$ Characteristic equation: $r^k - c_1r^{k-1} - \cdots - c_k = 0$ If roots distinct: $a_n = A_1r_1^n + A_2r_2^n + \cdots$

For $T(n) = aT(n/b) + f(n)$: Case 1: $f(n) = O(n^{\log_b a - \varepsilon}) \Rightarrow T(n) = \Theta(n^{\log_b a})$ Case 2: $f(n) = \Theta(n^{\log_b a}) \Rightarrow T(n) = \Theta(n^{\log_b a} \log n)$ Case 3: $f(n) = \Omega(n^{\log_b a + \varepsilon}) \Rightarrow T(n) = \Theta(f(n))$

If $f(a)f(b) < 0$, then $\exists c \in (a,b): f(c) = 0$ Algorithm: 1. $c = \frac{a + b}{2}$ 2. If $f(a)f(c) < 0$: $b = c$, else $a = c$ 3. Repeat until $|b - a| < $ tolerance Convergence: $O(\log_2((b-a)/\varepsilon))$

$$x_{n+1} = x_n - \frac{f(x_n)}{f'(x_n)}$$ Quadratic convergence when $f'(\text{root}) \neq 0$ May fail if $f'(x_n) \approx 0$ or poor initial guess

$$x_{n+1} = x_n - f(x_n)\frac{x_n - x_{n-1}}{f(x_n) - f(x_{n-1})}$$ Approximates derivative using secant line Superlinear convergence: $\varphi = \frac{1+\sqrt{5}}{2} \approx 1.618$

$$P(x) = \sum_{i=0}^n y_i L_i(x)$$ where $L_i(x) = \prod_{j=0, j \neq i}^n \frac{x - x_j}{x_i - x_j}$ Unique polynomial of degree $\leq n$ through $n+1$ points

$$P(x) = f[x_0] + f[x_0,x_1](x-x_0) + f[x_0,x_1,x_2](x-x_0)(x-x_1) + \cdots$$ $f[x_i,x_{i+1}] = \frac{f[x_{i+1}] - f[x_i]}{x_{i+1} - x_i}$ More efficient for adding new points

Cubic spline: $S(x) = a_i + b_i(x-x_i) + c_i(x-x_i)^2 + d_i(x-x_i)^3$ Conditions: - $S(x_i) = y_i$ - $S'(x_i^-) = S'(x_i^+)$ - $S''(x_i^-) = S''(x_i^+)$

Composite Trapezoidal: $$\int_a^b f(x)\,dx \approx \frac{h}{2}[f(x_0) + 2f(x_1) + \cdots + 2f(x_{n-1}) + f(x_n)]$$ Error: $O(h^2)$ Composite Simpson's: $$\int_a^b f(x)\,dx \approx \frac{h}{3}[f(x_0) + 4f(x_1) + 2f(x_2) + 4f(x_3) + \cdots + f(x_n)]$$ Error: $O(h^4)$

$$\int_{-1}^1 f(x)\,dx \approx \sum_{i=1}^n w_i f(x_i)$$ Optimal choice of points $x_i$ and weights $w_i$ $n$-point Gauss rule exact for polynomials of degree $\leq 2n-1$

$$y_{n+1} = y_n + h \cdot f(x_n, y_n)$$ First-order accuracy: $O(h)$ Simple but may be unstable for large $h$

RK4 (Fourth-order): $$k_1 = hf(x_n, y_n)$$ $$k_2 = hf(x_n + h/2, y_n + k_1/2)$$ $$k_3 = hf(x_n + h/2, y_n + k_2/2)$$ $$k_4 = hf(x_n + h, y_n + k_3)$$ $$y_{n+1} = y_n + \frac{k_1 + 2k_2 + 2k_3 + k_4}{6}$$

$$z = x + iy = re^{i\theta} = r(\cos\theta + i\sin\theta)$$ $|z| = \sqrt{x^2 + y^2} = r$ $\arg(z) = \theta = \arctan(y/x)$ $z^* = x - iy = re^{-i\theta}$ (complex conjugate)

$$z_1z_2 = r_1r_2e^{i(\theta_1+\theta_2)}$$ $$\frac{z_1}{z_2} = \frac{r_1}{r_2}e^{i(\theta_1-\theta_2)}$$ De Moivre's theorem: $z^n = r^n e^{in\theta}$ $n$th roots: $z^{1/n} = r^{1/n} e^{i(\theta+2\pi k)/n}$, $k = 0,1,\ldots,n-1$

$$e^z = e^x(\cos y + i\sin y)$$ $$\sin z = \frac{e^{iz} - e^{-iz}}{2i}$$ $$\cos z = \frac{e^{iz} + e^{-iz}}{2}$$ $\log z = \ln|z| + i(\arg z + 2\pi n)$

$$f(z) = \sum_{n=0}^{\infty} a_n(z - z_0)^n$$ Radius of convergence: $R = \frac{1}{\limsup_{n \to \infty} |a_n|^{1/n}}$ Convergent for $|z - z_0| < R$

Simple pole at $z_0$: $$\text{Res}(f, z_0) = \lim_{z \to z_0} (z - z_0)f(z)$$ Pole of order $n$: $$\text{Res}(f, z_0) = \frac{1}{(n-1)!} \lim_{z \to z_0} \frac{d^{n-1}}{dz^{n-1}}[(z-z_0)^n f(z)]$$

Walk: sequence of vertices $v_0, v_1, \ldots, v_k$ Trail: walk with distinct edges Path: walk with distinct vertices Connected: path exists between any two vertices Distance $d(u,v)$: length of shortest path from $u$ to $v$

Eulerian path: uses every edge exactly once Exists iff graph connected and $\leq 2$ odd-degree vertices Eulerian cycle: closed Eulerian path Exists iff graph connected and all vertices even degree Hamiltonian path: visits every vertex exactly once

$\chi(G) = $ minimum number of colors needed $\chi(K_n) = n$ $\chi(C_n) = 2$ if $n$ even, $3$ if $n$ odd $\chi(\text{bipartite graph}) = 2$ Four Color Theorem: $\chi(\text{planar graph}) \leq 4$

Brooks' Theorem: If $G$ connected, not complete, not odd cycle, then $\chi(G) \leq \Delta(G)$ where $\Delta(G) = $ maximum degree

For integers $a, b$ with $b > 0$: $$a = qb + r \text{ where } 0 \leq r < b$$ $q = $ quotient, $r = $ remainder $a \equiv r \pmod{b}$

$$\gcd(a, b) = \gcd(b, a \bmod b)$$ Extended Euclidean Algorithm: $$\gcd(a, b) = ax + by$$ for some integers $x, y$ Time complexity: $O(\log \min(a, b))$

$$\gcd(a, b) \times \text{lcm}(a, b) = ab$$ If $\gcd(a, n) = 1$ and $\gcd(b, n) = 1$, then $\gcd(ab, n) = 1$ Bézout's identity: $\gcd(a, b) = ax + by$

$a \equiv b \pmod{n}$ iff $n \mid (a - b)$ Properties: $(a + b) \bmod n = ((a \bmod n) + (b \bmod n)) \bmod n$ $(a \times b) \bmod n = ((a \bmod n) \times (b \bmod n)) \bmod n$ Reflexive: $a \equiv a \pmod{n}$ Symmetric: $a \equiv b \implies b \equiv a \pmod{n}$ Transitive: $a \equiv b, b \equiv c \implies a \equiv c \pmod{n}$

$a^{-1} \pmod{n}$ exists iff $\gcd(a, n) = 1$ Finding inverse: use Extended Euclidean Algorithm $ax + ny = 1 \implies ax \equiv 1 \pmod{n} \implies a^{-1} \equiv x \pmod{n}$ Fermat's Little Theorem: If $p$ prime, $\gcd(a, p) = 1$: $$a^{-1} \equiv a^{p-2} \pmod{p}$$

Trial division: test divisibility up to $\sqrt{n}$ Time: $O(\sqrt{n})$ Sieve of Eratosthenes: find all primes $\leq n$ Time: $O(n \log \log n)$ Miller-Rabin: probabilistic primality test Time: $O(k \log^3 n)$ for $k$ rounds

Prime Number Theorem: $$\pi(n) \approx \frac{n}{\ln(n)}$$ where $\pi(n) = $ number of primes $\leq n$ There are infinitely many primes

$$\varphi(n) = |\{k : 1 \leq k \leq n, \gcd(k, n) = 1\}|$$ $\varphi(p) = p - 1$ for prime $p$ $\varphi(p^k) = p^k - p^{k-1} = p^{k-1}(p - 1)$ If $\gcd(m, n) = 1$: $\varphi(mn) = \varphi(m)\varphi(n)$

If $\gcd(a, n) = 1$, then: $$a^{\varphi(n)} \equiv 1 \pmod{n}$$ Fermat's Little Theorem (special case): If $p$ prime and $\gcd(a, p) = 1$: $$a^{p-1} \equiv 1 \pmod{p}$$

$f(n) = O(g(n))$ if $\exists c > 0, n_0$ such that $f(n) \leq c \cdot g(n)$ for all $n \geq n_0$ Upper bound: $f$ grows no faster than $g$ $f(n) = \Omega(g(n))$ if $g(n) = O(f(n))$ Lower bound: $f$ grows at least as fast as $g$ $f(n) = \Theta(g(n))$ if $f(n) = O(g(n))$ and $f(n) = \Omega(g(n))$ Tight bound: $f$ and $g$ grow at same rate

$$O(1) < O(\log n) < O(n) < O(n \log n) < O(n^2) < O(n^3) < O(2^n) < O(n!)$$ Logarithmic: binary search, balanced tree operations Linear: linear search, single loop Linearithmic: merge sort, heap sort Quadratic: nested loops, simple sorting Exponential: brute force subsets Factorial: brute force permutations

Prerequisite: sorted array Algorithm: ``` while low ≤ high: mid = (low + high) / 2 if arr[mid] == target: return mid elif arr[mid] < target: low = mid + 1 else: high = mid - 1 ``` Time: $O(\log n)$, Space: $O(1)$

Average case: $O(1)$ for search, insert, delete Worst case: $O(n)$ if many collisions Load factor $\alpha = \frac{n}{m}$ (items/buckets) Keep $\alpha < 0.75$ for good performance Collision resolution: chaining, open addressing

A problem has optimal substructure if optimal solution contains optimal solutions to subproblems Examples: shortest paths, matrix chain multiplication, optimal binary search trees, edit distance

Recursive algorithm solves same subproblems repeatedly Memoization: top-down approach, store results Tabulation: bottom-up approach, fill table Fibonacci: naive $O(2^n)$, DP $O(n)$

Select maximum number of non-overlapping activities Greedy strategy: sort by finish time, always pick earliest finishing activity Time: $O(n \log n)$

Optimal prefix-free binary codes Greedy strategy: repeatedly merge two nodes with minimum frequency Time: $O(n \log n)$

P: problems solvable in polynomial time NP: problems verifiable in polynomial time NP-Complete: hardest problems in NP NP-Hard: at least as hard as NP-Complete $P \subseteq NP$, but $P = NP$? is open question

Problem $A$ reduces to $B$ ($A \leq_p B$) if $A$ can be solved using polynomial number of calls to $B$ If $A \leq_p B$ and $B \in P$, then $A \in P$ Used to prove NP-completeness

Encryption: $E(x) = (x + k) \bmod 26$ Decryption: $D(y) = (y - k) \bmod 26$ Key space: 26 possible keys Vulnerable to frequency analysis

Encryption: $E(x) = (ax + b) \bmod 26$ Decryption: $D(y) = a^{-1}(y - b) \bmod 26$ Requirement: $\gcd(a, 26) = 1$ Key space: $\varphi(26) \times 26 = 12 \times 26 = 312$

Encryption: $C_i = (M_i + K_{i \bmod \text{keylen}}) \bmod 26$ Polyalphabetic substitution Broken by Kasiski examination and index of coincidence

Public: prime $p$, generator $g$ Alice: chooses $a$, sends $g^a \bmod p$ Bob: chooses $b$, sends $g^b \bmod p$ Shared secret: $K = g^{ab} \bmod p$ Security based on discrete log problem

Key Generation: Choose prime $p$, generator $g$, private key $x$ Public key: $y = g^x \bmod p$ Encryption of $M$: Choose random $k$, send $(g^k \bmod p, M \cdot y^k \bmod p)$ Decryption: $M = c_2 \cdot (c_1^x)^{-1} \bmod p$

Pre-image resistance: given $h$, hard to find $x$ with $H(x) = h$ Second pre-image resistance: given $x$, hard to find $x' \neq x$ with $H(x) = H(x')$ Collision resistance: hard to find $x, x'$ with $H(x) = H(x')$ Birthday paradox: expect collision after $\sqrt{2^n}$ inputs for $n$-bit hash

Digital signatures: sign hash instead of message Password storage: store $H(\text{password} + \text{salt})$ Proof of work: find nonce with $H(\text{block} + \text{nonce}) < \text{target}$ Data integrity: compare hash values

Signing: $S = H(M)^d \bmod n$ Verification: check if $S^e \equiv H(M) \pmod{n}$ Must use padding (PSS) to prevent attacks

Parameters: prime $p$, $q \mid (p-1)$, generator $g$ Private key: $x$, Public key: $y = g^x \bmod p$ Signing $M$: $k = $ random, $r = (g^k \bmod p) \bmod q$ $s = k^{-1}(H(M) + xr) \bmod q$ Signature: $(r, s)$ Verification: check if $r = ((g^{H(M)s^{-1}} \cdot y^{rs^{-1}}) \bmod p) \bmod q$

Minimize: $\mathbf{c}^T \mathbf{x}$ Subject to: $A\mathbf{x} = \mathbf{b}$, $\mathbf{x} \geq \mathbf{0}$ Can convert any LP to standard form: - $\max f \rightarrow \min(-f)$ - inequality $\rightarrow$ equality (add slack variables) - unrestricted variable $\rightarrow$ difference of non-negative variables

1. Start at basic feasible solution (vertex of polytope) 2. Check optimality conditions 3. If not optimal, move to adjacent vertex that improves objective 4. Repeat until optimal or unbounded Worst case: exponential Average case: polynomial

First-order condition: $\nabla f(\mathbf{x}^*) = \mathbf{0}$ Second-order condition: $\nabla^2 f(\mathbf{x}^*)$ positive definite Gradient descent: $\mathbf{x}_{k+1} = \mathbf{x}_k - \alpha_k \nabla f(\mathbf{x}_k)$ Newton's method: $\mathbf{x}_{k+1} = \mathbf{x}_k - [\nabla^2 f(\mathbf{x}_k)]^{-1} \nabla f(\mathbf{x}_k)$

KKT conditions for $\min f(\mathbf{x})$ subject to $g(\mathbf{x}) \leq \mathbf{0}$, $h(\mathbf{x}) = \mathbf{0}$: $\nabla f(\mathbf{x}^*) + \sum_i \lambda_i \nabla g_i(\mathbf{x}^*) + \sum_j \mu_j \nabla h_j(\mathbf{x}^*) = \mathbf{0}$ $g_i(\mathbf{x}^*) \leq 0$, $h_j(\mathbf{x}^*) = 0$ $\lambda_i \geq 0$, $\lambda_i g_i(\mathbf{x}^*) = 0$ (complementary slackness)

Convex set: $\forall \mathbf{x}, \mathbf{y} \in S, \forall \lambda \in [0,1]: \lambda\mathbf{x} + (1-\lambda)\mathbf{y} \in S$ Convex function: $f(\lambda\mathbf{x} + (1-\lambda)\mathbf{y}) \leq \lambda f(\mathbf{x}) + (1-\lambda)f(\mathbf{y})$ Properties: - Local minimum = global minimum - First-order condition sufficient for optimality

Barrier method: replace constraints $g(\mathbf{x}) \leq \mathbf{0}$ with penalty terms $-t \sum_i \log(-g_i(\mathbf{x}))$ As $t \to \infty$, solution approaches constrained optimum Polynomial time complexity for convex problems

1. Solve LP relaxation 2. If solution integer, update best bound 3. If not integer, branch on fractional variable 4. Recursively solve subproblems 5. Prune if bound worse than current best NP-hard in general, but practical for many instances

Add linear constraints (cuts) that remove fractional solutions but preserve all integer solutions Gomory cuts: derived from optimal LP tableau Problem-specific cuts often more effective