This version of the course guide is provisional until the period for editing the new course guides ends.

Logo UAB

Discrete Mathematics

Code: 102772 ECTS Credits: 6
2025/2026
Degree Type Year
Computer Engineering FB 1

Contact

Name:
Maria Merce Villanueva Gay
Email:
merce.villanueva@uab.cat

Teachers

Joan Bartrina Rapesta
Miguel Hernández Cabronero
Julián Salas Piñón
Maria Merce Villanueva Gay
Bernat Gaston Braso

Teaching groups languages

You can view this information at the end of this document.


Prerequisites

There are no prerequisites. However, students should be familiar with the most basic concepts of fundamental algebra, such as set theory and applications.


Objectives and Contextualisation

The course deals with topics included in the area of Discrete Mathematics focussing on the study of discrete objects. It begins with basic graph theory, path optimisation, algorithms in graphs and complexity of algorithms and problems.


Learning Outcomes

  1. CM01 (Competence) Use knowledge and skills related to discrete mathematics to solve problems with multidisciplinary teams.
  2. KM01 (Knowledge) Explain algorithmic procedures related to graphs, sets and combinatorics.
  3. SM01 (Skill) Apply knowledge of graphs and combinatorics in problem solving in computer engineering.

Content

1.   Previous concepts: sets, functions and complexity of algorithms

  1. Sets and operations with sets
  2. Cartesian product and binary relations
  3. Combinatorial elements
  4. Finite, infinite and numerable sets
  5. Complexity of algorithms and problems
  6. Functions of complexity. Polynomial and non-polynomial complexity

2.   Fundamentals of graphs

  1. Definitions. Variants of graphs
  2. Paths, circuits and distances
  3. Degrees and handshaking lemma
  4. Subgraphs and important types of graphs
  5. Graphic sequences (Havel-Hakimi)
  6. Graph representation

 3.   Optimal tours, paths and generating trees

  1. Exploration of graphs (DFS and BFS)
  2. Minimum cost paths (Dijkstra, Floyd)
  3. Characterization of trees
  4. Optimal generating trees (Kruskal)

 4.   Planarity and colouring

  1. Basic results
  2. Characterization of planar graphs
  3. Colouring of planar graphs
  4. Annex: chromatic polynomial

5.   Eulerian and Hamiltonian graphs

  1. Eulerian paths and circuits
  2. Fleury method (or Hierholzer)
  3. Chinese postman problem
  4. Hamiltonian path and circuits
  5. Travelling salesman problem

6.  Modeling and problem solving

  1. Abstraction and formulation of problems using graphs
  2. Examples of modeling and solving real-world problems

Activities and Methodology

Title Hours ECTS Learning Outcomes
Type: Directed      
Exercise-based classes 15 0.6 KM01, SM01, KM01
Seminars 5 0.2 CM01, CM01
Theoretical classes / lectures 30 1.2 KM01, KM01
Type: Supervised      
Preparing exercises and seminars 12.5 0.5 CM01, KM01, SM01, CM01
Tutoring and consultations 5 0.2 CM01, KM01, SM01, CM01
Type: Autonomous      
Independent study 50 2 CM01, KM01, SM01, CM01
Preparing the final test 25 1 KM01, SM01, KM01

Theoretical content will be taught through lectures, although students will be encouraged to actively participate in the resolution of examples, complexity computation, etc. During problem sessions, a list of exercises will be resolved. Students are encouraged to solve the problems on their own in advance. Students will also be encouraged to present their own solutions in class. In the seminars, related topics will be discussed in depth: several exercises will be carried out on algorithms explained in theory applied to real cases and in a practical format. Campus Virtual will be used for communication between lecturers and students (material, updates, announcements, etc.).

Annotation: Within the schedule set by the centre or degree programme, 15 minutes of one class will be reserved for students to evaluate their lecturers and their courses or modules through questionnaires.


Assessment

Continous Assessment Activities

Title Weighting Hours ECTS Learning Outcomes
Group tests in seminar classes 25% 4 0.16 CM01, KM01, SM01
Tests based on exercise resolutions in exercise-base classes 15% 0.5 0.02 KM01, SM01
Two partial tests 60% 3 0.12 KM01, SM01

This subject does not provide for the sigle assessment system. 

Continuous-assessment dates will be published on Campus Virtual. Specific programming may change when necessary. Any such modification will always be communicated to students through Campus Virtual, which is the usual communication platform between lecturers and students.

Subject assessment (out of 10 points) will be carried out as follows:

  • Two individual partial tests, 6 points (3 points each). The first partial test will be given at the end of the first three chapters of the course; the second partial test will be given on finishing all the chapters of the course. These individual tests will consist mostly of exercises in the style of those worked on during the course; a smaller part will consist of more theoretical questions. A minimum of 1 point (of the 3 points) in each partial test is required to pass the course.  
  • Exercise resolutions, 1.5 points. As part of continuous assessment, activities must be carried out or exercises must be solved by applying the given algorithms (via online quizzes, for example). The non-online activities or exercises will take place during the theory or exercise sessions.
  • Continuous assessment for seminars, 2.5 points. The activities developed in a tutored way in these seminars will be evaluated. Students will be required to present their exercises done in group during the sessions. Passing the seminar assignments will require passing the individual validation tests linked to each assignment. These tests will assess the assimilation of both theoretical and practical concepts associated with each activity. A minimum of 1 point (of the 2.5 points) is required to pass the course
  • Finalexam, 6 points. Those who have not passed the subject through the individual partial tests will have the option to take final exam as a re-assessment grade to compensate the individual partial tests. There is therefore no separate re-assessment for partial tests; this exam covers material from the entire course. It will consist mainly of exercisesin thestyle of those worked on duringthe course; a smaller part will consist of more theoretical questions. A minimum of 2 points (of the 6 points) is required to pass the course

