MAT5433 - Revision history

Jose.iovino at 01:30, 25 March 2026

2026-03-25T01:30:36Z

Jose.iovino at 23:11, 24 March 2026

2026-03-24T23:11:28Z

Jose.iovino at 04:09, 26 March 2023

2023-03-26T04:09:03Z

Jose.iovino: /* Topics List */

2023-03-19T00:11:55Z

Topics List

Jose.iovino: /* Topics List */

2023-03-19T00:10:16Z

Topics List

Jose.iovino: /* Topics List */

2023-03-19T00:09:58Z

Topics List

Jose.iovino at 22:40, 18 March 2023

2023-03-18T22:40:08Z

Jose.iovino at 21:47, 18 March 2023

2023-03-18T21:47:32Z

Jose.iovino: Created page with "Introduction to basic discrete structures. '''Sample textbooks''': [1] Vladlen Koltun, ''Discrete Structures, Lecture Notes, Stanford University'', 2008. Freely available..."

2023-03-18T21:23:52Z

Created page with "Introduction to basic discrete structures. '''Sample textbooks''': [1] Vladlen Koltun, ''Discrete Structures, Lecture Notes, Stanford University'', 2008. Freely available..."

New page

Introduction to basic discrete structures.

'''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]

'''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==
{| class="wikitable sortable"
! 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
||
|}

@@ Line 1: / Line 1: @@
 == Catalog entry ==
-''Prerequisite'':Discrete Mathematics (MAT 3003) or Real Analysis I (MAT 4213), or instructor consent.
+''Prerequisite'':
 ''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.

@@ Line 1: / Line 1: @@
 == 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''
-(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.

@@ Line 1: / Line 1: @@
-Introduction to basic discrete structures.
+== Catalog entry ==
 ''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.
 (6) Order relations: Partially ordered sets, totally ordered sets, extreme elements (maximum, minimum, maximal and minimal elements), well-ordered sets, maximality principles.

@@ Line 45: / Line 45: @@
 || [[Graph models]]
 || 12.1-12.3
-||
+|| Isomorphism, edge counting, planar graphs.
 |-
 |  7-8

@@ Line 58: / Line 58: @@
 |-
 |  11-13
-|| [[Network algorithms) ]]
+|| [[Network algorithms]]
 || 4.1-4.5
 || Shortest path , minimum spanning trees, matching algorithms, transportation problems.
 |}

@@ Line 49: / Line 49: @@
 |  7-8
 || [[Covering circuits]]
 || Euler circuits, Hamilton circuits, graph colorings, coloring theorems.
 |-
 |  9-10

@@ Line 14: / Line 14: @@
 ''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) Basic counting principles: Permutations, combinations, binomial coefficients, arrangements with repetitions.
@@ Line 27: / Line 33: @@
 |  1-2
 || [[Basic counting principles]]
-|| 10.1-10-2
+|| 5.1-5.5
-|| Permutations, combinations, arrangements with repetitions
+|| Permutations, combinations, binomial coefficients, arrangements with repetitions
 || MAT1313, CS2233/2231, or instructor consent.
 |-
 |  3
 || [[Inclusion-Exclusion Principle]]
-|| 2.5-2.7
+|| 8.1-8.2
+|| Counting with Venn diagrams.
 |-
-|  4
+|  4-6
-|| [[The Pigeonhole Principle]]
+|| [[Graph models]]
 || 12.1-12.3
 ||
 |-
-|  Graphs
+|  7-8
-|| [[Asymptotics]]
+|| [[Covering circuits]]
-|| 13.1-13.2
+|| Euler circuits, Hamilton circuits, graph colorings, coloring theorems.
 ||
 |-
 |  9-10
-|| [[Discrete structures (graphs, partially ordered sets) ]]
+|| [[Trees]]
-|| 7.1-8.4
+|| 3.1-3.4
-||
+|| Search trees, spanning trees, the Traveling Salesman Problem
 |-
-|  10-16
+|  11-13
-|| [[Models of computation]]
+|| [[Network algorithms) ]]
-|| 10.1-10.4
+|| 4.1-4.5
-||
+|| Shortest path , minimum spanning trees, matching algorithms, transportation problems.
 |}

@@ 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]
-[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'''
-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.
@@ Line 26: / Line 23: @@
 ==Topics List==
 {| class="wikitable sortable"
-! Week !! Topic !! Sections from Koltuns's book !! Prerequisite
+! Week !! Topic !! Sections from Tucker's book !! Subtopics !! Prerequisite
 |-
 |  1-2
-|| [[Counting]]
+|| [[Basic counting principles]]
 || 10.1-10-2
 || MAT1313, CS2233/2231, or instructor consent.
 |-
 |  3
 || [[Inclusion-Exclusion Principle]]
-|| 2.5-2.7.
+|| 2.5-2.7
 ||
 |-
@@ Line 54: / Line 53: @@
 |-
 |  9-10
-|| [[Discrete structures]]
+|| [[Discrete structures (graphs, partially ordered sets) ]]
 || 7.1-8.4
 ||