Lesson 2.1: Correctness
Class Meeting:
| Section | Slides | Annotated Slides | Video |
| 12–1PM | 2.1-correctness-203-1221.pdf Download 2.1-correctness-203-1221.pdf | PDF Download PDF |
Posted in Zoom cloud recordings |
| 1–2PM | 2.1-correctness-1pm.pdf Download 2.1-correctness-1pm.pdf | 2.1-correctness-1pm-annotated.pdf Download 2.1-correctness-1pm-annotated.pdf |
Posted in Zoom cloud recordings |
| 4–5PM | 2.1-correctness-4pm.pdf Download 2.1-correctness-4pm.pdf | 2.1-correctness-4pm-annotated.pdf Download 2.1-correctness-4pm-annotated.pdf |
Posted in Zoom cloud recordings |
Readings:
- Carrano & Henry: 11.1
- Epp : Chapter 5.5
- Zych C++ pointers.pdf
- Zych C++ arrays.pdf
Summary:
Proving that an algorithm does what you say it does is a challenge! How do you communicate the reliability of your approach? Who is going to believe you if you simply say, "it just works!" or "I tried it, and it never failed..."? In this lesson we learn how to prove, by arguing logically, that the code we write actually does what we promise. We also learn selection sort along the way.
Learning Outcomes:
Upon completion off this lesson, students will be able to:
- identify and articulate loop invariants for simple iterative functions
- prove the correctness of simple iterative functions using a 5 step process
- recognize and execute selection sort on an array of values
- evaluate the running time of selection sort
- use the selection sort loop invariant to determine an iteration number