Difference between revisions of "MAT5433"
Jose.iovino (talk | contribs) |
Jose.iovino (talk | contribs) |
||
| Line 14: | Line 14: | ||
''Contents'' | ''Contents'' | ||
| − | (1) | + | (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. | ||
| + | |||
| Line 27: | Line 33: | ||
| 1-2 | | 1-2 | ||
|| [[Basic counting principles]] | || [[Basic counting principles]] | ||
| − | || | + | || 5.1-5.5 |
| − | || Permutations, combinations, arrangements with repetitions | + | || Permutations, combinations, binomial coefficients, arrangements with repetitions |
|| MAT1313, CS2233/2231, or instructor consent. | || MAT1313, CS2233/2231, or instructor consent. | ||
|- | |- | ||
| 3 | | 3 | ||
|| [[Inclusion-Exclusion Principle]] | || [[Inclusion-Exclusion Principle]] | ||
| − | || | + | || 8.1-8.2 |
| − | + | || Counting with Venn diagrams. | |
| − | || | ||
|- | |- | ||
| − | | 4 | + | | 4-6 |
| − | || [[ | + | || [[Graph models]] |
|| 12.1-12.3 | || 12.1-12.3 | ||
|| | || | ||
|- | |- | ||
| − | | | + | | 7-8 |
| − | + | || [[Covering circuits]] | |
| − | + | || Euler circuits, Hamilton circuits, graph colorings, coloring theorems. | |
| − | |||
| − | |||
| − | |||
| − | || [[ | ||
| − | || | ||
|| | || | ||
|- | |- | ||
| 9-10 | | 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. |
|} | |} | ||
Revision as of 16:40, 18 March 2023
Introduction to basic discrete structures.
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
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.
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 | ||
| 7-8 | Covering circuits | 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. |
