CS115. Discrete Structures for Computer Science
Offers an intensive introduction to discrete mathematics as it is used in computer science. Topics include functions, relations, sets, propositional and predicate logic, simple circuit logic, proof techniques, elementary combinatorics, and discrete probability.
Prerequisites: Mathematical preparation sufficient to take calculus at the college level.
Syllabus:
- Fundamental structures: Functions (surjections, injections, inverses, composition); relations (reflexivity, symmetry, transitivity, equivalence relations); sets (Venn diagrams, complements, Cartesian products, power sets); pigeonhole principle; cardinality and countability
- Basic logic: Propositional logic; logical connectives; truth tables; normal forms (conjunctive and disjunctive); validity; predicate logic; limitations of predicate logic; universal and existential quantification; modus ponens and modus tollens
- Digital logic: Logic gates, flip-flops, counters; circuit minimization
- Proof techniques: Notions of implication, converse, inverse, contrapositive, negation, and contradiction; the structure of formal proofs; direct proofs; proof by counterexample; proof by contraposition; proof by contradiction; mathematical induction; strong induction; recursive mathematical definitions; well orderings
- Basics of counting: Counting arguments; pigeonhole principle; permutations and combinations; recurrence relations
- Discrete probability: Finite probability spaces; conditional probability, independence, Bayes' rule; random events; random integer variables; mathematical expectation
Units covered:
| DS1 | Functions, relations, and sets | 6 | core hours |
| DS2 | Basic logic | 10 | core hours |
| DS3 | Proof techniques | 9 | core hours (of 12) |
| DS4 | Basics of counting | 5 | core hours |
| DS6 | Discrete probability | 6 | core hours |
| AR1 | Digital logic and digital systems | 3 | core hours (of 6) |
| | Elective topics | 1 | hour |
Notes:
This implementation of the Discrete Structures area (DS) compresses the core material into a single course. Although such a strategy is workable, many institutions will prefer to use two courses to cover this material in greater depth. For an implementation that uses the two-course model, see the descriptions of CS105 and CS106.
Online resources for CS115