Course:CPSC 320/Midterm 1 Reference Sheet

CPSC 320 2009W2 Exam Reference Sheet

Do not remove: This reference sheet is the appendix for Midterm #1. Only the first 4 printed pages will be used; so be compact!

• $f(n)\in O(g(n))$ iff $\exists c\in \mathbf {R^{+}} ,\exists n_{0}\in \mathbf {Z^{+}} ,\forall n\in \mathbf {Z^{+}} ,n\geq n_{0}\rightarrow f(n)\leq cg(n)$
• $f(n)\in \Omega (g(n))$ iff $g(n)\in O(f(n))$, $\exists c\in \mathbf {R^{+}} ,\exists n_{0}\in \mathbf {Z^{+}} ,\forall n\in \mathbf {Z^{+}} ,n\geq n_{0}\rightarrow 0\leq cg(n)\leq f(n)$
• $f(n)\in \Theta (g(n))$ iff $f(n)\in O(g(n))$ and $g(n)\in O(f(n))$, $\exists c_{1},c_{2}\in \mathbf {R^{+}} ,\exists n_{0}\in \mathbf {Z^{+}} ,\forall n\in \mathbf {Z^{+}} ,n\geq n_{0}\rightarrow 0\leq c_{1}g(n)\leq f(n)\leq c_{2}g(n)$
• $f(n)\in o(g(n))$ iff $\forall c\in \mathbf {R^{+}} ,\exists n_{0}\in \mathbf {Z^{+}} ,\forall n\in \mathbf {Z^{+}} ,n\geq n_{0}\rightarrow f(n)<cg(n)$
• $f(n)\in \omega (g(n))$ iff $g(n)\in o(f(n))$, $\forall c\in \mathbf {R^{+}} ,\exists n_{0}\in \mathbf {Z^{+}} ,\forall n\in \mathbf {Z^{+}} ,n\geq n_{0}\rightarrow 0\leq cg(n)<f(n)$

Also, if $\displaystyle \lim _{n\to \infty }{\frac {f(n)}{g(n)}}=$

• $\infty$, then $f(n)\in \omega (g(n))$
• a non-zero constant, then $f(n)\in \Theta (g(n))$
• $0$, then $f(n)\in o(g(n))$

(Plus bear in mind that (1) L'Hopital's rule may be handy, and (2) the limit is not always well-defined!)

L'Hopital's Rule:

If $\displaystyle \lim _{n\to \infty }{\frac {f(n)}{g(n)}}={\frac {0}{0}}$ or $\displaystyle \lim _{n\to \infty }{\frac {f(n)}{g(n)}}={\frac {\infty }{\infty }}$, then $\displaystyle \lim _{n\to \infty }{\frac {f(n)}{g(n)}}={\frac {f(n)'}{g(n)'}}$

Analogy to Inequalities

• $f(n)=O(g(n))$ if and only if $g(n)=\Omega (f(n))$
• $f(n)=o(g(n))$ if and only if $g(n)=\omega (f(n))$

It follows, where $a\rightarrow f(n)$ and $b\rightarrow g(n)$:

• $f(n)=O(g(n))\approx a\leq b$
• $f(n)=\Omega (g(n))\approx a\geq b$
• $f(n)=\Theta (g(n))\approx a=b$
• $f(n)=o(g(n))\approx a<b$
• $f(n)=\omega (g(n))\approx a>b$

Caution: For all $a,b,\in \mathbf {R}$ exactly one must hold: $a<b,a=b$ or $a>b$. Not all functions are asymptotically comparable.

Master Theorem

If $\displaystyle T(n)=aT(''n/b'')+f(n)$ and a constant in the base case, where $''n/b''$ can be either $\lfloor n/b\rfloor$ or $\lceil n/b\rceil$, $a>=1$ and $b>1$ then:

• If $f(n)\in O(n^{log_{b}{a-{\mathcal {E}}}})$ for some ${\mathcal {E}}>0$, then $T(n)\in \Theta (n^{log_{b}a})$
  • Dominated by leaf cost
• If $f(n)\in \Theta (n^{log_{b}a})$ then, $T(n)\in \Theta (n^{log_{b}a}lgn)$
  • Balanced cost
• If $f(n)\in \Omega (n^{log_{b}{a+{\mathcal {E}}}})$ for some ${\mathcal {E}}>0$ and if $\displaystyle af(''n/b'')\leq cf(n)$ for some constant $\displaystyle c<1$ and sufficiently large $n$, then $T(n)\in \Theta (f(n))$
  • Dominated by root cost - It is important in this case to check that f(n) is well behave. More specifically,
  • For sufficient large n, a*f(n/b) <= c*f(n)

The following equations cannot be solved using the master theorem:

• $T(n)=2^{n}T\left({\frac {n}{2}}\right)+n^{n}$
  a is not a constant

  $T(n)=2T\left({\frac {n}{2}}\right)+{\frac {n}{\log n}}$
  non-polynomial difference between f(n) and $n^{\log _{b}a}$

  $T(n)=0.5T\left({\frac {n}{2}}\right)+n$
  a<1 cannot have less than one sub problem

  $T(n)=64T\left({\frac {n}{8}}\right)-n^{2}\log n$
  f(n) is not positive

  $T(n)=T\left({\frac {n}{2}}\right)+n(2-\cos n)$
  case 3 but regularity violation.

Also, Case 3 always hold when f = n^k and If $f(n)\in \Omega (n^{log_{b}{a+{\mathcal {E}}}})$

Log Laws

For all real a > 0, b > 0, c > 0, and n,

