Month: February 2025 (Page 1 of 2)

We covered Sec 6.2 (the pigeonhole principle).

I also handed out Quiz #1, which is a take-home quiz with a couple exercises on proofs by induction. The quiz is due Monday (March 3); the pdf of the quiz is available in OpenLab Files.

In addition to the quiz, continue working on HW#2 (due date: next Thurs, March 6):

• Sec 5.4: #3, 4, 8
• Sec 6.1: #2-4, 7-12, 27, 28
• Sec 6.2: #1-3

In Classes 5 and 6 last week, we introduced the material from Sec 5.4 (recursive algorithms) and Sec 6.1 (counting techniques).

We reviewed this material in Class 7, after reviewing earlier material on induction and recursive definitions (building on the latter, and the HW#1 exercises, we also previewed material from Sec 8.2, on linear recurrence relations).

Please work on HW#2 (due date TBA):

• Sec 5.4: #3, 4, 8
• Sec 6.1: #2-4, 7-12, 27, 28
• Sec 6.2: TBA  

We revisited the example from Sec 5.2 of a proof by strong induction, and showed how we can write an algorithm using the idea of the proof.

We then covered the beginning of Sec 5.3, on recursive definitions. In particular, we focused on recursively defined functions on the natural numbers. See the examples we covered in class, and Examples 1-3 in the textbook (pp366-368).

For HW#1, please write out solutions to the following exercises

Sec 5.1: #3 & 4

Sec 5.2: #3 & 4

Sec 5.3: #1-3

(A screenshot of the latter exercises is also included below. For the Sec 5.1 and 5.2 exercises, see the previous Class Recaps.)