CS 2800: Discrete Structures
Over the summer of 2021, I worked to develop materials for the support course for CS 2800. In the support course, students revisit the material and work in groups on additional exercises. The worksheets are listed chronologically, and each corresponds to roughly one week of class material. Inspiration for many of the questions comes from Lehman, Leighton, and Meyer's Mathematics for Computer Science.
Worksheets
Covers: Direct and contrapositive proofs, proofs by contradiction, counterexamples, case analysis
Covers: Logical operations, truth tables, logical equivalence, translating sentences into logic
Covers: Predicates, quantifiers, understanding expressions with multiple quantifiers
Covers: Set operations, set equivalence proofs, cardinality, power sets, set builder notation
Covers: Arrow diagrams, function composition, injection, surjection, invertibility, cardinality
Covers: Many examples of proofs by induction
Covers: Inverting and composing relations, properties of relations, partial orders, equivalence relations
Covers: The graph of a relation, transitive closure, degree, walks, paths, and cycles
Covers: Divisibility, modular arithmetic, converting between bases, Euclidean algorithm, fast exponentiation, the RSA cryptosystem
Covers: The sum, product, bijection, and division rules, permutations, combinations
Covers: Binomial identities, the inclusion-exclusion theorem, counting arrangements, the pigeonhole principle
Covers: Probability spaces, events, discrete distributions, conditional probability, independence, Bayes’ theorem
Covers: Random variables, pdfs and cdfs, binomial distribution, expectation, variance, Markov and Chebyshev inequalities
Covers: Strings and languages, operations on languages, DFAs, the pumping lemma, NFAs, regular expressions, Kleene’s theorem