Algorithms and Data Structures (INF1, Autumn'05)
Lecture 2
Main topic: Correctness of algorithms.
Lecture Plan
- partial correctness, total correctness
- pre- and post-conditions
- recursion vs. iteration
- mathematical induction
- assertions, invariants
- examples
Reading
- Pseudocode appendix from: Discrete Mathematics and its
Applications (available in the course folder for photocopying).
Only a few pages worth reading!
- Chapter 1 of Algorithms and Data Structures:
Design, Correctness and Analysis by Jeffrey H. Kingston
[Note: Page 10 can be safely skipped as it gives some details of
a correctness argument that we won't need.]
Appendix A (less than three pages!) tells you all you need to know to read
the Eiffel code used in the book.
-
Chapter 5 of Algorithmics: The Spirit of Computing by David Harel
(available in the course folder for photocopying)