Discrete Mathematics

Discrete Mathematics (218 - 15971)
Study: Bachelor in Informatics Engineering
Semester 2/Spring Semester
1st Year Course/Lower Division

Students are expected to have completed:

Calculus and Algebra

Compentences and Skills that will be Acquired and Learning Results:

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.

Description of Contents: 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.

Learning Activities and Methodology:

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.

Assessment System:

We follow a continuous-assessment system plus a final exam:

a) The continuous-assessment part consists in a written examination contributing with weight 40% to the final mark. The mid-term examination will take place around the 12th week of the semester, and it will be held in regular class hours, according to the current regulations.

b) The final exam (contributing with weight 60% to the final mark) will be held at the end of the semester.
(PO: a)

In both the mid-term and final exams, competence CBG3 will be evaluated.

Both mid-term and final exams will mostly consist of practical questions, although more abstract questions and/or proofs of simple theoretical results might also be included.

There is an extraordinary exam in June for those students who did not obtain the required end-of-semester mark. This resit exam has a maximum mark of 10, and the June final mark is given by max (EE, 0.6 EE + 0.4 EC), where EE (resp. CA) is the extraordinary-exam (resp. continuous-assessment) mark.

Basic Bibliography:

F. García Merayo. Matemática Discreta. Paraninfo. 2015
J. Matousek and J. Nesetril. Invitation to Discrete Mathematics. Oxford. 2004
K.H. Rosen. Discrete Mathematics and Its Applications. McGraw-Hill. 1999

Additional Bibliography:

N.L. Biggs. Discrete Mathematics. Oxford University Press. 2002
R.P. Grimaldi. Discrete and Combinatorial Mathematics: An Applied Introduction. Addison Wesley. 2003