CS105. Discrete Structures I

Prerequisites: Mathematical preparation sufficient to take calculus at the college level.

Syllabus:

• Introduction to logic and proofs: Direct proofs; proof by contradiction; mathematical induction
• 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
• Boolean algebra: Boolean values; standard operations on Boolean values; de Morgan's laws
• Propositional logic: Logical connectives; truth tables; normal forms (conjunctive and disjunctive); validity
• Digital logic: Logic gates, flip-flops, counters; circuit minimization
• Elementary number theory: Factorability; properties of primes; greatest common divisors and least common multiples; Euclid's algorithm; modular arithmetic; the Chinese Remainder Theorem
• Basics of counting: Counting arguments; pigeonhole principle; permutations and combinations; binomial coefficients

Units covered:

DS1	Functions, relations, and sets	9	hours (6 core + 3)
DS2	Basic logic	5	core hours (of 10)
DS3	Proof techniques	4	core hours (of 12)
DS4	Basics of counting	9	hours (5 core + 4)
AR1	Digital logic and digital systems	3	core hours (of 6)
	Elementary number theory	5	hours
	Elective topics	5	hours

Notes:
This implementation of the Discrete Structures area (DS) divides the material into two courses. CS105 covers the first half of the material and is followed by CS106, which completes the core topic coverage. Because the material is stretched over two courses -- as opposed to CS115 which covers the material in a single course -- many of the units are given more coverage than is strictly required in the core. Similarly, the two-course version includes additional topics, reducing the need to cover these topics in more advanced courses, such as the introductory course in algorithmic analysis (CS210).

Although the principal focus is discrete mathematics, the course is likely to be more successful if it highlights applications whose solutions require proof, logic, and counting. For example, the number theory section could be developed in the context of public-key cryptography, so that students who tend to focus on the applications side of computer science will have an incentive to learn the underlying theoretical material.

Online resources for CS105