
Discrete and Algorithmic Mathematics
Code: 107928Credits: 6
| Degree programme | Type | Course |
|---|---|---|
| Mathematics | OB | 2 |
Contact lecturer
- Name :
- Joaquim Roé Vellvé
- Email :
- joaquim.roe@uab.cat
Teaching staff
- Laura Brustenga Moncusi
- Guillem Quingles Daví
Group languages
You can consult this information at the end of the document.
Prerequisites
Àlgebra Lineal I and II and Fonaments de les Matemàtiques I and II.
Objectives
Discrete Mathematics is the branch of mathematics concerned with the study of finite structures. Its main topics include combinatorics, graph theory, cryptography and coding theory, combinatorial designs, optimization, and the design and analysis of algorithms for solving problems in these areas. Most of these topics developed relatively recently, largely in response to problems arising in computer science and optimization. The topics are largely independent of one another, and their study in an introductory course requires only linear algebra, modular arithmetic, elementary combinatorics, and, above all, familiarity with mathematical language and reasoning.
The course begins with generating functions and recurrence relations. This topic provides a natural continuation of material introduced in the first-year course Foundations of Mathematics, while further developing students' ability to translate problem statements into mathematical and algorithmic language. The course then introduces graph theory, one of the fundamental tools for modelling and solving problems across a wide range of disciplines, from pure mathematics to operations research. In many cases, simply expressing a problem in the language of graphs provides valuable insight and leads to effective solution strategies. This course, however, offers only a brief introduction to the subject.
The third part of the course focuses on combinatorial optimization, which deals with combinatorial problems in which the objective is not to count objects of a given type but to identify those that are optimal according to a specified criterion. In this context, the solutions are not closed-form formulas but algorithms for finding or approximating optimal solutions. The mathematical tools required include linear algebra and matroid theory.
Throughout the course, students will encounter a variety of applications of mathematics in which relatively elementary techniques, combined with mathematical ingenuity, are used to solve interesting and challenging problems. Through exercises in combinatorics and optimization, students will also develop one of the fundamental skills of mathematical modelling: understanding a problem and translating it into an appropriate mathematical framework for its solution.
Learning outcomes
- CM14 (Reformulate real-world problems such as those of mathematical programming.) Reformulate real-world problems such as those of mathematical programming.
- CM15 (Pose ordering and enumeration problems using efficient solving techniques.) Pose ordering and enumeration problems using efficient solving techniques.
- KM22 (Identify the basic results of combinatorial theory.) Identify the basic results of combinatorial theory.
- KM23 (Identify elementary problem-solving algorithms in graphs.) Identify elementary problem-solving algorithms in graphs.
- KM24 (Identify the elementary algorithms of linear programming.) Identify the elementary algorithms of linear programming.
- SM18 (Use the main methods for solving linear programming problems (simplex method, two-phase method, interior point method).) Use the main methods for solving linear programming problems (simplex method, two-phase method, interior point method).
- SM19 (Use computational techniques to solve optimization problems (simplex method, gradient method, etc.).) Use computational techniques to solve optimization problems (simplex method, gradient method, etc.).
Contents
- Generating Functions and Recurrence Sequences
- Definition of generating functions. Techniques for computing generating functions. Solving combinatorial problems using generating functions.
- Recurrence sequences. Solving recurrence relations using generating functions.
- Algorithms and Complexity
- Graphs
- Definition. Some models based on graphs.
- Basic terminology. Graph invariants and graph isomorphisms.
- Paths, circuits, and trees.
- Combinatorial Optimization
- Search and sorting algorithms.
- Matroids.
- Optimization problems on graphs.
Learning activities and methodology
| Title | Hours | ECTS | Learning outcomes |
|---|---|---|---|
| Lectures | 26 | 1.04 | CM14, CM15, KM22, KM23, KM24, SM18 |
| Problem solving (seminar preparation) | 26.25 | 1.05 | CM14, CM15, KM22, KM23, KM24, SM18, SM19 |
| Personal study | 31.25 | 1.25 | CM14, CM15, KM22, KM23, KM24 |
| Seminars | 16 | 0.64 | CM14, CM15, KM22, KM23, KM24, SM18, SM19 |
| Practical sessions | 8 | 0.32 | CM15, KM23, KM24, SM18, SM19 |
| Presentation preparation | 31.25 | 1.25 | CM14, CM15, KM22, KM23, KM24, SM18 |
Face-to-face teaching will consist of the following components:
- Lectures. The instructor will present the theoretical foundations of the course, including selected proofs. Some of the subjects or applications of the theory will be explained by the students: during one of the lecture sessions, a list of topics will be proposed. Each group will select one topic and work on it independently. The outcome of this work will be submitted as a written report and presented orally to the rest of the class.
- Problem-solving sessions (seminars). Students will be provided with problem sets, which they are expected to prepare before class in order to participate effectively in the discussions held during the sessions.
- Computer laboratory sessions using SageMath. The first three sessions will correspond to the three main topics of the course. The fourth session will include exercises covering all three topics and will be assessed.
Note: Fifteen minutes of one class session, within the timetable established by the School/Degree Programme, will be reserved for students to complete the institutional surveys evaluating the teaching performance of the instructor and the course.
Assessment
Continuous assessment activities
| Title | Weight | Hours | ECTS | Learning outcomes |
|---|---|---|---|---|
| Assessed practical session | 0.2 | 2 | 0.08 | CM14, KM23, KM24, SM18, SM19 |
| Oral presentation | 0.2 | 0.25 | 0.01 | CM14, CM15, KM22, KM23, KM24 |
| Midterm exam | 0.25 | 3 | 0.12 | CM14, CM15, KM22 |
| Final exam | 0.35 | 3 | 0.12 | CM14, CM15, KM22, KM23, KM24, SM18 |
| Resit assessment | 0.6 | 3 | 0.12 | CM14, CM15, KM22, KM23, KM24 |
There are four assessed activities: a midterm exam, an oral presentation, an assessed practical session, and a final exam. The final grade for the course will be computed according to the following formula: 0.25 × midterm exam grade + 0.20 × oral presentation grade + 0.20 × assessed practical session grade + 0.35 × final exam grade.
Resit assessment: students may resit the two examinations (60% of the final grade). To be eligible for the resit assessment, students must have participated in at least three of the four assessed activities during the course.
The grade "Not assessed" ("No avaluable") will be awarded to students who have participated in two or fewer assessed activities, provided that none of them is the final exam.
After the final exam, the distinctions with honours ("Matrícula d'Honor") that are deemed clearly justified will be awarded. These distinctions will be final. If the maximum number of honours distinctions permitted has not been reached, the possibility of awarding additional distinctions will be reconsidered after the resit examination, which students may take in order to improve their final course grade.
For the assessment of this course, the use of "Artificial Intelligence" (AI) technologies is permitted exclusively for the preparation of the oral presentation as a support tool for tasks such as literature or information searches, text editing, or translation. Students must clearly identify any content generated using these technologies, specify the AI tools used, and include a critical reflection on how these tools have influenced both the process and the final outcome of the activity. Failure to disclose the use of AI in this assessed activity will be considered a breach of academic integrity and may result in a partial or full reduction of the activity grade, or more severe disciplinary sanctions in serious cases. The use of any external assistance, whether AI-based or otherwise, is not permitted during in-person assessment activities.
Unified evaluation
The assessment of students in the "unified evaluation" modality will take place on the same day as the final exam of the regular modality. There will be an exam on the whole content of the course, followed by a practical assessment and an interview on the subjects presented by peers. The resit assessment will follow the same rules as in the regular modality.
Bibliography
General bibliography:
- Basart, J.M, Rifà, J i Villanueva, M. "Fonaments de matemàtica discreta. Elements de combinatòria i d'aritmètica". Col. Materials de la UAB, n. 36. 1997.
- Graham, R.L, Knuth, D. E., Patashnik, O. "Concrete mathematics: a foundation for computer science". Addison-Wesley. 1990.
- Grimaldi, Ralph P. "Discrete and combinatorial mathematics: an applied introduction". 5th ed. Pearson.Addison-Wesley. 2004.
- Rosen, Kenneth H. "Discrete mathematics and its applications", 6th ed. McGraw-Hill. 2007.
- Lawler, Eugene. "Combinatorial Optimization: Networks and Matroids". Dover. ISBN 0-486-41453-1. (2001)
Graphs:
- Bondy, J.A. i Murty, U.S.R. "Graph Theory". Springer. 2008.
- Wilson, R.J. i Watkins, J. "Graphs: an introductory approach: a first course in discrete mathematics". Wiley, cop. New York. 1990.
Optimization:
- Alabert, A i Camps, R. "Programació Lineal, una introducció a la presa de decisions racional".
- Cormen, Thomas H.; Leiserson, Charles Eric.; Rivest, Ronald L., "Introduction to algorithms", Cambridge Mass. etc. : MIT Press cop. 1990
- Gordon, Gary.; McNulty, Jennifer, "Matroids : a geometric introduction", Cambridge University Press, 2012
Software
Python, SageMath.
Course groups and languages
The information provided is provisional until November 30. After this date, you will be able to consult the language of each group through this link. To access the information, you will need to enter the course CODE
| Type of teaching | Group | Language | Semester | Shift |
|---|---|---|---|---|
| (TE) Theory | 1 | Catalan | first semester | morning-mixed |
| (PLAB) Practical laboratories | 1 | Catalan | first semester | morning-mixed |
| (SEM) Seminars | 1 | Catalan | first semester | morning-mixed |
| (PLAB) Practical laboratories | 2 | Catalan | first semester | morning-mixed |
| (SEM) Seminars | 2 | Catalan | first semester | morning-mixed |
| (PLAB) Practical laboratories | 3 | Catalan | first semester | morning-mixed |