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
- Composition
- Iteration
- Recursion

- How do we study algorithms?
- Describing algorithms
- Natural language descriptions
- Pseudocode

- Analysis framework
- 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

- Any claim we make about an algorithm has to apply for all inputs
- 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

- For proving correctness

- Describing algorithms
- What will we study in this course?
- Specialized classes of algorithms
- Limitations
P vs NP (PvsNp); NP-hard problems