main page — COMP 526 Efficient Algorithms
Unit 0: Admin & Proof Techniques
This is an archived version of this module from Spring 2021.
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
- Video 0-1 (2021-02-08):
Welcome, teaching mode, prior knowledge survey
- Video 0-2 (2021-02-10):
Overview, assessment, Campuswire, video presentation
- Video 0-3 (2021-02-10):
§0.1 Proof templates
- Video 0-4 (2021-02-10):
§0.2 Mathematical induction
- Video 0-5 (2021-02-10):
§0.3 Correctness proofs (part 1)
- Video 0-6 (2021-02-16):
§0.3 Correctness proofs (part 2)
For this week’s tutorial, see Unit 1.