Difference between revisions of "MAT5433"

From Department of Mathematics at UTSA
Jump to navigation Jump to search
(Created page with "Introduction to basic discrete structures. '''Sample textbooks''': [1] Vladlen Koltun, ''Discrete Structures, Lecture Notes, Stanford University'', 2008. Freely available...")
 
 
(5 intermediate revisions by the same user not shown)
Line 1: Line 1:
−
Introduction to basic discrete structures.
+
== Catalog entry ==
  
−
'''Sample textbooks''':  
+
''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 [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'''
 
  
−
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.
 
  
  
Line 26: Line 29:
 
==Topics List==
 
==Topics List==
 
{| class="wikitable sortable"
 
{| class="wikitable sortable"
−
! Week !! Topic !! Sections from Koltuns's book !! Prerequisite
+
! Week !! Topic !! Sections from Tucker's book !! Subtopics !! Prerequisite
 
|-
 
|-
 
|  1-2   
 
|  1-2   
−
|| [[Counting]]
+
|| [[Basic counting principles]]
−
|| 10.1-10-2
+
|| 5.1-5.5
 +
|| 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]]
−
|| 2.5-2.7.
+
|| 8.1-8.2
−
||  
+
|| Counting with Venn diagrams.
 
|-
 
|-
−
|  4   
+
|  4-6    
−
|| [[The Pigeonhole Principle]]
+
|| [[Graph models]]
 
|| 12.1-12.3
 
|| 12.1-12.3
−
||  
+
|| Isomorphism, edge counting, planar graphs.
−
|-
 
−
|  Graphs 
 
−
|| [[Asymptotics]]
 
−
|| 13.1-13.2
 
−
||
 
 
|-
 
|-
−
|  8   
+
|  7-8   
−
|| [[Relations]]  
+
|| [[Covering circuits]]
−
|| 5.1-6.3
+
|| 2.1-2.4
−
||  
+
|| Euler circuits, Hamilton circuits, graph colorings, coloring theorems.
 
|-
 
|-
 
|  9-10   
 
|  9-10   
−
|| [[Discrete structures]]  
+
|| [[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.
 
|}
 
|}

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.
Retrieved from "https://mathresearch.utsa.edu/wiki/index.php?title=MAT5433&oldid=5073"