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.
Semester 1 (Examples and problems Pseudo / C)
1. Specification of algorithms
1.1. Introduction
1.2. Specifying algorithms
1.3. Preconditions and postconditions: syntax and semantics
2. Efficiency of algorithms
2.1. Introduction
2.2. Asymptotic measures. Growth rate
2.3. Calculating the execution time and cost
3. Recursive Design
3.1. Introduction
3.2. Design stages and recursive programs
3.3. Immersion Technique
3.4. Technique of "folding" and "unfolding"
3.5. Transforming a simple recursive iterative
3.6. Multiple recursion. Divide & Conquer
3.7. Ordination with Divide & Conquer: Mergesort and Quicksort
3.8. Verification of simple recursive algorithms
4. Backtracking Technique
4.1. Terminology and characterization of the problems
4.2. Recursive and iterative schemes
4.3. Solving methodology
4.4. Examples
4.5. Backtracking to find the best solution
4.6. Improved efficiency
5. Branch & Bound
5.1. Introduction to method
5.2. Algorithmic scheme
5.3. Examples
6. Greedy
6.1. Introduction to method
6.2. Algorithmic scheme
6.3. Examples
Semester 2 (Examples and problems Pseudo / C / Java)
7. Abstract Data Types
7.1. Introduction. Concept of abstract data types
7.2. Algebraic specification of abstract data types
7.3. Examples
8. Trees
8.1. Introduction
8.2. N-ary trees and binary trees
8.3. Paths
8.4. Search trees
8.5. AVL trees
8.6. B trees
8.7. Heaps
9. Tables
9.1. Introduction
9.2. Specification
9.3. Table design
9.4. Hash tables
9.5. Implementation of tables using balanced trees
10. Graphs
10.1. Introduction
10.2. Specification
10.3. Representation
10.4. Graph path
10.5. Shortest path algorithms
10.6. Minimal expansion trees
11. GRASP and GOF Design Patterns
The methodology is a hybrid of the lecture with exercises done in class and at home and practical sessions on short exercises or practices to deliver them. It is combined so that the student can go assimilating the contents firmly. A rhythm of knowledge presentation and the exercise of these, together, it seeks to facilitate this rate that ensures assimilation of knowledge in the short, medium and long term.
To calculate the final grade is necessary that theory and practice are all approved with a minimum of 5 each. The score is calculated by 60% of the theoretical part plus 40% of the portion of practice.
The theory consists of a majority of semester exams and continuous assessment. The midterm control and other exercises done and collected in class or practical short exercises implemented and fully functional stands can highlight. To take into account the continuous assessment note, the exam result must be equal to or greater than 3.5.
Semesters release material to the extraordinary if they have a minimum score of five (5). The student's semester grade is calculated as the higher of the only note of examination or the average between it and the continuous assessment (70% control and 30% of the continuous).
In June it is possible to recover the 1st Semester. In July (extraordinary) it is possible to recover the 1st Semester and 2nd Semester.
The final grade for the theory part can be calculated if the two semesters have a grade equal to or greater than five (5). It consists of the average of the two semesters of 50% each.
Each semester will have a practice and a practical exercise to deliver. Each practice and each exercise should be overcome with 5 to calculate minimum practical note. The practice note for one semester consists of 75% of the practice note plus 25% of the grade of the practical exercise. The final practice grade is 50% of the grade of each semester.
Set out in paragraph Assessment.
Available on the intranet.
Available on the intranet.