Shaun Conlon
CS 211
Section 6
3/27/2003 Notes

Topics for this week:
-A5 help/hints/guidelines
-Big-Oh notation
-Searching/Sorting

1) A5 help/hints/guidelines

  Here are some important points for A5:
    
    Assignment grading:
    -Q1: 30   Q2: 10    Q3: 10    Q4: 50
    -for Q4, GUI: 10 pts, 2x2 board: 25 pts, 3x3: 15 pts
    Doubly Linked List:
    -the iterator returns Integers, not Nodes
    Tic Tac Toe:
    -board size is general
    -get the 2x2 puzzle working first (tree is small, easy to test)
      -but, do not hard code the tree for the 2x2 case
    -space/time constraints: for 3x3 ~5 minutes max to build tree
      -we will run at command prompt (no extra space allocation)
    -optimization is necessary to get 3x3 to work
       -> warning: library functions (e.g. Math.pow) take lots of time
    -represent the board as an integer
    -think carefully about how to make each step of tree building faster

2) Big-Oh Notation

  Here are some things that you are expected to be able to do with complexity
problems:
    -derive T(n) from code - see lecture notes
    -derive O() from T(n) - see lecture notes
    -prove that f(n) = O(g(n))
    -arrange O() expressions in order from fastest to slowest

  To prove that f(n) = O(g(n)), you must find a "witness pair", (c, n0) that   
satisfy the following:

  f(n) <= c * g(n) for all n >= n0

  Example proof:

  prove that log2(n) = O(log3(n)) and log3(n) = O(log2(n))
    [log2(n) is log base 2 of n]

  We will use the fact that log2(n) = log(n)/log(2) (any base)

  So we need to find a c that satisfies:

    log2(n) <= c * log3(n)
    log(n)/log(2) <= c * log(n)/log(3)

  You can see that if we pick any c >= log(2)/log(3) we have satisfied the 
equation for all n >= 1.  So we can pick a witness pair (3,1).

  The proof for the other equation is very similar.  I leave it to you to work 
out.

3) Searching/Sorting

  For searching and sorting, it is important to know two things about every 
algorithm:

  -how it works (be able to show each step on an example list)
  -what the worst-case (and sometimes average case) running time is

  Here is a list (not guaranteed to be exhaustive):

  * Linear Search = O(n)
    -works by stepping through list until element found
  * Binary Search = O(log(n))
    -only works on sorted lists
    -works by looking at middle element and then recursively searching
     on either first or second half of list
  * Selection Sort = O(n^2)
    -each iteration finds the smallest (or largest) element of the
     unsorted portion of the array and swaps it into place
  * Merge Sort = O(n*log(n))
    -splits the list in half, calls merge sort on each half, then
     merges the two sorted halves back together
  * Quick Sort = O(n^2), but on overage O(n*log(n))
    -finds a pivot and arranges elements so everything less than pivot
     is places before pivot and everything after pivot is placed after
     the pivot.  Then calls quicksort recursively on the part before the
     pivot and the part after the pivot.

Email me (sc235) with any questions.