MAT2540/D670 – Discrete Structures II

We started Ch 10, on graphs. On Monday we introduced the basic definitions and terminology, and discussed some applications. We continued with some examples on Wednesday, and introduced some additional definitions.

Please start working on HW#3:

• Sec 10.1: #3-9 [we discussed some of these on Wednesday]
• Sec 10.2: TBA

Monday, March 17:

Wednesday, March 19:

We spent the class reviewing the topics for Exam #1, which will be on Wednesday, March 12. The exam will consist of exercises on the following topics/sections:

• Sec 5.1: proofs by induction
• Sec 5.2: proofs by strong induction
• Sec 5.3/5.4: recursively defined functions and recursive algorithms
• Sec 6.1: Counting techniques (product rule and sum rule)
• Sec 6.3: Permutations and combinations

Study the examples and concepts we discussed in class over the course of the semester, and the homework exercises from HW#1 and HW #2 (in particular, you can consult the solutions to the odd-numbered exercises in the back of the textbook).

We recapped the topics and did some additional examples in class:

We covered Sec 6.3 (combinations and permutations), and introduced Sec 8.1 (applications of recurrence relations). See below for snapshots of the blackboard.

We will have Exam #1 on Wednesday, March 12. It will cover Sec 5.1-5.4 and Sec 6.1-6.3, and be similar to the homework exercises from those sections, and and examples from those sections we covered in class.

If you didn’t hand in HW#2 on Thursday, you can still hand it in on Monday:

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

Monday, March 3:

Wednesday, March 5:

Thursday, March 6: