Course:CPSC 320/Midterm 1 Reference Sheet

From UBC Wiki

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!

  • iff
  • iff ,
  • iff and ,
  • iff
  • iff ,

Also, if

  • , then
  • a non-zero constant, then
  • , then

(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 or , then

Analogy to Inequalities

  • if and only if
  • if and only if

It follows, where and :

Caution: For all exactly one must hold: or . Not all functions are asymptotically comparable.

Master Theorem

If and a constant in the base case, where can be either or , and then:

  • If for some , then
    • Dominated by leaf cost
  • If then,
    • Balanced cost
  • If for some and if for some constant and sufficiently large , then
    • 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:

  • a is not a constant

    non-polynomial difference between f(n) and

    a<1 cannot have less than one sub problem

    f(n) is not positive

    case 3 but regularity violation.

Also, Case 3 always hold when f = n^k and If

Log Laws

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


  • Arithmetic Series:
  • Sum of Squares:
  • Sum of Cubes:
  • Geometric Series: for real
  • Infinite decreasing:
  • Telescoping:


Decision Tree-Related Notes

  • for a list of elements, there's permutations
  • a binary tree of height has at most leaves
  • therefore, a binary tree with at least leaves must have height at least
  • to get the height of a tree: the longest path (say we divide by 3/2 at each level) finishes when , so the height is
  • , 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


The Silicon Downs : Furlongs of Asymptotic Complexity

"NEWS FLASH: Mounties Find Silicon Downs Fixed!"

  • Constant
  • Logarithmic ie.
  • Poly-Log
  • Linear
  • Log-Linear
  • Superlinear where: c is a constant > 0
  • Quadratic
  • Cubic
  • Polynomial where: k is a constant, "tractable"
  • Exponential where: c is a constant > 1, "intractable"

Stable Marriage Notes


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.


  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 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):

  If there is one building (x1,h,x2)
    output (x1,h),(x2,0)
    divide into B1[1..floor(n/2)] and B2[floor(n/2)+1..n]

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
      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.