Algorithmics and Combinatorics in Graphs. Heuristic Methods
Code: 104388Credits: 6
2026/2027
| Degree programme | Type | Course |
|---|---|---|
| Computational Mathematics and Data Analytics | FB | 1 |
Contact lecturer
- Name :
- Albert Ruiz Cirera
- Email :
- albert.ruiz@uab.cat
Teaching staff
- Albert Ruiz Cirera
Group languages
You can consult this information at the end of the document.
Prerequisites
It is recommended that the student has taken Mathematics in the two baccalaureate courses and has examined this matter in the PAU.
Objectives
- Know the combinatorial graphs and their terminology.
- Know the different search algorithms and movement in graphs.
- Know the types of dynamic data for representation of graphs and their implemtation in C.
- Know the basic algorithms of optimal searches in graphs and evaluate their complexity.
Learning outcomes
- KM02 (Distinguish the objects of calculus with functions and their properties and uses.) Distinguish the objects of calculus with functions and their properties and uses.
- KM05 (Describe the mathematical concepts and objects specific to the graph theory.) Describe the mathematical concepts and objects specific to the graph theory.
- SM05 (Develop independent strategies to solve problems specific to numerical calculus, probability and graph theory.) Develop independent strategies to solve problems specific to numerical calculus, probability and graph theory.
Contents
- Combinatorial algorithms for graphics.
- Introduction to combinatorial graphs.
- Search in graphs: Depth-first and Breadth-first.
- Greedy Algorithms.
- Recursion.
- Abstract data types: Dynamic lists and trees.
- Graphic representation algorithms. Advantatges and disadvantages of each of the options.
- Abstract and dynamic data types for graphs and their implementation in C.
- Basic algorithms for optimal search graphs and their complexity.
- Calculation of distances from latitude and longitude.
- Algorithm of Dijkstra for optimal routes in graphs.
- Algorithm A *: heuristic search for optimal paths in graphs.
Learning activities and methodology
| Title | Hours | ECTS | Learning outcomes |
|---|---|---|---|
| Resolution of complementary exercises | 30 | 1.2 | |
| Completion of the practices | 62 | 2.48 | |
| Attend the theoretical and practical classes | 49 | 1.96 |
The weekly sessions of the subject will be divided, usually, in two parts:
- A theoretical part in which the teacher will introduce the concepts, methods and examples related to the syllabus of the subject.
- A practical part in which students will be proposed a series of problems or exercises in which they will be shown and a concrete work will be worked on that which has been seen in the theoretical part. Each practice will have a different statement, which will be published on the Virtual Campus and will involve the delivery of the answers to some questions raised.
Complementary exercises will also be proposed as an autonomous activity to help them understand the applied part of the subject.
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
Continuous assessment activities
| Title | Weight | Hours | ECTS | Learning outcomes |
|---|---|---|---|---|
| Individual practical work | 35% | 5 | 0.2 | KM02, KM05, SM05 |
| Delivery of practical exercices | 25% | 0 | 0 | KM02, KM05, SM05 |
| End of term exam | 40% | 4 | 0.16 | KM02, KM05, SM05 |
The evaluation will consist of the following activities:
- A final exam, which accounts for 40% of the note.
- An individual practical work with a delivery period where it will be necessary to develop and implement algorithms, which account for 35% of the note.
- Delivery of practical exercises that will be carried out in groups of two. They count 25% of the note. This is a continuous evaluation activity and is not recoverable.
Teh final marks will be:
- The weighted average according to the weight of each part for those students who have obtained 3.5 or more in all parts.
- The minimum between 3.5 and the weighted average according to the weight of each part for those students who have done any of the individual evaluations and in any of the parts does not reach 3.5.
- Not assessable for those students who have not done any of the individual evaluations.
Those who have been evaluated in all three parts and do not pass the subject may present themselves for a retake of the final exam and the individual practical work. In particular, those who have not submitted the individual practical work and the final exam will not be able to present themselves for retake.
The instructions for each submission will make explicit what use of Artificial Intelligence can be made. Skipping these instructions will be considered academic fraud.
This subject does not allow a unique evaluation procedure.
[Translated from the Catalan version by Google translator]
Bibliography
- Fundamentos de programación (algoritmos, estructuras de datos y objetos), Luis Joyanes, McGraw-Hill, Madrid etc. (2003).
- Algoritmos y estructuras de datos – una perspectiva en C, Luis Joyanes y Ignacio Zahonero, McGraw-Hill, Madrid etc. (2004).
- Grafs combinatòris i cerques en gràfs:Wikipedia
- Tipus abstractes de dades i programació orientada a objectes: Llistes dinàmiques i arbres; Tipus abstractes i dinàmics de dades per a grafs i la seva implementació en C.
- Notes del curs
- Algoritmos + Estructura de datos = Programas, Niklaus Wirth, Ediciones del Castillo, Madrid (1986).
- C algoritmos, programación y estructuras de datos, Luis Joyanes Aguilar et al., McGraw-Hill, Madrid etc. (2005).
- Algorismes de representació de grafs. Avantatges inconvenients de cada una de les opcions: Wikipedia i notes del curs
- Càlcul de distàncies a partir de la latitud i la longitud: Wikipoedia i notes del curs
- Algorisme de Dijkstra per a rutes òptimes en grafs: Presentació d'Eric Demaine
- Algorisme A*: cerca heurística per a rutes òptimes en grafs
- Heuristics: Intelligent Search Strategies for Computer Problem Solving, Judea Pearl
Addison-Wesley Pub (Sd) | ISBN: 0201055945 | 1984-04 | djvu (ocr) | 399 pages | 3.66 Mb
Pagines: 33 to 46, 48, 49, 64, 65, 73--85.L'exemple a les pàgines 52--54 pot ser relevant.
Software
C
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 | second semester | morning-mixed |
| (PLAB) Practical laboratories | 1 | Catalan | second semester | morning-mixed |
| (SEM) Seminars | 1 | Catalan | second semester | morning-mixed |