Math for algorithms

23 Oct 2018

Math basics for algorithm

$\sum_{k=1}^n k^2 = \frac {n(n+1)(2n+1)}{6}$ $\sum_{k=1}^n k^3 = \frac { n^2(n+1)^2}{4}$

$\sum_{k=1}^n (ca_k+b_k) = c\sum_{k=1}^n a_k + \sum_{k=1}^n b_k$ $\sum_{k=1}^n \Theta\left(f(k)\right) = \Theta \left( \sum_{k=1}^n f(k) \right)$

\[\sum_{k=0}^n x^k = 1 + x + x^2 + \ldots + x^n = \frac {x^{n+1} -1} {x-1}\] \[\sum_{k=0}^{\infty} x^k = \frac {1} {x-1}\]

\[H_n = 1 + \frac{1}{2} + \frac{1}{3} + \frac{1}{4} + \ldots + \frac{1}{n} = \sum_{k=1}^n \frac{1}{n} = \ln{n} + O(1)\]

\[\sum_{k=0}^{\infty} kx^k = \frac {x} {(1-x)^2}\]

\[\sum_{k=1}^{n} (a_k - a_{k-1}) = a_n - a_0\]

$\sum_{k=0}^{n-1} (a_{k-1} - a_k) = a_0 - a_n$ $\sum_{k=1}^{n-1} \frac{1}{k(k+1)} = \sum_{k=1}^{n-1} (\frac{1}{k} - \frac{1}{k+1}) = 1- \frac{1}{n}$

数学归纳法
确定级数中各项的界
\[\sum_{k=1}^{\infty} \frac{1}{k} = \lim _{n \to \infty} {\sum_{k=1}^{n} \frac{1}{k} } = \lim _{n \to \infty} {\Theta(\lg n)} = \infty\]

\[H_n = \sum_{k=1}^n \frac{1}{n} = 1 + \frac{1}{2} + \frac{1}{3} + \frac{1}{4} + \ldots + \frac{1}{n} \leq \ln{n} + 1\]

通过积分求和的近似
- if $f(x)$ 单调递增: $\int_{m-1}^{n} f(x)\,dx \leq \sum_{k=m}^n f(k) \leq \int_{m}^{n+1} f(x)\,dx$
- if $f(x)$ 单调递减: $\int_{m}^{n+1} f(x)\,dx \leq \sum_{k=m}^n f(k) \leq \int_{m-1}^{n} f(x)\,dx$
$H_n = \sum_{k=1}^n \frac{1}{n} \geq \int_{1}^{n+1} \frac{1}{x}\,dx = \ln{(n+1)}$ $\sum_{k=2}^n \frac{1}{n} \leq \int_{1}^{n} \frac{1}{x}\,dx = \ln{(n)}$
\[H_n = \sum_{k=1}^n \frac{1}{n} \leq \ln{n}+1\]

Illustrate function call stack
Describe how to convert recursion to iteration
- one function call
- 2 or more function calls
- tail recursion
PERMUTATION

PERM(A, k)
  if(k == n)
    PRINT(A)
  for i = 1 to n 
    SWAP(A, i, k)
    PERM(A, k+1)
    SWAP(A, i, k)


PERM(A, 1)