Notwithstanding other disciplinary measures deemed appropriate, and in accordance with the academic regulations in force, assessment activities will receive a zero whenever a student commits academic irregularities that may alter such assessment. Assessment activities graded in this way and by this procedure will not be re-assessable. If passing the assessment activity or activities in question is required to pass the subject, the awarding of a zero for disciplinary measures will also entail a direct fail for the subject, with no opportunity to re-assess this in the same academic year. Irregularities contemplated in this procedure include, among others:

  • the total or partial copying of an evaluation activity;
  • allowing others to copy;
  • presenting group work that has not been done entirely by the members of the group;
  • presenting any materials prepared by a third party as one’s own work, even if these materials are translations or adaptations, including work that is not original or exclusively that of the student;
  • having communication devices (such as mobile phones,smart watches, etc.) accessible during theoretical-practical assessment tests (individual exams).

To pass the course it is necessary that the mark of each one of the parts exceeds the minimum required and that the overall grade is 5.0 or higher. If you do not pass the course because some of the assessment activities do not reach the minimum mark required, the mark in the Transcript of Records will be the lowest value between 4.5 and the overall average grade. A "non-assessable" grade cannot be assigned to students who have participated in any of the individual partial tests or the final exam. No special treatment will be given to students who have completed the course in the previous academic year, except that the seminar grade previously obtained can be assigned to this course gradebook. In order to pass the course with honours, the final grade must be a 9.0 or higher. Because the number of students with this distinction cannot exceed 5% of the number of students enrolled in the course, this distinction will be awarded to whoever has the highest final grade. In case of a tie, partial-test results will be taken into consideration.

In the case of tests based on exercise resolutions, a review may be requested after the date of the activity or the date of closure of the quiz. For all other assessment activities, a place, date and time of review will be indicated allowing students to review the activity. If students do not take part in this review, no further opportunity will be made available.

In this course, the use of Artificial Intelligence (AI) technologies is permitted exclusively for learning support tasks, such as bibliographic or information searches, text correction, or personal study. The use of AI technologies for completing deliverable activities (i.e., assignments, graded exercises, or exams) is not allowed. Any work that includes AI-generated content will be considered a breach of academic integrity and may result in partial or full penalties on theactivity’s grade, or more severe sanctions in serious cases.

To consult the academic regulations approved by the Governing Council of the UAB, please follow this link: http://webs2002.uab.es/afers_academics/info_ac/0041.htm


Bibliography

  • J.M. Basart. Grafs: fonaments i algorismes. Manuals de la UAB, 13. Servei de publicacions de la UAB, 1994.
  • C. Berge. Graphs. North-Holland, 1991.
  • N.L. Biggs. Matemàtica discreta. Vicens-Vives, 1994.
  • N. Christofides. Graph theory, an algorithmic approach. Academic Press, 1975.
  • M.R. Garey, D.S. Johnson. Computers and intractability. A guide to the theory of NP-Completeness. W.H. Freeman, 1979.
  • F.S. Roberts. Applied combinatorics. Prentice-Hall, 1984.
  • J. Gimbert, R. Moreno, J.M. Ribó, M. Valls. Apropament a la teoria de grafs i als seus algorismes. Eines 23, edicions de la UdL, 1998.
  • R. J. Wilson, Introduction to graph theory. 5th edition. Pearson, 2010.

Software

Python3 is used and to follow the seminars you need to bring a computer with a web browser.

https://docs.python.org/3/reference/index.html

https://docs.jupyter.org/en/latest/


Groups and Languages

Please note that this information is provisional until 30 November 2025. You can check it through this link. To consult the language you will need to enter the CODE of the subject.

Name Group Language Semester Turn
(PAUL) Classroom practices 411 Catalan/Spanish second semester morning-mixed
(PAUL) Classroom practices 412 Catalan/Spanish second semester morning-mixed
(PAUL) Classroom practices 431 Catalan/Spanish second semester morning-mixed
(PAUL) Classroom practices 432 Catalan/Spanish second semester morning-mixed
(PAUL) Classroom practices 451 Catalan/Spanish second semester afternoon
(PAUL) Classroom practices 452 Catalan/Spanish second semester afternoon
(PAUL) Classroom practices 471 Catalan/Spanish second semester afternoon
(SEM) Seminars 411 Catalan/Spanish second semester morning-mixed
(SEM) Seminars 412 Catalan/Spanish second semester morning-mixed
(SEM) Seminars 413 Catalan/Spanish second semester morning-mixed
(SEM) Seminars 414 Catalan/Spanish second semester morning-mixed
(SEM) Seminars 431 Catalan/Spanish second semester morning-mixed
(SEM) Seminars 432 Catalan/Spanish second semester morning-mixed
(SEM) Seminars 433 Catalan/Spanish second semester morning-mixed
(SEM) Seminars 434 Catalan/Spanish second semester morning-mixed
(SEM) Seminars 451 Catalan/Spanish second semester afternoon
(SEM) Seminars 452 Catalan/Spanish second semester afternoon
(SEM) Seminars 453 Catalan/Spanish second semester afternoon
(SEM) Seminars 471 Catalan/Spanish second semester afternoon
(SEM) Seminars 472 Catalan/Spanish second semester afternoon
(SEM) Seminars 473 Catalan/Spanish second semester afternoon
(TE) Theory 41 Catalan/Spanish second semester morning-mixed
(TE) Theory 43 Catalan/Spanish second semester morning-mixed
(TE) Theory 45 Catalan/Spanish second semester afternoon
(TE) Theory 47 Catalan/Spanish second semester afternoon