September 21 lecture notes - sorting

 -------------------------------------------------------------

 I) questions
   1) recent homework
   2) general progress


 II) wikipedia : Print["Hello world"]

 III) algorithms
   1) what     : nit-picky recipes
   2) why      : 'cause all the cool kids are into 'em
   3) how long : the key question
      a) most of these problems have a size N
      b) we'd like to know how the problem scales as N gets bigger,
         O(N^2), O(N log N), O(N!), ...
      c) examples: 
          i.  put the names of 1 million city folks in order
          ii. arrange 1000 people in every possible living permutation
         Which is easier?
	  
 IV) searching
   1) traveling salesman problem
   2) chess and games like that
   3) google
   4) natural language translation
   5) ...

 V) closely related : sorting
   1) cool in and of itself, *and*
   2) leads to "data structures" : not just lists but trickier things
   3) animated - see for example
       http://www.geocities.com/SiliconValley/Network/1854/Sort1.html
       http://www.cs.ubc.ca/spider/harrison/Java/sorting-demo.html
   4) trade-offs : time vs space (common theme in this stuff)
   5) recursion - often simple way to describe procedure,
                  once you see how it works