Notes@HKU by Jax

Recursion

Solves a problem by breaking it down into smaller instances of the same problem. If you can solve a smaller instance of the problem, you can solve a larger one.

  1. Base Case(s): The simplest instance(s) of the problem that can be solved directly without further recursion.
  2. Recursive Case(s): More complex instances of the problem that are solved by breaking them down and making recursive calls.

Tower of Hanoi

Goal: Move nn disks from peg A  ⟹  CA \implies C using peg BB.

Rules: Only one disk can be moved at a time, and a disk can only be placed on top of a larger disk.

We define the problem as H(num,from,to,via)H(num, from, to, via):

  1. Move top n−1n-1 disks A  ⟹  BA \implies B via CC: H(n−1,A,B,C)H(n-1, A, B, C)
  2. Move 1 disk A→CA \to C
  3. Move top n−1n-1 disks B  ⟹  CB \implies C via AA: H(n−1,B,C,A)H(n-1, B, C, A)

Recurrence relation

Recurrence relation / equation

A mathematical equation which is defined in terms of itself.

f(n)={1n=12f(n−1)+1n>1f(n)=\begin{cases}\quad1&n=1\\2f(n-1)+1&n>1\end{cases}

Solve a recurrence relation - subsitution method

We "solve" a recurrence relation by finding a closed-form expression for f(n)f(n) in terms of nn.

  1. Expand the relation as f(n)f(n) to 3 levels
  2. Observe the pattern of f(n)f(n)
  3. Generalize the pattern in terms of the level kk
  4. Using the base case to define kk in terms of nn
  5. Subsitute kk back into the generalization

Example

Relevant mathematics

  1. Geometric series: Sn=a(1+r+r2+⋯+rn−1)=arn−1r−1S_n = a(1 + r + r^2 + \cdots + r^{n-1}) = a\frac{r^n - 1}{r-1}
  2. Arithmetic series: Sn=n(a1+an2),n=number of terms,a=first / last termS_n = n(\frac{a_1+a_n}{2}),\quad n=\text{number of terms}, a=\text{first / last term}
  3. Factorial: n!=n×(n−1)×(n−2)×⋯×1n! = n \times (n-1) \times (n-2) \times \cdots \times 1
  4. Falling factorial: n(k)=n(n−1)(n−2)⋯(n−k+1)=n!(n−k)!n^{(k)} = n(n-1)(n-2)\cdots(n-k+1)=\frac{n!}{(n-k)!}
  5. Logarithm: ak=b  ⟹  k=log⁡aba^k=b\implies k=\log_a b
  6. Logarithm property: klog⁡a=alog⁡kk^{\log a} = a^{\log k}

The master theorem

The master theorem can give us the order of growth (Big Theta) of a recurrence relation.

For T(n)=a⋅T(nb)+f(n),T(1)=c,a,c>0, b>1, f(n)∈Θ(nk), d≥0T(n) = a\cdot T(\frac{n}{b}) + f(n),\quad T(1) = c,\quad a, c > 0,\ b > 1,\ f(n)\in \Theta(n^k),\ d\geq 0, we have:

T(n)={Θ(nlog⁡ba)if a>bkΘ(nklog⁡n)if a=bkΘ(nk)if a<bkT(n) = \begin{cases} \Theta(n^{\log_b a}) & \text{if } a > b^k \\ \Theta(n^k \log n) & \text{if } a = b^k \\ \Theta(n^k) & \text{if } a < b^k \end{cases}

Mathematical induction

Mathematical induction

A method of mathematical proof that proves a statement for all natural numbers.

  1. Base case: Prove the statement for the first natural number in the statement's range.
  2. Inductive step: Assume the statement is true for nn, then prove it is also true for n+1n+1.

Example

Edit on GitHub

Previous

COMP2119 Notes for HKU

Next

Algorithm Analysis

On this page