CSCI 220 (Fall 1998): Class Notes

Simple Induction

Complete (or Strong) Induction

Proving Termination

Correctness of Recursive Algorithms

Justification of Inductive Arguments

Loop Invariants (I)

Loop Invariants (II)

Loop Invariants (III)

Correctness of Iterative Binary Search

Correction of Exercise 1.1

Correction of Exercise 1.2

Correction of Exercise 1.5 (I)

Correction of Exercise 1.5 (II)

Correction of Exercise 1.5 (III)

Maximum Subvector (I)

Maximum Subvector (II)

Evaluation of Polynomials (I)

Evaluation of Polynomials (II)

Evaluation of Polynomials (III)

Evaluation of Polynomials (III)

Evaluation of Polynomials (IV)