CSC151.01 2007S, Class 01: An Introduction to Algorithms

Admin:
* Yes, we will get the torture light fixed soon!  (But not during class.)
* Do Homework 1 (due tomorrow).
* Read Linux and the MathLAN 
* Upcoming talks (extra credit for attending)
  * Johanna Meehan on vocation, Thursday, 11:00 a.m.
  * John David Stone on Life, Thursday, 4:15 p.m.
    * A simple solitaire board game designed by John Horton Conway
	* Unexpectedly beautiful

Overview:
* Introduction; What is CS?
* An Algorithm for Making Simple Sandwiches.

SO ... what is Computer Science?
* The study of computers
* Based on observation
  * First observation: When I use computers (well, when anyone uses
    computers) there are LOTS OF ERRORS
* Form hypotheses and devise experiments to test those hypotheses
  * Hypothesis: If I do X rather than Y, I'll get less errors
  * Random group assignment, group one does X, group two does Y,
    look at the outcome in terms of error counts.
* If a field has science in the name (e.g., Policital Science, Economic
  Science) IT'S NOT
* And we don't really study computers
* So what do we study?  And how?
  * We study *computation* 
    * That is, instructions for doing things (algorithms)
	* And the representation of information for such computation
  * We study computation 
    * As Engineers: By building things (programs or algorithms)
	* As Mathematicians: By proposing theorems about them and proving
	  those theorems
	* As Scientists: By proposing hypotheses and testing them
	* As Humanists: By considering the human implications of the algorithms
	  and software we write.
* Key issue:
  We write sets of instructions, and worry about their efficiency and
  accuracy

It's time for an example
Sam attempts to make a peanut-butter and jelly sandwich
* Told to "grab plate with two hands and place on table",
  * Sam places it on its side
  * But the students are lucky, and the plate falls correctly
* Told to "Open the bag of bread",
  * Sam pulls at the two ends
  * Fortunately, one group of students gave essentially those
    instructions
* Told to "Pull out two pieces",
  * Sam grabs from the middle
  * Sam ends up with literal pieces - small bits of bread, rather
    than slices
  * No one had suggestions for getting whole slices, but, in the
    interests of time, we took them out anyway
* Told to "Grasp peanut butter jar by non-dominant hand",
  * Sam grasps it upside down
  * issue resolved with "with the lid pointing toward the ceiling"
* Told to "Grasp lid with dominant hand and unscrew counter clockwise,"
  * Sam did so successfully
  * Unfortunately, there is a paper seal underneath.  
  * In the interests of the health of our peanut-allergic students, we
    will leave the jar sealed.
BREAK ... write the jelly part

What might you have learned from this exercise?
* Know your data - E.g., we had to know that the jelly jar had a 
  pop-open lid (or might have a pop-open lid) and the direction in
  which the twisty-tie was oriented.
* Be precise - ambiguity leads to doom
* Incorrect or vague instructions can lead to infinite computation
  * Be particularly careful about these instructions
* Working in teams often leads to better solutions
* It can still be fun when things go wrong
* Computers are SENTIENT AND MALICIOUS