Algorithm Design

Steps:

1. Formulate the problem precisely
2. Design an algorithm
3. Prove the algorithm is correct
4. Analyze its runtime

Algothrm design techniques:

• Greedy Algorithm
• Divide and Conquer
• Dynamic Programming
• Network Flow

Complexity:

• An algorithm is efficient if its running time is a polynomial in the input size $T$
  • The running time is upper bounded by $c.T^d$ for some constants $c,d>0$
  • ex: brute force can solve Gale Shapley Algorithm in $n!$
• 2 main complexities:
  • Time Complexity
  • Space Complexity

Algorithm’s running time:

• To measure a Efficient Algorithm
• $f(n)$ is asymptotically bounded by $g(n)$
  • if $g(n)$ is asymptotically upper bound: Big O Notation
  • if $g(n)$ is asymptotically lower bound: Big Omega Notation
  • if $g(n)$ is asymptotically tight bound: Big Theta Notation
• Propositions:
  1. if $\underset{n\to \infty }{\lim }\frac{f(n)}{g(n)}=c$ for some constant $c>0$ then $f(n)=\Theta (g(n))$
     • Proof: $c-ϵ\le \frac{f(n)}{g(n)}\le c+ϵ$ by definition
     • $(c-ϵ)g(n)\le f(n)\le (c+ϵ)g(n)$
     • by definition of Big Theta notation, it is true
  2. if $\underset{n\to \infty }{\lim }\frac{f(n)}{g(n)}=0$ then $f(n)=O(g(n))$
  3. if $\underset{n\to \infty }{\lim }\frac{f(n)}{g(n)}=\infty$ then $f(n)=\Omega (g(n))$
• To find which notation a function belongs to, do $\frac{f(n)}{g(n)}$

Some classes of function:

• Polynomials:
  • $f(n)={\sum }_{k=0}^d{a}_k{n}^k=O(n^d),a_d>0$
  • as $\underset{n\to \infty }{\lim }\frac{f(n)}{n^d}=a_d>0$
• Logarithms:
  • ${\log }_a(n)=\Theta ({\log }_{b}n)$ for every $a>1$ and $b>1$
  • as $\underset{n\to \infty }{\lim }\frac{{\log }_{a}n}{{\log }_{b}n}=\frac{1}{{\log }_{b}a}=c$
• Logarithms and Polynomials:
  • ${\log }_{a}n=O(n^d)$ for every $a>1$ and every $d>0$
  • as $\underset{n\to \infty }{\lim }\frac{{\log }_{a}n}{n^d}=0$
• Exponentials:
  • $n^d=O(r^n)$ for every $r>1$ and every $d>0$
  • as $\underset{n\to \infty }{\lim }\frac{n^d}{r^n}=0$
• Factorials:
  • $n!=2^{\Theta (n\log n)}$
  • as by Stirling’s Fomula $n!\approx \sqrt{2\pi n}(\frac{r}{e}{)}^n$

Computational Intractability

P vs NP Problem

Approximation Algorithm

---