Universidad Carlos III de Madrid
Discrete Mathematics
21815971
Iowa State Course Substitution
Discrete Mathematics and Applications
MATH 547
Course Info
International Credits:
6.0
Converted Credits:
3.5
Semester:
spring
Country:
Spain
Language:
English
Course Description:
The programme has three main blocks: combinatorics, graph theory, and set theory. In particular, the course programme contains the following topics:
1. Elementary set theory. Definitions. Set operations and their algebraic properties. Set cardinality. Elementary counting techniques. Subsets and power set. Binomial coefficients. Set partitions. Refinement of a partition. Relations and functions. Binary relations. Functions. Characteristic function.
2. Graph theory. Generalities. Graph representation. Graph isomorphism. Walks and paths on graphs. Graph connectivity. Weighted graphs. Directed graphs. Trees. Planar graphs. Euler's formula and its consequences. Kuratowski theorem.
3. Graphtheoretic algorithms. Minimumweight spanning tree (Prim's and Kruskal's algorithms). Shortestdistance path between two vertices (Dijkstra's algorithm and generalizations). Eulerian and Hamiltonian graphs. Algorithms for obtaining an Eulerian tour. The traveling salesman problem. Approximate algorithms. Search algorithms in trees.
4. Advanced techniques in combinatorics. Recurrence relations. Generating functions. Integer sequences of interest in combinatorics. Combinatorial problems in graph theory: proper colorings, matchings, etc.
5. Equivalence relations. Equivalence relations and partitions. Equivalence classes and quotient set. Application to modular arithmetic.
6. Order relations. Partially ordered sets. Hasse diagrams. Extremal elements. Totally ordered sets. Wellordered sets: mathematical induction. Lexicographic order. Topological order.
7. Lattices. Bounded, modular, and distributive lattices. Complementary lattices. Boolean algebras.
Review
 Evaluation Date:
 November 21, 2016
 Evaluated:
 James Wilson
 Comments:

This course has different emphasis, goes further with application, whereas our course emphasizes teaching.