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.
It's important to have consolidated the contents of the "Methodology and technology of programming' course, such as descendant analysis, modularity, memory management, linear data structures, the C programming language, and others.
After understanding the concepts considered in this subject, the student acquires abilities to propose and discuss the adequacy of solutions to complex problems
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.
The subject is aligned with the following Learning Outcomes:
- Define interactive computer programs from logical and structured designs.
- Develop software in a structured and efficient manner with the purpose of creating an interactive project.
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.
The subject's general contents are as follows:
1. Algorithm specification
2. Algorithm efficiency
3. Recursive design
4. Dynamic programming
5. Computational complexity theory
6. Combinatorial problems
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 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 subject's grade is obtained by weighting its knowledge and projects grades.
Final_Grade = 0.5 · Knowledge_Grade + 0.5 · Projects_Grade
Both grades must be greater than or equal to 5 to pass the subject. 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.
Knowledge_Grade = max( 0.4 · CE_Grade + 0.6 · Exam_Mark,Exam_Mark )
One of the continuous evaluation exercises will be submitted during the midterm week, substituting that exam.
If the knowledge part of the subject 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
The projects grade is calculated by weighting together the marks of the two projects that will be carried out. 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= 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 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 final exam instead.
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.