Held: Friday, 4 September 2015

Back to Outline 03 - Reflective Activities. On to Outline 05 - Divide and Conquer Approaches.

Summary

We continue our explorations of algorithm analysis.

Related Pages

• skiena-2-4.c - code for Skiena 2-4.
• [Summation formulas][http://polysum.tripod.com/]

Overview

• Asymptotic analysis, revisited.
• Other properties of Big-Oh notation.
• Careful loop counting.

Administrivia

• My normal office hours are MWF 11:00-11:50. I've added MWF 8:30-9:00. You sign up for those at https://rebelsky.youcanbook.me.

Upcoming Work

• For Monday: No additional reading.
• For Wednesday: Problems 2-1, 2-2, 2-3, 2-8, 2-13, 2-14, 2-15, 2-18, 2-23, 2-32, 2-37, any two interview problems from chapter 2.
  
  • Turn in hardcopy.
  • I prefer that you write your homework in LaTeX. If you don't know LaTeX, now is a good time to start learning!

Extra Credit

Academic

• CS Table, Tuesdays, topic tbd.
• CS Extras, Thursdays, topics forthcoming.
• Convo, Thursday, 11am.

Peer

• Men's Soccer, 5pm, 9/4 vs. Crown College
• Women's Soccer, 2pm, 9/5 vs. Simpson.

Asymptotic analysis, reviewed

• What have you learned about asymptotic analysis?
• What does it mean for a function to be in O(n), theta(N), omega(N)?
• How does the formality relate to algorithm analysis?

Additional properties of Big-Oh

• Prove that if f(n) is in O(g(n)) and g(n) is in O(h(n)) then f(n) is in O(h(n)).
• What other properties do you expect to be useful?

Careful loop analysis

• At times, we want to know an exact value for the number of steps executed, rather than a bound.
• And upper bounds can be far too estimated.
• To help us think about these things, it's helpful to do a few analyses in depth.
• You have some on your homework.
• We'll work on one together in class. 2-4 from Skiena.

function conundrum(n)
  r := 0
  for i := 1 to n do
    for j := i + 1 to n do
      for k := i + j − 1 to n do 
        r := r + 1
  return(r)

• Quick and dirty upper bound. Count the maximum number of repetitions of each loop and multiply.
• Accurate assessment: Fun with summations.