Core Module 5: Inductions

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.
  • 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:

Leave a Reply

Your email address will not be published. Required fields are marked *