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
Proof Techniques
CS 2800 AEW ∙ August 2021
Covers: Direct and contrapositive proofs, proofs by contradiction, counterexamples, case analysis
Propositional Logic
CS 2800 AEW ∙ August 2021
Covers: Logical operations, truth tables, logical equivalence, translating sentences into logic
Predicate Logic
CS 2800 AEW ∙ August 2021
Covers: Predicates, quantifiers, understanding expressions with multiple quantifiers
Sets
CS 2800 AEW ∙ August 2021
Covers: Set operations, set equivalence proofs, cardinality, power sets, set builder notation
Functions
CS 2800 AEW ∙ August 2021
Covers: Arrow diagrams, function composition, injection, surjection, invertibility, cardinality
Induction
CS 2800 AEW ∙ August 2021
Covers: Many examples of proofs by induction
Relations
CS 2800 AEW ∙ August 2021
Covers: Inverting and composing relations, properties of relations, partial orders, equivalence relations
Graphs
CS 2800 AEW ∙ August 2021
Covers: The graph of a relation, transitive closure, degree, walks, paths, and cycles
Number Theory
CS 2800 AEW ∙ August 2021
Covers: Divisibility, modular arithmetic, converting between bases, Euclidean algorithm, fast exponentiation, the RSA cryptosystem
Combinatorics 1
CS 2800 AEW ∙ August 2021
Covers: The sum, product, bijection, and division rules, permutations, combinations
Combinatorics 2
CS 2800 AEW ∙ August 2021
Covers: Binomial identities, the inclusion-exclusion theorem, counting arrangements, the pigeonhole principle
Probability 1
CS 2800 AEW ∙ August 2021
Covers: Probability spaces, events, discrete distributions, conditional probability, independence, Bayes’ theorem
Probability 2
CS 2800 AEW ∙ August 2021
Covers: Random variables, pdfs and cdfs, binomial distribution, expectation, variance, Markov and Chebyshev inequalities
Automata
CS 2800 AEW ∙ August 2021
Covers: Strings and languages, operations on languages, DFAs, the pumping lemma, NFAs, regular expressions, Kleene’s theorem