Universidad Carlos III de Madrid
Area of Study
Computer Engineering, Computer Science, Mathematics
Taught In English
STUDENTS ARE EXPECTED TO HAVE COMPLETED:
Calculus and Algebra
Course Level Recommendations
ISA offers course level recommendations in an effort to facilitate the determination of course levels by credential evaluators.We advice each institution to have their own credentials evaluator make the final decision regrading course levels.
Recommended U.S. Semester Credits3
Recommended U.S. Quarter Units4
Hours & Credits
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.
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.
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.
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.
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
N.L. Biggs. Discrete Mathematics. Oxford University Press. 2002
R.P. Grimaldi. Discrete and Combinatorial Mathematics: An Applied Introduction. Addison Wesley. 2003
Courses and course hours of instruction are subject to change.
ECTS (European Credit Transfer and Accumulation System) credits are converted to semester credits/quarter units differently among U.S. universities. Students should confirm the conversion scale used at their home university when determining credit transfer.