15-110: Fall 2010
Class Notes:  Algorithm and Analysis

• Arithmetic (a familiar domain)
  
  
• Subtraction
  
  
• Subtraction Algorithms
  
  
• The Traditional Method
  
  
• Subtract by Adding (10's Complement):
  
  
• Example:
   534
  -378
  
  
• Step 1:  Negate by complementing each digit, then adding 1 (this is the "10's Complement")
  
  -378 --> 621 + 1 --> 622 (So 622 is -378 represented in 10's Complement!)
  
  
• Step 2:  Now add these numbers, ignoring the final carry!
  
   534
  +622
  ----
  1156
  
  
• Question:  What happens if the result is negative?  How can we tell?  What should we do?
  
  
• Analysis
  
  
• Informally compare these two subtraction algorithms.  Which do you prefer?  Why?
  
  
• Would you expect one of these algorithms to be much faster than the other?
  
  
• Multiplication
  
  
• Multiplication Algorithms
  
  
• The Traditional Method
    247
   x 38
    ---
   1976
  +7410
   ----
   9386
  
  
• The Lattice Method:
  
  
  
• Repeated Addition (The Hopeless Method)
    247 x 38 = 247 + 247 + ... + 247 = 9386
                    (38 times)
  
  
• The Egyptian Method (By Clever Addition)
  Step 1:
    247 x  1 =  247
    247 x  2 =  247 +  247 =  494
    247 x  4 =  494 +  494 =  988
    247 x  8 =  988 +  988 = 1976
    247 x 16 = 1976 + 1976 = 3952
    247 x 32 = 3952 + 3952 = 7904
  
  Step 2:
    247 x 38 =   494  (247 x  2)
                 988  (247 x  4)
               +7904  (247 x 32)
               -----
                9386
  
  
• Analysis
  
  
• Informally compare these four multiplication algorithms.  Which do you prefer?  Why?
  
  
• Question:  How does the Egyptian Method make use of binary representations?
  
  
• Question:  How can we be sure that the Egyptian Method is better than the Repeated Addition (Hopeless) Method?
  
  
• If you use the Repeated Addition (Hopeless) Method to add N + N, show that the maximum number of additions is O(N).
  
  
• If you use the Egyptian Method to add N + N, show that the maximum number of additions is O(logN).
  
  
• Sketch a graph of the functions N and logN.
  
  
• Are you convinced?
  
• Search
  
  
• Search Algorithms
  
  
• Linear Search
  Check each element in turn, from first to last.
  
  
• Binary Search
  Check middle element each time and eliminate half the remaining elements from consideration on each pass.
  
  
• Activity:  Find a name in a phone book
  
  
• Activity:  The number-guessing game (with a fixed range)
  
  
• Analysis
  
  
• Question:  Show that linear search requires at most O(N) comparisons.
  
  
• Question:  Show that binary search requires at most O(logN) comparisons.
  
  
• Question:  about how many checks must binary search make on a list with 1 thousand elements?  1 million?  1 billion?
  
  
• Binary search is obviously faster, but when must we use linear search instead?
  
  
• Sorting
  
  
• Sorting Algorithms
  
  
• Selectionsort
  Select smallest unsorted element, swap to front of unsorted list, repeat.  (Or largest, and swap to back.)
  
  
• Mergesort (iterative)
  Sort by 1's, then by 2's, then by 4's, then by 8's, etc.  At each step, merge two sorted sublists into one larger sorted sublist..
  
  
• Activity:  Step-by-Step sorting simulations (See xSortLab in The Most Complex Machine)
  
  
• Choose "Selection Sort" on the right.  Click on the "Fast" button.  Then "Step" through the sort.
  
  
• Question:  Does this version of selectionsort find the smallest or largest element at each step?
  
  
• Choose "Merge Sort" on the right.  Then "Step" through the sort.
  
  
• Question:  Why does mergesort use an extra array?
  
  
• Practice:  Given a snapshot of either selectionsort or mergesort, predict the next step.
  
  
• Activity:  Timing sorting simulations (Again see xSortLab, but choose "Timed Sort" at the top)
  
  
• Question:  What happens to the run time when you double the array size in selectionsort?  Triple?  Quadruple?  See the pattern?
  
  
• Question:  How does mergesort compare when you double the size?  Triple?  Quadruple?
  
  
• Question:  How large an array can you sort using selectionsort in 0.1 seconds?  In 1 second?  In 10 seconds?
  
  
• Question;  Repeat the previous question using mergesort.  Impressed?
  
  
• Analysis
  
  
• Show that selectionsort requires O(N²) steps (comparisons and swaps or copies).
  
  
• Show that mergesort requires O(NlogN) steps (comparisons and swaps or copies).
  
  
• Compare the values of N² and NlogN  for various values of N.  Do you see why mergesort is so much better?
  
  
• Say we need to find an element in an unsorted list with N elements.  Would it be faster to use linear search, or to first mergesort the list and then use binary search?