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.
The Learning Outcomes of this subject are:
- The student will be able to identify the theory, concepts and methods of programming and data structures to solve a specific problem.
- The student will be able to solve a problem by designing and implementing an efficient algorithm using appropriate data structures.
To achieve these outcomes, the subject divides its contents into two blocks: Advanced Programming and Data Structure.
By the end of the course, students should be able to:
- Justify the need for formal algorithm specification.
- Formally specify an algorithm in terms of pre- and post-conditions.
- Implement an algorithm unambiguously based on its specification.
- Evaluate the efficiency of an algorithm by calculating its cost.
- Design a recursive algorithm.
- Explain the main mechanisms for formal derivation and verification of simple recursive algorithms and apply them to practical problems.
- Recognize different classes of computational complexity such as P or NP, as well as reductions between problems of different classes.
- Choose the most appropriate methods for solving combinatorial problems in each situation.
- Implement Backtracking, Branch & Bound, and Greedy methods adapted specific problems, striving for maximum efficiency and effectiveness.
- Design and implement the most suitable data structure for a given application, considering time and space efficiency requirements.
- Implement graphs and apply algorithms to solve problems such as finding the shortest path.
- Implement binary search trees and AVL trees, alongside the corresponding traversals.
- Implement hash tables.
The subject's general contents are as follows:
1. Algorithm specification
2. Algorithm efficiency
3. Recursive design
4. Computational complexity
5. Combinatorial optimization
6. Graphs
7. Trees
8. 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 and two projects. Continuous evaluation exercises are also conducted, which can improve the block's final grade.
The second block is assessed through a group project and an individual exam.
Despite this being a semester course, it?s structured in two blocks that need to be passed independently, both with a grade of 5 of higher. If both blocks passed the subject will be failed with a maximum grade of 4.
Final_Grade = 0.5 · B1_Grade + 0.5 · B2_Grade
Block 1 ? Advanced programming:
The grade of the first block will be given from the averaging between knowledge and project grades.
B1_Grade= 0.4 · B1_Knowledge_Grade + 0.6 · B1_Projects_Grade
A minimum of 5 will be required on each part in order to pass the block, otherwise the maximum grade will be a 4.
Knowledge
To get the knowledge grade for the first block, the grade from the midterm exam and the continuous evaluation grade will be used, only if it benefits the student and in the case the midterm?s grade is equal or greater than 5.
B1_Knowledge_Grade = max( 0.4 · B1_CE_Grade + 0.6 · B1_Exam_Grade,B1_Exam_Grade )
If the knowledge part of the block is failed, a second call exam will be held in the July extraordinary call. The
continuous evaluation grade will not benefit the student, and a mark of 5 is required to pass.
Projects
This block?s projects grade is calculated by weighting together the marks of the two projects that will be carried out
in it. Students must pass both projects with a grade of 5 or higher. Otherwise, the resulting grade will have an upper
limit of 4.
Projects_Grade_B1 = 0.5 · Project_1_Mark + 0.5 · Project_2_Mark
Block 2 ? Data Structures:
The second semester is based on the Project-Based Learning (PBL) methodology, and therefore there will only be one project and a final exam. Passing both elements with a grade of 5 or higher is required. Otherwise the block?s mark will have an upper limit of 4.
B2_Grade = 0.4 · B2_Exam_Grade + 0.6 · Project_3_Mark
Summary and retakes:
In summary, the subject?s grade will be determined mainly by 5 evaluated activities, each with the following weights:
Project 1: 15%
Project 2: 15%
Project 3: 30%
Block 1 Exam: 20% (midterms, if passed on ordinary call grade may be improved by CE)
Block 2 Exam: 20% (final)
Each of these activities will have a retake/re-submission on July?s extraordinary call on the dates specified on the subject?s teaching plan or calendar.
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.