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.
Learning Outcomes of this subject are:
- Use of a real programming environment.
- Teamwork in the analysis, design and implementation of software.
- Definition of the modular structure and data to carry out computer applications.
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.
- 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, AVL trees, and R-trees, alongside the corresponding traversals.
- Implement hash tables.
The general contents by semester are as follows:
First semester:
1. Algorithm specification
2. Algorithm efficiency
3. Recursive design
4. Dynamic programming
5. Computational complexity theory
6. Combinatorial problems
Second semester:
7. Graphs
8. Trees
9. R-Trees
10. 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 and two projects. 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 second semester is assessed through a group project and an individual validation exam.
This is an annual subject, which means that its final grade is derived from two semester grades, given that both are greater than or equal to 5. If a student fails either semester, the whole subject is failed with a maximum grade of 4.
Final_Grade= 0.5 · S1_Grade + 0.5 · S2_Grade
First semester:
The first semester's grade is obtained by weighting its knowledge and projects grades.
S1_Grade = 0.5 · S1_Knowledge_Grade + 0.5 · S1_Projects_Grade
Both grades must be greater than or equal to 5 to pass the semester. Otherwise, the resulting grade will have an upper limit of 4.
Knowledge
To obtain this grade, the final exam mark and continuous evaluation grade are weighted together, only if it benefits the student and if the exam mark is greater than or equal to 5.
S1_Knowledge_Grade = max( 0.4 · S1_CE_Grade + 0.6 · S1_Exam_Mark,S1_Exam_Mark )
One of the continuous evaluation exercises will be submitted during the midterm week, substituting the corresponding exam.
If the knowledge part of the semester is failed, a second call exam will be held in the July extraordinary call. The continuous evaluation grade will not benefit the student in this scenario, and a mark of 5 is required to pass.
Projects
This semester'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.
S1_Projects_Grade= 0.4 · Project_1_Mark + 0.6 · Project_2_Mark
Final exam validation interview
If a student meets the following requirements, they can opt to validate the first semester final exam. To be eligible, a student must:
- Pass all CE exercises, obtaining a weighted average grade greater than or equal to 7.
- Pass Project 1 and submit Project 2, both in the first call (maximum grade of 10).
- Regularly assist the subject's class sessions.
The structure of the validation interview will be made public alongside the instructions to request one at the end of the semester.
The subject team will propose a validation grade based on the interview result and the CE marks. Students are free to give up this validation, opting to take the first semester exam instead.
Second semester:
The second semester is based on the Project-Based Learning (PBL) methodology, and therefore its final grade will be calculated from the project's grade.
The project is split into four phases, each corresponding to a content unit. Each phase will start with the release of the corresponding document and end in two evaluation activities: A checkpoint consisting of a meeting with the subject's team to validate the project's status, and a P2P self-evaluation questionnaire. For indicative purposes, a grade will be calculated in each phase based on these two elements.
Regardless of said indicative grades, the definitive evaluation will take place at the end of the semester and will consist of two separate marks: Code and report. The project grade will be equal to their weighted average, but each group member will get an individual grade by multiplying it by two factors in the [0.5, 1.5] range: Mentoring and P2P.
S2_Project_Grade = 0.6 · Code_Mark + 0.4 · Report_Mark
S2_Grade = S2_Project_Grade · Mentoring_Factor · P2P_Factor
The mentoring factor will be determined by the subject's team depending on the supervision during project sessions, as well as the checkpoint results. If the group skips or doesn't show any work in two or more checkpoints, the project grade will be NP and the entire group will have to retake the semester.
The P2P factor will be calculated from the results of the four self-evaluation questionnaires. In case a student doesn't answer one of them, the factor will be calculated from the remaining three. If two or more are left unanswered, the project grade will be NP and the student will have to retake the semester.
All phases of the code must satisfy their minimum requirements independently. Otherwise, the code mark will have an upper limit of 4.
Both the code and report mark must be greater than or equal to 5 to pass. The project grade will have an upper limit of 4 otherwise, and no individual factors will be applied to any group members.
Knowledge validation exam
To validate that the semester's contents have been understood even when working as a group, any student that submits the project will have to take a validation exam.
If the exam is passed with a 5 or more, it won't have any effect over the final grade. Otherwise, it will substitute it, meaning the student will have to retake the semester.
Retake
If the project is failed (including not submitting it or failing the validation exam), a retake exam will take place during July's extraordinary call, where a minimum mark of 5 is required to pass.
Depending on the mentoring and the state of the project, groups that are close to passing may exceptionally be allowed a second attempt (maximum grade of 8). The subject team has the power to allow only part of the members of a group to re-submit the project, meaning that the rest would have to retake the semester with the corresponding exam.
Re-submitting the project and the retake exam are mutually exclusive mechanisms. If a student is allowed a second attempt but decides to take exam the latter grade will prevail.
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.