**To-Do Date: Feb 20 at 11:59pm**

Reading: AIDMA** Chapter 8** (many parts can be skipped if you’ve taken CS201, see below). As a preview, they cover:

- 8.1: covers mathematical induction.
- Induction is a hard topic to grasp at the first glance. If you find yourself confused by the first few pages of AIDMA 8.1, you may consider reading MCSLinks to an external site. 5.1 first before going back to AIDMA 8.1 again. This is because:
- MCS 5.1 mainly discusses an easier variant of induction: it assumes there is only one base case P(0), while the theorem is to be proved for all nonnegative integers (so n≥0), which makes the concept marginally easier to understand.
- On the other hand, AIDMA (more generally) defines the base case as P(a), which enables the theorem to be proved for all n≥a.
- AIDMA also explicitly discusses more topics like the approach in doing induction proofs, which is why it is chosen as the official required reading.

- In AIDMA Example 8.19, you will find the proof for the generalized form of De Morgan’s law, which we took for granted in the first few recitations.

- Induction is a hard topic to grasp at the first glance. If you find yourself confused by the first few pages of AIDMA 8.1, you may consider reading MCSLinks to an external site. 5.1 first before going back to AIDMA 8.1 again. This is because:
- 8.2: covers recursive algorithms.
*Can be skipped or a quick skim if taken CS201*. - 8.3.1-8.3.3: covers solving recurrence relations…
*which we already discussed in module 3!*So this should be a quick recap.*Skip 8.3.4 (linear recurrence relations).* - 8.4: analyzing recursive algorithms using recurrence relations;
*can be skipped or a quick skim if taken CS201.*

There is no Canvas prepare quiz for CM5. Instead, please complete PL practice 5.

To earn a satisfactory completion for CM5:

- Get both questions in PL practice (unlimited tries until LDoC)
- Get a completion on recitation work by either attending or submitting on Gradescope
- Get a satisfactory or above on the Gradescope assignment – Note that Gradescope assignment for CM5 is made up through PL – see the announcement Groups of 3 allowed for CM7-8; CM5 makeup instructions; EM assignment grading; CM1-5 completion status
- Get all 3 questions in the PL homework (unlimited tries until LDoC)OR
- Get an excellent on all Gradescope assignment questions
- Get all 3 questions in the PL homework (unlimited tries until LDoC)