The Advanced Programming and Data Structure subject delves deep into algorithm design for the resolution of complex problems. It reinforces the necessary core of computer science knowledge needed for engineering studies.
Abstract algorithmic reasoning is encouraged through the use of pseudocode, while concepts such as computational complexity enable students to analyze the performance of different solutions to justify their adequacy in a given context. Lastly, the practical implementation of these algorithms and structures allows students to continue developing some of the essential abilities in the field of programming, such as the capacity to detect and solve errors or teamwork skills.
Thus, the subject builds on the foundations of programming and algorithmics established in the first year, and prepares students to face advanced subjects that require knowledge from the field of computer science.
Titular Professors
Professors
- Proficiency in the programming techniques covered in the "Methodology and Technology of Programming" course (top-down analysis, modularity, parameter passing, and linear data structures).
- Ability to write code using a programming language (C/Java preferred).
- Ability to follow mathematical reasoning.
This subject's main objective is to provide an advanced vision of algorithm design. Algorithm efficiency, as well as diverse problem-solving techniques, are studied with the goal of proposing elegant solutions. After understanding the concepts considered in this subject, the student acquires abilities to propose and discuss the adequacy of solutions to complex problems
The subject's contents are as follows:
1. Algorithm specification
1.1 - Syntax
1.2 - Boolean expressions
1.3 - Quantifiers and range operators
2. Algorithm efficiency
2.1 - Efficiency, performance and complexity
2.2 - Asymptotic analysis
2.3 - Sorting algorithms
3. Recursive design
3.1 - Recursive design stages
3.2 - Tail recursion and immersion techniques
3.3 - Recursive sorting algorithms
4. Dynamic programming
4.1 - Top-down strategy
4.2 - Bottom-up strategy
5. Computational complexity theory
5.1 - Cobham's thesis
5.2 - Complexity classes
5.3 - P vs NP
6. Combinatorial problems
6.1 - Bruteforce
6.2 - Backtracking
6.3 - Branch and bound
6.4 - Greedy
During the subject, the following methodologies will be used:
- Lectures, for those contents that require them.
- Class problems and exercises, to consolidate knowledge.
- Evaluable exercises in class (CE) and practical work.
- Self-paced learning, for contents that won't be evaluated directly.
- Flipped-classroom, to motivate personal learning and to support students.
The subject is assessed through an exam (50%) and two projects (20% and 30%).. Continuous evaluation exercises are also conducted, which, in addition to encouraging students to keep up with the course, may allow those who perform well to have their final exam validated through an interview. The exam and the projects must all be passed independently.
The following criteria will be considered:
- Projects - Code:
- The correctness of the algorithms' design and implementation, in relation to the requirements.
- The efficiency and performance of algorithms, both in design and implementation.
- Code quality and ease of validation.
- Projects - Report:
- The correctness of the document's structure, in relation to the requirements.
- The suitability of conceptual explanations and of the justification of decisions.
- The relevance and mathematical correctness of performance analysis, as well as conclusions derived from it.
- Exams:
- The ability to propose an efficient solution to a complex problem that wasn't discussed beforehand.
- The correct application of techniques included in the syllabus, such as asymptotic analysis or recursive design.
- The ability to synthesize and visualize the behaviour of algorithms and data structures included in the syllabus.
- The reasonable justification of given answers.
Subject notes available on the virtual campus.
Brass, P. (2008). Advanced Data Structures. Cambridge University Press.
Cormen, T. H., Leiserson, C. E., Rivest, R. L., & Stein, C. (2022). Introduction to algorithms (4th Edition). MIT Press.
Sedgewick, R., Wayne, K. (2011). Algorithms (4th Edition). Addison-Wesley Professional.
Skiena, S. S. (2020). The algorithm design manual (3rd Edition). Springer.