main page — COMP 526 Efficient Algorithms
Unit 0: Admin & Proof Techniques
This unit covers:
- organization of the module (administrative part)
- strategies for mathematical proofs
- mathematical induction
- loop invariants
Learning outcomes
- Know logical proof strategies for proving implications, set inclusions, set equality, and quantified statements.
- Be able to use mathematical induction in simple proofs.
- Know techniques for proving termination and correctness of procedures.
Material
- slides on administrativa
- lecture notes on administrativa
- Video 0-0 (2023-09-28):
Welcome, teaching mode, overview, assessment, academic integity, Campuswire, prior knowledge survey
- Video 0-1 (2023-09-29):
§0.1 Random shuffle motivation
- Video 0-2 (2023-09-29):
§0.2 Proof templates, random shuffle motivation
- Video 0-3 (2023-09-29):
§0.3 Mathematical induction, Towers of Hanoi
- Video 0-4 (2023-09-29):
§0.4 Correctness proofs
Further reading and sources
A much more in-depth introduction to proof techniques, with many examples and exercises can be found, e.g., here:
The loop invariants are the center piece of Hoare Logic for program verification. More background on Hoare Logic is given for example here: