- Math colloquium
- “Learning Mathematics in a Language Not Your Own”
- Dr. Kyriakos Petakos
- Wednesday, Sept. 16, 2:45
- Newton 204
- Extra credit (up to 2 points of homework credit) for attending and writing ca. 1 paragraph re what struck you as interesting/important and why
- First part of section 2.1
- Establish loop invariant (condition true on every iteration)
- Use it to imply final result is correct
- Like mathematical induction, except it stops at loop exit
- Examples
- Sum of i from i=1 to n
- Finding invariants
- Formalize intuitive understanding of how loop works
- Design algorithm around invariants
- Finding invariants
- Inner loop from insertion sort (see textbook for code)
- Loop moves items bigger than key right in list to make room
to insert key in its sorted position
- Candidate invariant, holding before first statement in loop body: for all k such that i ≤ k < j, A[k] > key
- Loop moves items bigger than key right in list to make room
to insert key in its sorted position
- Sum of i from i=1 to n
- Finish loop invariants