Discrete Math - The MKD Remix (CSC230 Version)

This lesson can be used to introduce the concept of conjecture, lay the groundwork for proof, and provide a nonarithmetic/nonalgebraic example for proof by mathematical induction that can be referred to later when mathematical induction is formally introduced.
The graph theory content needed by students is minimal and can be learned just-in-time, so this lesson can be used very early in the course. Note that it may be important to mention to students that this activity does not involve literally shaking the hands of other people.
A possible extension to this lesson could be to examine the corresponding properties for vertices of directed graphs.
I find that using Handshake as the introductory lesson has an advantage over using the intended counting problem lesson: The graph theory content is likely to be unfamiliar to most students so team members are more likely to adhere to their specific team roles and work collaboratively. I’ve found that many students already “know” how to do the counting problems (but perhaps incorrectly) from their previous learning, so some team members can dominate their team’s discussion which prevents the team from working collaboratively as a whole.

This lesson involves counting arguments and seems to have been designed as an accessible entry point for all students.
However, as mentioned earlier, some students in each team may know how to solve the problems already while others may not, and this can undermine collaboration and adherence to the assigned team roles.

This lesson focuses on using rules of inference to make a valid argument, and analyzing invalid arguments (e.g., ones that include a converse or inverse error.) Some teams may try to use AI to solve the problem, which often brings up the opportunity to talk about common logical fallacies (i.e., the converse error and the inverse error.) In fact, the lesson includes examples from AI that have made these common errors.

This lesson introduces algorithms and their analysis using recurrence relations and recursively-defined functions, and the comparison of the linear search and binary search algorithms for sorted lists. I use it to introduce recursion and recurrence relations, and the need to follow an algorithm carefully, step-by-step. I use this several weeks before formally introducing the search algorithms and their complexity analysis.

I do this lesson after recurrence relations to try to focus on the relationships in the number triangle. Try to stress the reasoning needed to justify Pascal’s identity, as many students will focus on "getting the right numbers" instead.

Teams use an assembly-line approach to starting one proof, completing a second proof started by another team, then verifying a third proof completed by the second team. This activity works well with trios of teams completing each other’s proofs. In my experience, the student teams find the problems with algebraic equations the easiest (but not very easy at all.) Most undergraduate students have no experience using the kind of nesting arguments needed to work with inequalities. I’ve tried to use some "visual questions" (say, about properties of star graphs) but the teams would need much more practice with recursive definitions than they’ve had up to and including this course.

I use this as the final activity, typically with only 3 students per team. The content involves graph edge colorings, presented as a game. I have found that the game context makes this lesson highly engaging. At this point in the semester, students are used to working in their team roles so this engagement does not lead them to abandon those roles.