CS106. Discrete Structures II

Prerequisites: CS105

Syllabus:

• Review of previous course
• Predicate logic: Universal and existential quantification; modus ponens and modus tollens; limitations of predicate logic
• Recurrence relations: Basic formulae; elementary solution techniques
• Graphs and trees: Fundamental definitions; simple algorithms ; traversal strategies; proof techniques; spanning trees; applications
• Matrices: Basic properties; applications
• Computational complexity: Order analysis; standard complexity classes
• Elementary computability: Countability and uncountability; diagonalization proof to show uncountability of the reals; definition of the P and NP classes; simple demonstration of the halting problem
• Discrete probability: Finite probability spaces; conditional probability, independence, Bayes' rule; random events; random integer variables; mathematical expectation

Units covered:

DS2	Basic logic	7	core hours (of 10)
DS3	Proof techniques	8	core hours (of 12)
DS5	Graphs and trees	4	core hours
DS6	Discrete probability	6	core hours
AL1	Basic algorithmic analysis	2	core hours (of 4)
AL5	Basic computability	3	core hours (of 6)
AL6	The complexity classes P and NP	2	hours
	Matrices	3	hours
	Elective topics	5	hours

Notes:
This implementation of the Discrete Structures area (DS) divides the material into two courses: CS105 and CS106. For programs that wish to accelerate the presentation of this material, there is also CS115, which covers the core topics in a single course. The two-course sequence, however, covers some additional material that is not in the compressed version, primarily in the Algorithms and Complexity area (AL). As a result, the introductory course in algorithmic analysis (CS210) can devote more time to advanced topics if an institution adopts the two-course implementation.

Like CS105, this course introduces mathematical topics in the context of applications that require those concepts as tools. For this course, likely applications include transportation network problems (such as the traveling salesperson problem) and resource allocation.

Online resources for CS106