Checking date: 08/08/2020


Course: 2019/2020

Discrete Mathematics
(18260)
Bachelor in Applied Mathematics and Computing (Plan: 433 - Estudio: 362)


Coordinating teacher: MORO CARREÑO, JULIO

Department assigned to the subject: Mathematics Department

Type: Compulsory
ECTS Credits: 6.0 ECTS

Course:
Semester:




Requirements (Subjects that are assumed to be known)
Fudamentals of Algebra; Linear Algebra
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

The course syllabus may change due academic events or other reasons.