A continuation of CSE 113 covering the mathematical foundations of computer science. Topics include counting techniques, graph theory, and finite automata.
Prerequisite
CSE 113 or CSE 215 or CSE 150; CSE major
Course Outcomes
Textbook
Discrete Mathematics with Applications, by Susanna S. Epp, 2020 (9781337694193)
Introduction to the Theory of Computation 3rd Edition, Michael Sipser (supplemental)
Major Topics Covered in Course
Section numbers come from Discrete Mathematics with Applications by Susanna Epp.
Introduction to Probability; Possibility Trees and the Multiplication Rule, Secs. 9.1-9.2
Counting Elements of Disjoint Sets: The Addition Rule; The Pigeonhole Principle, Secs. 9.3-9.4
Counting Subsets of a Set: Combinations; r-Combinations with Repetition Allowed, Secs. 9.5-9.6
Pascal’s Formula and the Binomial Theorem, Sec. 9.7
Probability Axioms and Expected Value, Sec. 9.8
Conditional Probability, Bayes’ Formula, and Independent Events, Sec. 9.9
Trails, Paths, and Circuits, Sec. 10.1
Matrix Representations of Graphs, Sec. 10.2
Isomorphisms of Graphs, Sec. 10.3
Trees: Examples and Basic Properties; Rooted Trees, Secs. 10.4-10.5
Spanning Trees and a Shortest Path Algorithm, Sec. 10.6
Formal Languages and Regular Expressions, Sec. 12.1