CSC152 2004F, Class 2: More About Core Topics

Admin:
* Sorry about syllabus.  Still forthcoming.
* Sorry about memory trouble.  I'm now over 40.
* Homework for tomorrow: Find a definition of OOP and compare to mine.

Overview:
* Programming Paradigms
* Object-Oriented Programming
* Abstract Data Types and Algorithms
* Stuff from Scheme

Computer Science is the Study of Problem Solving
* There are different ways to express the solution to a problem.
* Example: Making cookies
  * Inexperienced: Do this, do that
    * Sift the flour and sugar together.
    * Cream butter in separate dish by squishing against the side with a flat spoon
  * Experience cook: List ingredients
* Example: Computing the inner product of two N element vectors, A and B
  * Pascal
  sum := 0
  for i = 1 to N do
    sum := sum + A[i]*B[i]
  * Scheme
  (apply + (map * A B))
* Four primary paradigms
  * Imperative: Do this, do that (traditional recipe style)
  * Declarative: Here are the facts, figure out what to do
  * Functional: Programming is based on functions
  * Object-oriented: Programming is based on objects
* Functional:
  * Everything is based on an equation (or a function or something similar that looks like math)
  * Order is not always important (or explicit)
  * Functions can operate on other functions

Object-Oriented Programming
* Two motivations
  * Early (1960's): Built for simulation.  One program "object" per real world "object"
  * Modern (now): Better construction of big systems.
    * Encapsulation/Information hiding: One part of the system has lmited knowledge of the rest of the system.
    * Software reuse.
* Just as functional programming focuses on *functions* object-oriented programming focuses on *objects*
  * An object is a collection of data (fields) and capabilities (methods)
  * A customer object might have
    * Name
    * Money in wallet/purse
    * Patience level
    * Shopping goals
  * A customer might be able to
    * Select a line
    * Purchase items
    * Scream when frustrated
  * Some data are internal, some are somewhat external
* Object-oriented feature 1: ENCAPSULATION
  * Related data together
  * Related methods with appropriate data
  * Data hidden
* Object-oriented feature 2: INHERITANCE
  * Once you design one kind of object, you can reuse that design for similar objects
  * Once I've designed people and said that people have names, genders, and goals, I can say that a customer is a person and automatically get the name, gender, and goal defined.
  * Once I've said that cars have four wheels, run on fuel, have accellerators (method) and brakes (method), I can say that a race car is a kind of car
* Object-oriented feature 3: POLYMORPHISM
  * Once you design something that works with one type of object, it can "automatically" work with all related objects.

This is also a course in Abstract Data Types (ADTs) and Data Structures (DSs)
* The way you organize data has a significant effect on the algorithms you design.
* We must therefore study ways to arrange data.
* Abstract data types: The "why" and "what" of the arrangement
* E.g. list
  * Basic philosophy: A collection of elements whose size you can change.
  * Key methods: Create (null, cons), Look at 'em (car, cdr), Check if they're empty (null?)
    (Apply functions, ...)
  * Applications: Stick 'em together or rearrange
* E.g. vector
  * Basic philsophy: A collection of elements of fixed size with quicker access to individual elements
  * Key methods: Create (vector), Look at 'em (vector-ref), Change 'em (vector-set!), Check their size (vector-length)
* Data structure: The "how" of the arrangement: How do we set up data so that we can do the key methods well?
  * Lists: Using cons cells / pairs
  * Vectors: 

* Abstract data type: Phone book
  * Idea: Given a name, find the phone number
  * Methods: Create (), Look at 'em (getNumber)
* Implementation:
  * List of name/number pairs
  * Sorted vector of name/number pairs (use binary search)
  * Tree of name/number pairs
  *