Titular Professors
Professors
Domain programming techniques worked on Methodology and Technology of Programming (analysis top-down, modularity, passing parameters and basic data structures).
Good knowledge of the language to be used for the exercises (Pseudo / C / Java).
Ability to follow and propose mathematical reasoning.
After completing the course, students should be able to:
- Evaluate the efficiency of an algorithm by calculating the cost.
- Design a recursive algorithm.
- Transform a recursive algorithm in iterative.
- Justify the need for formal specification of algorithms.
- Explain the main mechanisms of formal referral and formal proof of simple recursive algorithms and to implement it in exercices.
- Make the specification of a function in terms of pre- and post-conditions.
- Implement an algorithm unambiguously from the same specification.
- Choose the resolution methods most suitable combinatorial problems in every situation.
- Implement methods Backtracking, Branch & Bound and Greedy adapted to each specific problem and seeking maximum efficiency and effectiveness.
- Formally specify any abstract data type using algebraic specification.
- Implement an abstract data type from its algebraic specification.
- Design and implement the most appropriate data structure for a particular application, given certain requirements of temporal and spatial efficiency.
- Implement binary trees, n-ary, AVL, 2-3, B and heaps. Also implement the various possible paths.
- Implement the tables exposed on the subject.
- Implement the variants of different graphs. Implement the shortest path search.
This subjects contents are divided in two clearly separated parts:
During the first semester the focus is on the specification, analysis, design and formal verification of algorithms. Their design comprises the solving of problems with the use of simple and multiple recursive techniques. This part also includes the study and application of techniques oriented to solve problems with a combinatorial space of solutions.
The second semester is centered around the study of advanced lineal and non-lineal data structures, alongside their practical applications.
The studied techniques include theoretical and practical knowledge, abilities, experiences and critical thinking, all of which is based in solid, corroborated and well stablished theories and techniques.
During the subject, the following methodologies will be used, by semester:
First Semester:
o Lectures, for those contents that require them.
o Class problems and exercises, to consolidate knowledge.
o Evaluable exercises in class (CE) and practical work.
o Self-paced learning, for contents that wont be evaluated directly.
o Flipped-classroom, to motivate personal learning and to support students.
Second Semester:
o Project-Based Learning, where students will learn to design and implement data structures.
o Interspersed lectures to introduce necessary concepts, complemented during PBL.
o Self-paced learning, for contents that dont fit in the project.
This is an annual subject, which means that its final grade is derived from two semester grades, as long as both are greater than or equal to 5. If a student fails either semester, the whole subject is considered to be failed with a grade of 4.
Final_Grade= 0.5 · S1_Grade + 0.5 · S2_Grade
First semester:
The first semesters grade is obtained by weighting the knowledge and projects grades:
S1_Grade = 0.5 · S1_Knowledge_Grade + 0.5 · S1_Projects_Grade
Both grades must be greater than or equal o 5 in order to pass the semester. Otherwise, the final grade will be 4.
Knowledge
To obtain this grade, the final exam and continuous evaluation grades are weighted together, only if it benefits the student and the exam grade is greater than or equal to 3.5.
S1_Knowledge_Grade = max( 0.6 · S1_CE_Grade + 0.4 · S1_Exam_Grade,S1_Exam_Grade )
The midterm will be part of the continuous evaluation grade, with a specific weight of 30%. The rest will come from exercises done in class.
If the knowledge part of the semester is failed, a second call exam will be held in July. The continuous evaluation grade will not benefit the student, and a grade of 5 is required to pass.
Projects
This semesters projects grade is calculated by weighting together the grades of the two projects that will be carried out in pairs. Students must pass both projects with a grade of 5 or higher. Otherwise, this grade will be 4.
S1_Projects_Grade= 0.4 · Project_1_Grade + 0.6 · Project_2_Grade
Validating the final exam
If a student meets the following requirements, they can opt to validate the first semester final exam, getting their continuous evaluation grade as the semesters final grade. In particular, the student must:
Hand in all CE exercises, including the midterm, obtaining a weighted average grade greater than or equal to 7.
Deliver all first semester projects.
Assist classes regularly and show interest in the subject.
Students are free to give up this validation, opting to take the first semester exam, whether its during ordinary or extraordinary calls.
The specific mechanisms of validation, alongside how to submit a request, will be made public at the end of the semester, with some margin of time for those who end up having to study for the exam.
Second semester:
The second semester is almost exclusively based on the Project-Based Learning (PBL) mechanism, and therefore its final grade will be the projects grade, which must be greater than or equal to 5 in order to pass:
S2_Grade =S2_Project_Grade
The second semester midterm will consist of an optional exercise that will only be able to improve the students grade.
If the subjects team decides to do so, interviews for the project can be carried out to groups or individual students, in order to make sure that they have interiorized the semesters contents. If the project is failed, there will be a second call delivery in July, as the following section explains.
Brass, P. (2008). Advanced Data Structures. Cambridge University Press.
Cormen, T. H., Leiserson, C. E., Rivest, R. L., & Stein, C. (2014). Introduction to algorithms (3rd Edition). MIT Press.
Sedgewick, R., Wayne, K. (2011). Algorithms (4th Edition). Addison-Wesley Professional.
Skiena, S. S. (2012). The algorithm design manual (2nd Edition). Springer.