Materials for Teaching Discrete Mathematics

Welcome to the SIGCSE Committee on the Implementation of a Discrete Mathematics Course's collection of course materials. The Committee's task was to develop and disseminate models for a one-semester course for Computing Curriculum 2001's Discrete Structures area. Part of this effort included identifying exercises and examples that instructors can use in such courses.

Materials have been contributed by Committee members, participants in workshops run by Committee members, and others interested in this project. We particularly thank Susanna Epp, Elana Epstein, Andy Felt, Peter Henderson, Tara Holm, Brian Hopkins, David Hunter, Don Josephson, Carol Kajor, Gerald Kruse, Linda Lesniak, Jerry Lodder, Fred Rispoli, Kathryn Shafer, Shai Simonson, LeenKiat Soh, and Howard Whitson for their contributions. It is our understanding that all materials have been contributed for non-profit, non-commercial educational use and adaptation. However, ownership of each example or exercise rests with its contributor, and specific items may have tighter or looser requirements for use. See the individual items for details.

Materials are organized according to the Computing Curriculum 2001 units within discrete structures, namely...

• DS1. Functions, Relations, and Sets
• DS2. Basic Logic
• DS3. Proof Techniques
• DS4. Basics of Counting
• DS5. Graphs and Trees
• DS6. Discrete Probability

A final group labeled "Courses" contains links to the Web sites of entire courses. While these courses are not deliberate implementations of any of the Committee's models, and don't necessarily satisfy the Committee's charge to develop one-semester courses, they do present a wealth of ideas and materials that people designing or teaching courses based on the Committee's models may find helpful.

Each exercise or other item is represented by a descriptive title, which is a link to the item as provided by its contributor, and by a few words that identify specific concepts covered by the item. Click on the links to retrieve individual items.

DS1. Functions, Relations, and Sets

• Keys and Locks. Properties of functions.
• The Coin Problem. Set operations.
• Counting Subsets. Power sets, set-related algorithms.
• Transitive Closure. Transitive closure and reflexivity.
• The Josephus Problem. Equivalence classes. Solutions available in Scheme and Java.
• Bridge Crossing. Constraint satisfaction.
• Widget Weighing. Set analysis.

DS2. Basic Logic

• Personal Relationships. Simple inference.
• Activities Worksheet. Basic logic.
• Three Gifts. Inference.
• Conditional Logic. The contrapositive.
• Kickball Problem. Inference.
• Logical Equivalence. Propositional equivalance.
• Or Logic. Disjunction.
• Propositional Logic. Implication, disjunction, negation.
• Time. Inference.
• Two Pots. Inference and contradiction.
• Defective Switch. Inference.
• Puzzle Piece Sequence. Inductive reasoning.
• Chuck-a-Luck Logic. Propositional logic notation.

DS3. Proof Techniques

• List Partitioning. Inductive/recursive thinking.
• Gray Codes. Inductive/recursive thinking.
• Jigsaw Puzzle. Induction.
• Tournament Matches. Inductive/recursive thinking.
• Truth Table Construction. Inductive/recursive thinking.
• The Josephus Problem. Recursive thinking. Solutions available in Scheme and Java.
• Pile Splitting. Strong induction. Algorithms available in Scheme (1, 2, 3) and Java.
• Two-Color Theorem. Proof by induction.
• Points in a Circle. Counter-example.
• The Four-Color Theorem. Case-study in proof, notably a famous flawed "proof."
• ProofBuilder. A tool to help students learn to do proofs.

DS4. Basics of Counting

• Counting Subsets. Counting issues related to sets.
• Bugs in a Jar. Inductive counting, exponential growth.
• Mouse on a Grid. Inductive counting.
• Figurate Numbers. Geometric counting with applications to algorithm analysis.
• Card Trick. Combinations and permutations.
• Catalan Numbers. Recurrence relations.
• Chuck-a-Luck Logic. Combinations.

DS5. Graphs and Trees

• Relations and Graphs. Transitive closure.
• Way-Finding. Paths and cycles
• Card Trick. Graphs as problem models.
• Two-Color Theorem. Graphs as problem models.
• Geodesic Dome. Euler paths. Answers available.
• Tree Reconstruction. Tree traversals.
• Text Compression. Huffman codes.
• The Four-Color Theorem. Colorability.

DS6. Discrete Probability

• Chuck-a-Luck Logic. Probability, expected value.

Courses

(Please note that because many of these courses are ongoing and offered every year or even every semester/quarter, their instructors reserve the right to temporarily restrict access to exercises, exams, solutions, and similar materials.)

• UNL CSE235 S02. Introduction to Discrete Structures, University of Nebraska - Lincoln, Spring 2002.
• UNL CSE235 S03. Introduction to Discrete Structures, University of Nebraska - Lincoln, Spring 2003.
• UNL CSE235 S04. Introduction to Discrete Structures, University of Nebraska - Lincoln, Spring 2004.
• Stonehill CS201. Discrete Mathematics for Computer Scientists, Stonehill College.
• Stonehill CS202. Discrete Mathematics for Computer Scientists II, Stonehill College