• $a=b^{\log _{b}a}$
• $\log _{c}ab=\log _{c}a+\log _{c}b$
• $\log _{b}a^{n}=n\log _{b}a$
• $\log _{b}a={\frac {\log _{c}a}{\log _{c}b}}$
• $\log _{b}{\frac {1}{a}}=-\log _{b}a$
• $\log _{b}a={\frac {1}{\log _{a}b}}$
• $a^{\log _{b}c}=c^{\log _{b}a}$
• $\log 1=0$

Summation

• Arithmetic Series: $\displaystyle {\sum _{k=1}^{n}(k)=1+2+\dots +n}={\frac {1}{2}}n(n+1)$
• Sum of Squares: $\displaystyle {\sum _{k=0}^{n}(k^{2})}={\frac {n(n+1)(2n+1)}{6}}$
• Sum of Cubes: $\displaystyle {\sum _{k=0}^{n}(k^{3})}={\frac {n^{2}(n+1)^{2}}{4}}$
• Geometric Series: $\displaystyle {\sum _{k=0}^{n}(x^{k})=1+x+x^{2}+\dots +x^{k}}={\frac {x^{n+1}-1}{x-1}},$ for real $x\neq 1$
• Infinite decreasing: $\displaystyle {\sum _{k=0}^{\infty }(x^{k})={\frac {1}{1-x}},for|x|<1}$
• Telescoping: $\displaystyle {\sum _{k=1}^{n-1}(a_{k}-a_{k+1})=a_{0}-a_{n}}$

Exponents

• $a^{0}=1$
• $a^{1}=a$
• $a^{-1}={\frac {1}{a}}$
• $(a^{m})^{n}=a^{mn}$
• $a^{m}\times a^{n}=a^{m+n}$

Decision Tree-Related Notes

• for a list of $n$ elements, there's $n!$ permutations
• a binary tree of height $d$ has at most $2^{d}$ leaves
• therefore, a binary tree with at least $n$ leaves must have height at least $\lceil \lg n\rceil$
• to get the height of a tree: the longest path (say we divide by 3/2 at each level) finishes when $\left({\frac {2}{3}}\right)^{k}n=1\rightarrow k=log_{\frac {3}{2}}n$, so the height is $log_{\frac {3}{2}}n$
• $\lg(n!)\in \Theta (n\lg n)$, which we can establish by proving big-O and big-Ω bounds separately (pumping "up" or "down" the values of the terms in the factorial and the overall number of terms as needed)

Stirling's Approximation

• $\ln n!\sim n\ln n-n\ .$

Derivatives

• ${\frac {d}{dx}}a^{f(x)}=a^{f(x)}*{\frac {d(f(x))}{dx}}ln(a)$
• ${\frac {d}{dx}}\ln(x)={\frac {1}{x}},\qquad x>0$
• ${\frac {d}{dx}}\log _{a}(x)={\frac {1}{x\ln(a)}}$

The Silicon Downs : Furlongs of Asymptotic Complexity

"NEWS FLASH: Mounties Find Silicon Downs Fixed!"

• Constant $\in O(1)$
• Logarithmic $\in O(logn)$ ie. $log_{k}n,logn^{2}\in O(logn)$
• Poly-Log $\in O(log^{k}n)$
• Linear $\in O(n)$
• Log-Linear $\in O(nlogn)$
• Superlinear $\in O(n^{1+c})$ where: c is a constant > 0
• Quadratic $\in O(n^{2})$
• Cubic $\in O(n^{3})$
• Polynomial $\in O(n^{k})$ where: k is a constant, "tractable"
• Exponential $\in O(c^{n})$ where: c is a constant > 1, "intractable"

Stable Marriage Notes

Algorithm:

initialize all men in M and all women in W to unengage
while (an unengaged man with at least one woman on his preferance list remains)
     do choose such a man m (element of) M
       propose to the next woman w(element of)W on his preference list
     if( w is unengaged)
          then engage m to w
     else if w prefers m to fiance m'
           then break engagement of m' to w
          engage m to w
      cross w off m's preferance list
report set of engaged pairs as final matching.

Notes:

1. All executions of the stable marriage sort produce the same matching, and all men end up with their "best possible partner".
2. In the stable matching set each woman is paired with her worst valid partner.
3. This algorithm terminates after at most $n^{2}$ iterations of the while loop.

Skyline Problem & Algorithm

For input B[1..n] buildings as triples (left, height, right), we get output of tuples (pos of height change, new height):

SKYLINE-ALG(B) {
  If there is one building (x1,h,x2)
    output (x1,h),(x2,0)
  Else
    divide into B1[1..floor(n/2)] and B2[floor(n/2)+1..n]
    out1=SKYLINE-ALG(B1)
    out2=SKYLINE-ALG(B2)
    OUTPUT=MERGE(out1,out2)
}

The merge step is as follows:

MERGE(out1,out2) {
  h1=h2=0, currx=0,curry=0
  While out1 or out2 is not empty do {
    If out1 and out2 start at the same x-coord
      currx=first x-coord in out1
      h1=first y-coord in out1
      h2=first y-coord in out2
      DELETE first entries in out1 and out2
    Else If out1 has smallest first x-coord
      currx=first x-coord in out1
      h1=first y-coord in out1
      DELETE first entry in out1
    Else
      currx=first x-coord in out2
      h2=first y-coord in out2
      DELETE first entry in out2
    If max(h1,h2)!=curry
      APPEND (currx,max(h1,h2)) to output
  }
  APPEND (currx,0) to output
}

Proving a Loop Invariant

1. induction variable: Number of times through the loop
2. base case: Prove the invariant true before the loop starts
3. inductive hypothesis: Assume the invariant holds just before begininng some (unspecified) iteration of the loop.
4. inductive step: prove the invariant holds at the end of that iteration (right before the next iteration)
5. extra-bit: make sure the loop will eventually terminate.