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 Artificial Intelligence 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 subjects that rely on knowledge in the field of computer science.
Titular Professors
- Proficiency in the programming techniques covered in the "Fundamentals of Programming I" and "Fundamentals of Programming II" courses (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 shows that they grasp and are able to model different topologies of data structures as well as the algorithms necessary for their access and manipulation, considering their computational impact.
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. Computational complexity theory
4.1 - Cobham's thesis
4.2 - Complexity classes
4.3 - P vs NP
4.4 - Reductions
5. Combinatorial problems
5.1 - Bruteforce
5.2 - Backtracking
5.3 - Branch and bound
5.4 - Greedy
6. Graphs
6.1 - Definition and basic concepts
6.2 - Representation
6.3 - Traversals
6.4 - Topological sorting
6.5 - Minimum spanning tree
6.6 - Shortest path
7. Trees
7.1 - Definition and basic concepts
7.2 - Representation
7.3 - Traversals
7.4 - Binary search trees
7.5 - AVL trees
8. Tables
8.1 - Definition and basic concepts
8.2 - Representation
8.3 - Hash tables
During the subject, the following methodologies will be used, by block:
Advanced Programming:
- 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.
Data Structure:
- 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 block is assessed through an exam (50%) and two projects (20% and 30%). Continuous evaluation exercises are also conducted, which can improve the block's final grade. The exam and projects must be passed independently.
The second block is assessed through a group project (60%) and an individual exam (40%). The exam and the project must 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.