15-110 Spring 2011
Class Notes:  A Gentle Introduction to Analysis

• Correctness:
• Correctness:  Does the algorithm work as advertised?
• How to check?
• In 15-110:
• Informal reasoning
• Some simple invariants
• For example:  In selection sort, after K passes, the smallest K elements are always sorted.
• Lots of testing (but does this prove anything?)
• And beyond:
• Formal reasoning
• Formal verification
  
• Activity:  try to explain why each algorithm we covered this week (satisfiability, linear search, binary search, selection sort, merge sort) is in fact correct.
  

• Efficiency
• Efficiency:  How many resources (time, space, bandwidth, etc) does the algorithm use?  For this week, we'll focus on time.  That is, how fast is the algorithm?
• How to check:
• This week:
• Informal reasoning
• Some timing tests
• To time Selection Sort or Merge Sort:
• xSortLab applet (by David Eck)
• At the top, select "Timed Sort"
• At the bottom, select "Selection Sort" or "Merge Sort" as appropriate
• At the top, select a reasonable starting size for your array, say ten thousand (10,000)
• At the bottom, click "Start Sorting" and wait...
• Write down what you wish to measure ("Approximate Compute Time" is a nice place to start)
• Repeat, trying different sizes of arrays.
• Question:  what happens to the compute time when you repeatedly double the size of the array?
• Soon...:
• Introduction to Big-O
• Activity:
• For large enough inputs, the algorithms we covered this week (satisfiability, linear search, binary search, selection sort, merge sort) can be placed in a strict order from fastest to slowest.  Find that order, and explain your reasoning.