Difference between revisions of "MAT5433"
Jose.iovino (talk | contribs) |
Jose.iovino (talk | contribs) |
||
| (3 intermediate revisions by the same user not shown) | |||
| Line 1: | Line 1: | ||
| − | + | == Catalog entry == | |
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
''Prerequisite'': Algebra and Number Systems (MAT 1313), or Discrete Mathematical Structures (CS 2233/2231), or instructor consent. | ''Prerequisite'': Algebra and Number Systems (MAT 1313), or Discrete Mathematical Structures (CS 2233/2231), or instructor consent. | ||
| Line 20: | Line 10: | ||
(5) Network algorithms: Shortest path, minimum spanning trees, matching algorithms, transportation problems. | (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. | (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] | ||
| + | |||
| + | |||
| + | |||
| + | |||
| Line 45: | Line 45: | ||
|| [[Graph models]] | || [[Graph models]] | ||
|| 12.1-12.3 | || 12.1-12.3 | ||
| − | || | + | || Isomorphism, edge counting, planar graphs. |
|- | |- | ||
| 7-8 | | 7-8 | ||
|| [[Covering circuits]] | || [[Covering circuits]] | ||
| + | || 2.1-2.4 | ||
|| Euler circuits, Hamilton circuits, graph colorings, coloring theorems. | || Euler circuits, Hamilton circuits, graph colorings, coloring theorems. | ||
| − | |||
|- | |- | ||
| 9-10 | | 9-10 | ||
| Line 58: | Line 58: | ||
|- | |- | ||
| 11-13 | | 11-13 | ||
| − | || [[Network algorithms | + | || [[Network algorithms]] |
|| 4.1-4.5 | || 4.1-4.5 | ||
|| Shortest path , minimum spanning trees, matching algorithms, transportation problems. | || Shortest path , minimum spanning trees, matching algorithms, transportation problems. | ||
|} | |} | ||
Latest revision as of 22:09, 25 March 2023
Catalog entry
Prerequisite: Algebra and Number Systems (MAT 1313), or Discrete Mathematical Structures (CS 2233/2231), or instructor consent.
Contents (1) Basic counting principles: Permutations, combinations, binomial coefficients, arrangements with repetitions. (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 here
[2] Alan Tucker, Applied Combinatorics, Freely available online here
Topics List
| 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. |
