Authors:
This repository was created for our subject Software Engineering Algorithmic Techniques in Complutense University of Madrid. These were the problems we had to solve on the online judge, lab sessions, and exams. 1
Note
This is a cloned repository, because I wanted to have it on my profile, if you want to see the original, check Alex's github profile
There are 12 different themes we learned in this subject, and they are organized by the number on the judge following this pattern:
There are 2 numbers on each problem:
- The first number corresponds to the theme (see the different content down below)
- The second number means just the order in the judge.
Note
The second number might not be a number and can be a letter; if the letter is L, it means it was a lab exercise, and if it's an E, it means it was an exam exercise.
For example, the exercise 6.1 means it is the 6th theme and the first exercise of that theme, the exercise 3.L was the lab exercise of the third theme, and the exercise 6.E was an exam exercise.
Each folder also includes the problem .pdf file and a .txt cases file.
The .pdf file is the text of the problem, which usually includes a small introduction story with the problem
we have to solve, the structure of the entry data, the structure of how the output is supposed to look, and some test cases.
The .txt file contains the test cases for each problem; normally, these are the cases on the problem text, and sometimes there are more cases that we thought of to test the algorithm before uploading it to the judge.
- AVL trees and how to implement them.
- Priority queues and how to implement them.
- Variable priority queues
(indexed priority queue). - Heaps and
heapsort algorithm.
- Graphs and how to implement them
(Adjacency list and adjacency matrix). - Directed graphs.
- Weighted graphs.
- Directed weighted graph.
Kruskal algorithm.Dijkstra algorithm.
- Disjoint sets and how to implement them.
- Amortized analysis of the cost in time and cost in space of a function or algorithm.
- Greedy algorithms and how to know if they are optimal or not.
- Greedy algorithms used in maximization and minimization problems.
- Dynamic programming and whether it is optimal or not
- Coin change problem
- Full backpack problem
- Floyd's algorithm
- Dynamic programming in sequence problems
- Chainied matrix multiplication problem using dynamic programming
- Justified text problem
- Branch and bound and when to do it, knowing if it is optimal or not
- Definition
- Space complexity
- Time complexity
- Amortized cost
| Number | Section | Total exercises | Lab/Exam | Content |
|---|---|---|---|---|
| 1 | 1 | 2 (See) | N/A | AVL trees |
| 2 | 2 | 6 (See) | LAB | Priority queues |
| 3 | 2 | 4 (See) | LAB | Indexed priority queues |
| 4 | 3 | 7 (See) | LAB | Graphs |
| 5 | 3 | 5 (See) | LAB | Directed graphs |
| 6 | 3, 4 | 5 (See) | EXAM | Weighted graphs, disjoint sets, and Kruskal |
| 7 | 3 | 6 (See) | LAB | Weighted directed graphs and Dijkstra |
| 8 | 6 | 5 (See) | LAB | Greedy algorithms |
| 9 | 6 | 5 (See) | LAB | Greedy algorithms over minimization and maximization problems |
| A | 7 | 5 (See) | LAB | Dynamic programming |
| B | 7 | 5 (See) | LAB | Dynamic programming |
| C | 7 | 5 (See) | EXAM | Dynamic programming |
| D | 8 | 3 (See) | LAB | Branch and bound |
| R | ALL | 15 (See) | LAB | Review for all themes and types of exercises |
This project is licensed under the MIT License - see the LICENSE file for details.
Footnotes
-
Footnote (ns q poner aquí pero igual si le pregutamos al profe si podemos subir este repositorio pues podemos poner que le preguntamos y nos dijo que por él no hay problema. ↩