CS365/Schedule/2004-01-13

Note: You are looking at a static copy of the former PineWiki site, used for class notes by James Aspnes from 2003 to 2012. Many mathematical formulas are broken, and there are likely to be other bugs as well. These will most likely not be fixed. You may be able to find more up-to-date versions of some of these notes at http://www.cs.yale.edu/homes/aspnes/#classes.

Administrative details of course: see CS365/Syllabus
What are algorithms?
- Platonic ideal of a program.
- Input, output, resource consumption.
- Goal is to produce correct output for any input using fewest resources.
- Semi-formal definition: an algorithm is a program that can be implemented by a TuringMachine that carries out some desired task by executing a sequence of primitive operations (usually either given by the problem specification or assumed to be the default operations that a TuringMachine can do).
Why study algorithms?
- To learn ProblemSolvingTechniques.
- To write more efficient programs.
  - By being able to quickly estimate efficiency of different approaches.
  - By coming up with your own algorithms.
  - By adapting other people's algorithms for your own purposes.
- To satisfy the requirements of the ComputerScienceMajor.
  - Because you like ComputerScience.
  - Because you want to take more advanced courses.
The fundamental problem
- Computers are bigger than brains
- Need to organize computation so that we can understand it
  - DesignPatterns
  - Composition
  - Iteration
  - Recursion
How do we study algorithms?
- Describing algorithms
  - Natural language descriptions
  - Pseudocode
- Analysis framework
  - ComputationalModel
  - Correctness
    - Specifications
    - Proofs of correctness
  - Efficiency
    - Constant-time operations
    - Asymptotic performance
- The universal quantifier
  - Any claim we make about an algorithm has to apply for all inputs
    - We can't predict how our programs will be used
    - Our programs will be used enough that any bad input is likely to come up eventually
  - Well-formed input requirements can be made part of the specification
  - Algorithms that work only some of the time are called heuristics---we won't study them much in this class
- Algorithms are mathematical objects
  - Nobody likes mathematics
  - But we have to use it anyway
    - We can't test algorithms directly
    - Mathematicians have been studying abstract objects rigorously forever---let's exploit their tools
  - What kind of mathematics do we need?
    - For proving correctness
      - Induction arguments
    - For analyzing performance
      - Inequalities
      - Sums
      - Recurrence relations
      - AsymptoticNotation and limits
    - Warning: a little bit of calculus will slip in when we do sums and limits
What will we study in this course?
- AlgorithmAnalysis
- AlgorithmDesign
  - ProblemSolvingTechniques
  - AlgorithmDesignTechniques
- Specialized classes of algorithms
- Limitations
  - ComputationalComplexityTheory
  - P vs NP (PvsNp); NP-hard problems