Course: 2020/2021

Discrete Mathematics

(18260)

Students are expected to have completed

Fudamentals of Algebra; Linear Algebra

ObjectivesFurther information on this link

GENERAL COMPETENCES
CG2.Students are able to formulate in mathematical language problems that arise in science, engineering, economy and other social sciences.
SPECIFIC COMPETENCES
CE1.Students have shown that they know and understand the mathematical language and abstract-rigorous reasoning as well as to apply them to state and prove precise results in several areas in mathematics.
CE3.Students have shown that they understand the fundamental results from discrete mathematics.
LEARNING OUTCOMES
Upon completion of the course, students should be able to
- Reformulate into mathematical language specific real-world problems, and solve them using permutations, combinations and the basic rules for counting;
- Identify recursively defined sets and functions, and check whether they are defined correctly;
- Solve linear recurrence equations of low order;
- Understand the `big-Oh' asymptotic notation, and be able to use it to analyse asymptotic performance for some basic algorithmic examples;
- Estimate the time complexity of divide-and-conquer computational algorithms;
- Identify binary relations, and assess their properties by representing them in mathematical terms via graphs or matrices;
- Given a binary relation, recognize if it is an equivalence relation, an order relation, or neither;
- Given a simple partial ordering, identify its extremal elements by constructing its Hasse diagram;
- Propose simplified mathematical models for real-world situations in terms of graphs;
- Given two simple directed or undirected graphs, decide whether they are isomorphic;
- Determine the existence of Euler or Hamilton paths on simple undirected graphs;
- Find shortest paths using Dijkstra's algorithm, or minimal spanning trees using Kruskal's.

Description of contents: programme

1. Basic counting techniques: combinatorics
a) Basic counting rules;
b) Permutations and combinations; binomial coefficients and identities;
c) Permutations and combinations with repetition.
2. Recursion
a) Recursively defined sets and functions; dependence tree;
b) Linear difference equations;
c) Time complexity of `divide-and-conquer' algorithms;
3. Binary relations
a) Relations and their basic properties;
b) Order relations;
c) Equivalence relations;
4. Graph theory and applications
a) Graphs: basic definitions and concepts; undirected graphs;
b) Euler and Hamilton paths;
c) Directed graphs;
d) Weighted graphs;
e) Trees.

Learning activities and methodology

AF1.THEORETICAL-PRACTICAL CLASSES. Knowledge and concepts students must acquire. Student will have basic reference texts to facilitate following the classes and carrying out follow-up work. Students partake in exercises to resolve practical problems and participate in two partial tests, all geared towards acquiring the necessary capabilities. Subjects with 6 ECTS require typically 44 hours / 100% classroom instruction
AF2.TUTORING SESSIONS. Individualized attendance (individual tutoring) or in-group (group tutoring) for students with a teacher. Subjects with 6 credits have 4 hours of tutoring/ 100% on- site attendance.
AF3.STUDENT INDIVIDUAL WORK OR GROUP WORK. Subjects with 6 credits have 98 hours/0% on-site.
MD1.THEORY CLASS. Classroom presentations by the teacher with IT and audiovisual support in which the subject`s main concepts are developed, while providing material and bibliography to complement student learning.
MD2.PRACTICAL CLASS. Resolution of practical cases and problem, posed by the teacher, and carried out individually or in a group.
MD3.TUTORING SESSIONS. Individualized attendance (individual tutoring sessions) or in-group (group tutoring sessions) for students with teacher as tutor. Subjects with 6 credits have 4 hours of tutoring/100% on-site.

Assessment System

- % end-of-term-examination 60
- % of continuous assessment (assigments, laboratory, practicals...) 40

Basic Bibliography

- B. Bollobás. Graph Teory: An Introductory Course. Springer . 1990
- K.H. Rosen. Discrete Mathematics and its Applications (8th edition). McGraw Hill. 2019
- R.P. Grimaldi. Discrete and combinatorial mathematics : an applied introduction (5th edition). Pearson. 2017

Additional Bibliography

- B. Bollobás. Modern Graph Theory. Springer. 1998
- P. Cull, M. Flahive & R. Robson. Difference equations: from rabbits to chaos. Springer . 2005
- R. Diestel. Graph Theory. Springer. 2017