The Advanced Programming and Data Structure subject delves deep into algorithm design for the resolution of complex problems, as well as into the efficient use of data structures. It reinforces the necessary core of computer science knowledge needed for computer 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 in the computer science area of knowledge.
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, as well as to dive deep into some of the most used data structures. Algorithm efficiency, as well as diverse problem-solving techniques and structures, 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 by semester are as follows:
First semester:
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
Second semester:
7. Graphs
7.1 - Definition and basic concepts
7.2 - Representation
7.3 - Traversals
7.4 - Topological sorting
7.5 - Minimum spanning tree
7.6 - Shortest path
8. Trees
8.1 - Definition and basic concepts
8.2 - Representation
8.3 - Traversals
8.4 - Binary search trees
8.5 - AVL trees
9. R trees
9.1 - Definition and basic concepts
9.2 - Representation
9.3 - Basic algorithms: Search, insertion,deletion
9.4 - Optimizing kNN
10. Tables
10.1 - Definition and basic concepts
10.2 - Representation
10.3 - Hash tables
During the subject, the following methodologies will be used, by semester:
First semester:
- 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.
Second semester:
- Project-Based Learning, where students will learn to design and implement data structures.
- Interspersed lectures to introduce necessary concepts, complemented during PBL.
- Self-paced learning, for contents that don't fit in the project.
The first semester 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 second semester is assessed through a group project and an individual validation exam. If the validation exam is passed, the semester's grade will correspond to the project's, with additional adjustements derived from individual evaluation mechanisms. Otherwise, the semester's grade will correspond to the exam's.
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 in 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.