Calculus and Algebra

GENERIC COMPETENCES (PO: a) CGB3: Ability to understand and master the basic concepts of Discrete Mathematics, and its application to solving problems of engineering. SPECIFIC COMPETENCES. The goal of this course is to provide the students the necessary mathematical tools to understand the scientific and mathematical principles of computer science. The PROGRAMME OUTCOMES acquired in Discrete Mathematics are of type RA1 (knowledge and understanding). In particular, they correspond to those of RA1.1 type: "Knowledge and understanding of the scientific and mathematical principles underlying computer science". We have split the specific competences of this course in three classes: A) Learning objectives (RA1.1, PO: a) 1. To learn the basic concepts related to set theory, binary relations, and lattices, as well as their relevance in computer-science applications. 2. To know elementary counting techniques, understand the concept of recurrence, and know how to solve linear recurrence equations. 3. To understand the concept of generating function, its relevance in combinatorics, and know how to use it to solve recurrence problems. 4. To understand the language of graph theory, and learn how to model real-world problems in graph-theoretic terms. 5. To learn how to solve typical graph-theoretic problems using algorithmic methods. B) Specific skills (RA1.1, PO: a) 1. To be able to handle the abstract properties of set theory and binary relations. 2. To be able to solve ordering and enumeration problems. 3. To be able to model real-world problems using graph-theoretic techniques, and solve them using algorithmic procedures. C) General skills (RA1.1, PO: a) 1. To be able to think abstractly, and to use induction and deduction. 2. To be able to communicate in oral and written forms using appropriately mathematical language. 3. To be able to model a real situation using discrete-mathematics techniques. 4. To be able to interpret a mathematical solution of a given problem, its accuracy, and its limitations.

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.

Lecture sessions: 2.5 ECTS credits (CBG3, RA1.1, PO: a). Problem sessions: 2.5 ECTS credits (CBG3, RA1.1, PO: a). Self-study using the course web page (interactive quizzes, multimedia material, etc): 1 ECTS credit (CBG3, RA1.1, PO: a). Office hours: each teacher offers a number of office hours according to the regulations of the Carlos III University. In particular, a minimum of one hour per group with time schedule compatible with the students.