Algorithms

Thu Jan 24

First : finish going over the homework that was due Tuesday, from chap 1. My answers are posted.

Any questions on the chap 1 material ?

Today : continue discussion of chap 2 material :

• O() notation :
  • f is O(g) => f(x) < c g(x)
  • f is Ө(g) => c1 g(x) < f(x) < c2 g(x)
  • f is Ω(g) => f(x) > c g(x)
  • ... all for constant multiple of g, for x big enough
• understanding log2(n) and 2**n
• making plots to visualize time(n) vs n behavior
  • some sample notebooks
  • run at jupyter.marlboro.college
  • log plots
  • curve fitting visualization
• "divide and conquer" idea
  • binary search
  • Exponentiation by squaring
• timing python programs :
  • unix "time" command line utility, i.e. "time python yourprogram.py"
  • python : import time; start=time.time(); ... do stuff ... ; print(time.time()-start)