Universidad Carlos III de Madrid
Iowa State Course Substitution
Discrete Mathematics and Applications
- International Credits:
- Converted Credits:
- 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. Graph-theoretic algorithms. Minimum-weight spanning tree (Prim's and Kruskal's algorithms). Shortest-distance 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. Well-ordered sets: mathematical induction. Lexicographic order. Topological order. 7. Lattices. Bounded, modular, and distributive lattices. Complementary lattices. Boolean algebras.
- Evaluation Date:
- November 21, 2016
- James Wilson
- This course has different emphasis, goes further with application, whereas our course emphasizes teaching.