Difference between revisions of "MAT5433"
Jose.iovino (talk | contribs) (Created page with "Introduction to basic discrete structures. '''Sample textbooks''': [1] Vladlen Koltun, ''Discrete Structures, Lecture Notes, Stanford University'', 2008. Freely available...") |
Jose.iovino (talk | contribs) |
||
| Line 5: | Line 5: | ||
[1] Vladlen Koltun, ''Discrete Structures, Lecture Notes, Stanford University'', 2008. Freely available online [https://web.stanford.edu/class/cs103x/cs103x-notes.pdf here] | [1] Vladlen Koltun, ''Discrete Structures, Lecture Notes, Stanford University'', 2008. Freely available online [https://web.stanford.edu/class/cs103x/cs103x-notes.pdf here] | ||
| − | [2] | + | [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] |
| + | |||
'''Catalog entry''' | '''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. |
| − | |||
| − | |||
| − | |||
| − | |||
| − | Contents | + | ''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. | (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. | ||
| Line 26: | Line 23: | ||
==Topics List== | ==Topics List== | ||
{| class="wikitable sortable" | {| class="wikitable sortable" | ||
| − | ! Week !! Topic !! Sections from | + | ! Week !! Topic !! Sections from Tucker's book !! Subtopics !! Prerequisite |
|- | |- | ||
| 1-2 | | 1-2 | ||
| − | || [[ | + | || [[Basic counting principles]] |
|| 10.1-10-2 | || 10.1-10-2 | ||
| + | || Permutations, combinations, arrangements with repetitions | ||
|| MAT1313, CS2233/2231, or instructor consent. | || MAT1313, CS2233/2231, or instructor consent. | ||
|- | |- | ||
| 3 | | 3 | ||
|| [[Inclusion-Exclusion Principle]] | || [[Inclusion-Exclusion Principle]] | ||
| − | || 2.5-2.7 | + | || 2.5-2.7 |
| + | |||
|| | || | ||
|- | |- | ||
| Line 54: | Line 53: | ||
|- | |- | ||
| 9-10 | | 9-10 | ||
| − | || [[Discrete structures]] | + | || [[Discrete structures (graphs, partially ordered sets) ]] |
|| 7.1-8.4 | || 7.1-8.4 | ||
|| | || | ||
Revision as of 15:47, 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) 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 Tucker's book | Subtopics | Prerequisite |
|---|---|---|---|---|
| 1-2 | Basic counting principles | 10.1-10-2 | Permutations, combinations, arrangements with repetitions | 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 (graphs, partially ordered sets) | 7.1-8.4 | ||
| 10-16 | Models of computation | 10.1-10.4 |
