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

1. Know logical proof strategies for proving implications, set inclusions, set equality, and quantified statements.
2. Be able to use mathematical induction in simple proofs.
3. Know techniques for proving termination and correctness of procedures.

Material

• slides on administrativa
• slides on proof techniques

• lecture notes on proof techniques

• Video 0-1 · transcript (2021-02-08, 27:14): Welcome, teaching mode, prior knowledge survey
  
  Chapters

  5:08 Poll
  7:50 Conversacin
  16:16 Learning Experience
  20:38 Prior Knowledge Survey
  
• Video 0-2 · transcript (2021-02-10, 33:45): Overview, assessment, Campuswire, video presentation
  
  Chapters

  0:18 Overview
  2:27 Plan
  11:26 Clickers
  14:34 Class Feed
  16:30 QA
  19:14 QA Goals
  21:26 QA Gamification
  22:52 Research Literature
  28:34 Philosophy
  
• Video 0-3 · transcript (2021-02-10, 27:33): §0.1 Proof templates
  
  Chapters

  1:35 Defining a formal proof
  4:44 Logical operators and notation
  9:45 Analyzing logical implications
  15:03 Proof strategies
  24:52 Equivalence and set proofs
  
• Video 0-4 · transcript (2021-02-10, 8:20): §0.2 Mathematical induction
  
  Chapters

  0:45 Quantified statements
  1:47 Existential quantifiers
  3:06 Nesting quantifiers
  5:28 Inductive proof
  6:30 Inductive step
  
• Video 0-5 · transcript (2021-02-10, 7:41): §0.3 Correctness proofs (part 1)
  
  Chapters

  2:00 Proving termination
  4:21 Loop invariants
  
• Video 0-6 · transcript (2021-02-16, 18:53): §0.3 Correctness proofs (part 2)
  
  Chapters

  0:33 Recap
  7:09 Proof
  15:27 Summary
  

For this week’s tutorial, see Unit 1.

---

Syllabus  ⋅  Unit 1