main page — COMP 526 Efficient Algorithms
Unit 0: Admin & Proof Techniques
This is an archived version of this module from Spring 2022.
Click here for the current iteration.
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
- slides on proof techniques
- lecture notes on administrativa
- Video 0-1 (2022-01-31):
Welcome, teaching mode, overview, assessment, Campuswire, video presentation, prior knowledge survey
- Video 0-2 (2022-02-03):
§0.1 Proof templates
- Video 0-3 (2022-02-03):
§0.2 Mathematical induction
- Video 0-4 (2022-02-03):
§0.3 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: