SUNY Geneseo Department of Computer Science
Introduction
to Theory
{Date}
CSci 141, Fall 2003
Prof. Doug Baldwin
Return to
List of Lectures
Previous Lecture
Questions?
Intro to Theory
(Sections 3.1 - 3.3, 3.5)
Modus Ponens?
Proofs
- Logical way to prove an algorithm
"Theorem" = the claim you want to prove
Proof process
- Intuitive, informal, guess that some claim is right
- Why?
- Test it
- Examine intuition
- Rigor
Correctness
- Algorithm is correct if end result corresponds to postconditions
2 kinds of theorem in computing
- "This algorithm/program is correct"
- "This algorithm uses x amount of some resource"
MakeChange example, fewest possible coins
- Proof by contradiction
- Show that it is impossible for something not to be true
- Proofs can you help you find bugs in incorrect algorithms
Next
Introduction to Experimentation
- (Motivation: Next week's lab will ask you to do an experiment to determine
whether it takes a robot longer to move or to hit a wall)
Read Chapter 4
Mini-Assignment: Identify a likely source of experimental error in measuring
how long it takes a robot to move or hit a wall.
Next Lecture