MAT5433
Introduction to basic discrete structures.
Sample textbooks:
[1] Vladlen Koltun, Discrete Structures, Lecture Notes, Stanford University, 2008. Freely available online here
[2]
Catalog entry
Prerequisite: Algebra and Number Systems (MAT 1313), or Discrete Mathematical Structures (CS 2233/2231), or instructor consent.
Catalog entry:
Prerequisite: Algebra and Number Systems (MAT 1313), or Discrete Mathematical Structures (CS 2233/2231), or instructor consent.
Contents (1) Relations: Cartesian products, relations, properties of relations, equivalence relations and partitions. (2) Order relations: Partially ordered sets, totally ordered sets, extreme elements (maximum, minimum, maximal and minimal elements), well-ordered sets, maximality principles, Zorn's Lemma, lattices, boolean algebras, circuit design. (3) Graphs: Euler and Hamiltonian paths and circuits, matching, graph coloring, Ramsey’s theorem, trees and searching. (4) Binary operations: Groups and semigroups, products and quotients of groups, other algebraic structures.
Topics List
| Week | Topic | Sections from Koltuns's book | Prerequisite |
|---|---|---|---|
| 1-2 | Counting | 10.1-10-2 | MAT1313, CS2233/2231, or instructor consent. |
| 3 | Inclusion-Exclusion Principle | 2.5-2.7. | |
| 4 | The Pigeonhole Principle | 12.1-12.3 | |
| Graphs | Asymptotics | 13.1-13.2 | |
| 8 | Relations | 5.1-6.3 | |
| 9-10 | Discrete structures | 7.1-8.4 | |
| 10-16 | Models of computation | 10.1-10.4 |
