|
|
| Line 1: |
Line 1: |
| | == Catalog entry == | | == Catalog entry == |
| | | | |
| − | ''Prerequisite'': Algebra and Number Systems (MAT 1313), or Discrete Mathematical Structures (CS 2233/2231), or instructor consent. | + | ''Prerequisite'':Discrete Mathematics (MAT 3003) or Real Analysis I (MAT 4213), or instructor consent. |
| | | | |
| | ''Contents'' | | ''Contents'' |
| − | (1) Basic counting principles: Permutations, combinations, binomial coefficients, arrangements with repetitions.
| + | The Zermelo-Fraenkel axioms, ordinals and cardinals, the Axiom of Foundation, the Reflection Principle, ordinal-definable sets, relative consistency of the Axiom of Choice, Fraenkel-Mostowski models, relative consistency of the negation of the Axiom of Choice, consistency of the Generalized Continuum Hypothesis. |
| − | (2) The Inclusion-Exclusion principle.
| |
| − | (3) Graph models: Isomorphisms, edge counting, planar graphs.
| |
| − | (4) Covering circuits and graph colorings: Euler circuits, Hamilton circuits, graph colorings, Ramsey's theorem
| |
| − | (5) Network algorithms: Shortest path, minimum spanning trees, matching algorithms, transportation problems.
| |
| − | (6) Order relations: Partially ordered sets, totally ordered sets, extreme elements (maximum, minimum, maximal and minimal elements), well-ordered sets, maximality principles.
| |
| − | | |
| − | == Sample textbooks ==
| |
| − | | |
| − | [1] Vladlen Koltun, ''Discrete Structures, Lecture Notes, Stanford University'', 2008. Freely available online [https://web.stanford.edu/class/cs103x/cs103x-notes.pdf here]
| |
| − | | |
| − | [2] Alan Tucker, ''Applied Combinatorics'', Freely available online [https://www.isinj.com/mt-usamo/Applied%20Combinatorics%20(6th%20Edition)%20by%20Alan%20Tucker%20Wiley%20(2012).pdf here]
| |
| − | | |
| − | | |
| − | | |
| − | | |
| − | | |
| − | | |
| − | | |
| − | | |
| − | | |
| − | | |
| − | | |
| − | ==Topics List==
| |
| − | {| class="wikitable sortable"
| |
| − | ! Week !! Topic !! Sections from Tucker's book !! Subtopics !! Prerequisite
| |
| − | |-
| |
| − | | 1-2
| |
| − | || [[Basic counting principles]]
| |
| − | || 5.1-5.5
| |
| − | || Permutations, combinations, binomial coefficients, arrangements with repetitions
| |
| − | || MAT1313, CS2233/2231, or instructor consent.
| |
| − | |-
| |
| − | | 3
| |
| − | || [[Inclusion-Exclusion Principle]]
| |
| − | || 8.1-8.2
| |
| − | || Counting with Venn diagrams.
| |
| − | |-
| |
| − | | 4-6
| |
| − | || [[Graph models]]
| |
| − | || 12.1-12.3
| |
| − | || Isomorphism, edge counting, planar graphs.
| |
| − | |-
| |
| − | | 7-8
| |
| − | || [[Covering circuits]]
| |
| − | || 2.1-2.4
| |
| − | || Euler circuits, Hamilton circuits, graph colorings, coloring theorems.
| |
| − | |-
| |
| − | | 9-10
| |
| − | || [[Trees]]
| |
| − | || 3.1-3.4
| |
| − | || Search trees, spanning trees, the Traveling Salesman Problem
| |
| − | |-
| |
| − | | 11-13
| |
| − | || [[Network algorithms]]
| |
| − | || 4.1-4.5
| |
| − | || Shortest path , minimum spanning trees, matching algorithms, transportation problems.
| |
| − | |}
| |
Catalog entry
Prerequisite:Discrete Mathematics (MAT 3003) or Real Analysis I (MAT 4213), or instructor consent.
Contents
The Zermelo-Fraenkel axioms, ordinals and cardinals, the Axiom of Foundation, the Reflection Principle, ordinal-definable sets, relative consistency of the Axiom of Choice, Fraenkel-Mostowski models, relative consistency of the negation of the Axiom of Choice, consistency of the Generalized Continuum Hypothesis.
