Estudia
- Artes y humanidades
- Ciencias
- Ciencias de la salud
- Ciencias sociales y jurídicas
-
Ingeniería y arquitectura
- Doble Grado en Ingeniería Civil e Ingeniería de los Recursos Mineros y Energéticos
- Doble Grado en Ingeniería en Tecnologías y Servicios de Telecomunicación / Grado en Ciencia e Ingeniería de Datos
- Doble Grado en Ingeniería Informática del Software / Grado en Matemáticas
- Doble Grado en Ingeniería Informática en Tecnologías de la Información / Grado en Ciencia e Ingeniería de Datos
- Grado en Ciencia e Ingeniería de Datos
- Grado en Ingeniería Civil
- Grado en Ingeniería de los Recursos Mineros y Energéticos
- Grado en Ingeniería de Organización Industrial
- Grado en Ingeniería de Tecnologías Industriales
- Grado en Ingeniería de Tecnologías Mineras
- Grado en Ingeniería Eléctrica
- Grado en Ingeniería Electrónica Industrial y Automática
- Grado en Ingeniería en Geomática
- Grado en Ingeniería en Tecnologías y Servicios de Telecomunicación
- Grado en Ingeniería Forestal y del Medio Natural
- Grado en Ingeniería Forestal y del Medio Natural (En extinción)
- Grado en Ingeniería Informática del Software
- Grado en Ingeniería Informática en Tecnologías de la Información
- Grado en Ingeniería Mecánica
- Grado en Ingeniería Química
- Grado en Ingeniería Química Industrial
- Grado en Marina
- Grado en Náutica y Transporte Marítimo
- Información, acceso y becas
Algoritmia
The Algorithmics module (ALG) is part of the Programming area (PR), from the Application Software module (SA), with six more modules: Fundamentals of Informatics (FIN), Introduction to Programming (INP), Programming Methodology (MTP), Data Structures (ESD), Technologies and Paradigms of Programming (TPP) and Concurrent and Parallel Programming (PCP). In the PR area, the main content which covers the ALG module corresponds to fundamental Techniques in the design and verification of recursive algorithms and fundamental Techniques in the design and analysis of efficient algorithms.
Algorithmics is one of the programming foundations and is crucial for the development of any application, beyond the mere construction of programs. The goal of this module is providing to students basic techniques in the design and implementation of algorithms, and also tools to determine their efficacy and efficiency.
For addressing this module would be recommendable that the student has studied the following modules: Fundamentals of Informatics, Introduction to Programming and Programming Methodology.
General competences |
GTR1. Capacity of solving problems inside their study area. |
GTR2. Capacity of abstraction: capacity of creating and using models which represent real situations. |
GTR3. Capacity of acting autonomously. |
GTR4. Capacity of personal planning and organization. |
GTR6. Capacity of effective communication (in expression and comprehension) oral and written, with special emphasis in the writing of technical documentation. |
GTR7. Learning skills for starting subsequent studies or improving their formation with a certain degree of autonomy. |
GTR8. Motivation for the quality and continuous improvement and act rigorously in the professional development. |
Specific competencies | Learning results |
ECR6.1 Knowledge and application of basic algorithmic procedures in informatics technologies for designing solutions to problems. | PR32 Understand the classic algorithms schemas (Divide and Conquer, Branch and Bound, etc.), and apply them effectively to a problem whenever is required. |
ECR6.2 Analysis of the suitability and complexity of proposed algorithms. | PR33 Work out the efficiency of an algorithm from the complexity order technique (notation O). |
PR34 Understand the notion of recursive algorithm. | |
PR35 Apply the technique of designing recursive algorithms for solving a problem. | |
PR36 Transform a recursive algorithm into its equivalent iterative version. | |
PR37 Determine the suitability of a recursive algorithm versus its iterative version to solve a problem | |
PR38 Choose the most suitable algorithm schema for solving a specific problem. |
Didactic unit I: Fundamental concepts of algorithmics
Chapter 1. Analysis of algorithms
Introduction. Temporal and spatial complexity. Asymptotic notations: O, W and q. Complexity orders. Analysis of cases: the best, the worst and the average. Cost analysis of iterative and recursive algorithms. Cases of study: search, sort, etc.
Chapter 2. Design of Recursive Algorithms
Introduction. Principle of induction. Design and verification of a recursive function. Immersion techniques. Types of recursion. Transformation of recursive algorithms into their iterative versions.
Didactic unit II: Algorithmics Schemas
Chapter 3. Dynamic Programming
Introduction: general characteristics of dynamic programming. Optimization problems. Principle of optimality. General schema. Examples: knapsack, change-making, minimal paths, etc.
Chapter 4. Divide and Conquer
Introduction: general characteristics of divide and conquer. General schema. Examples: binary search, merge sort, quick sort, etc.
Chapter 5. Backtracking
Introduction: general characteristics of backtracking. Exploration trees. General schemas. Examples: knapsack, eight queens, etc.
Chapter 6. Greedy Schema
Introduction: general characteristics of greedy algorithms. General schema. Examples: change-making, knapsack, minimal paths (Dijkstra), minimum spanning trees (Prim and Kruskal), tasks scheduling, etc.
Chapter 7. Branch and Bound
Introduction: general characteristics of branch and bound. General schemas. Examples: knapsack, tasks scheduling, etc.
The face-to-face classes will consist of attending the following activities: theory classes, classroom activities, lab activities and group tutoring. In the theory classes, the teacher will alternate the theory contents with examples and exercises according to the theory. In the classroom activities, there will have discussions in relation with the theory, or practical exercises, and a high participation from the students will be required. On the contrary, the lab sessions are individual in order to guarantee that every student acquire the basic practical skills. The group tutoring expects to put in common the different questions and hardships from students during the learning process.
The academic tutoring can be done at the timetable established by each teacher. Moreover, the email can be used as a mean of communication to contact with the teacher.
Not physical presence activities consist in the study of both theory content, exercises and problems which have been recommended by the teacher or published in the Virtual Campus.
The module requires a total of 150 hours between physical and not physical presence of a student.
The estimated breakdown of work by chapter is as follows (two hours of theory classes, half an hour of a classroom activity and two hours of lab sessions per week):
PHYSICAL PRESENCE WORK | NOT PHYSICAL PRESENCE WORK | |||||||
Chapters | Total hours | Theory Class | Classroom Activity | Lab Sessions | Group Tutoring | Evaluation Sessions | Total | Autonomy work |
Analysis of algorithms | 35 | 7 | 2 | 5 | 1 | 15 | 20 | |
Design of Recursive Algorithms | 35 | 7 | 2 | 5 | 1 | 15 | 20 | |
Dynamic Programming | 44 | 7 | 1 | 5 | 1 | 14 | 30 | |
Divide and Conquer | 7 | 2 | 2 | 4 | 3 | |||
Backtracking | 12 | 2 | 1 | 2 | 5 | 7 | ||
Greedy Schema | 13 | 2 | 1 | 2 | 1 | 6 | 7 | |
Branch and Bound | 4 | 1 | 1 | 3 | ||||
Total | 150 | 28 | 7 | 21 | 1 | 3 | 60 | 90 |
The summary by work modalities is described as follows:
MODALITIES | Hours | % | Total | |
Physical presence | Theory Classes | 28 | 18,67 | 60 (40%) |
Classroom activities / Seminars / Workshops | 7 | 4,67 | ||
Lab sessions / field / informatic classroom / Language classroom | 21 | 14,00 | ||
Group tutoring | 1 | 0,67 | ||
Evaluation sessions | 3 | 2,00 | ||
Not physical presence | Autonomy work | 90 | 60 | 90 (60%) |
Total | 150 |
Ordinary Assessment
The learning evaluation is only performed with a continuous evaluation process. The final mark from the continuous evaluation consists in three parts, Theory, Lab and Group Work. The weights are the following:
- Theory 50%
- Lab 45%
- Group Work 5%
Continuous Evaluation in Theory.-
During the course, there are three exams to evaluate the student work in the theory part of the module. The two first exams will take place along the theoretical classes, and the third one at the official date which is already established for the evaluation. Every exam weight in the final mark of the theory part is: 25% the first, 25% the second and 50% the third. The weight is proportional to the teaching load in the evaluation part. There is not a final recovery exam.
Continuous Evaluation in Practice.-
In the lab sessions, individual work will have a continuous evaluation. Contents are divided into the same three blocks that theory and the same weights in the final lab mark. There is not a final recovery exam.
Evaluation of Group Work.-
A group work has to be done. It will be proposed and supervised during the classroom activities. Therefore, every group has to be made with students who belong to the same classroom activities.
If a student does not do the evaluable activities, then he/she will get a mark of zero. However, if the total weight in those activities is higher than 50% of the total mark, the final mark of the student will be “Not presented”.
If a minimum of 40% is not achieved in the mark of the Theory part or in the Practice part, the final mark in the module will be “Not pass”, with a maximum of 4.5 points. In the ordinary assessment, the module will be passed if the minimum mark is 5 points (out of 10).
Extraordinary Assessment
The evaluation consists in a theory exam and a practical exam, where the percentages in the final mark are as follows:
- Theory Extraordinary exam: 50%
- Practice Extraordinary exam: 50%
The module will be considered as pass if a student achieves a 50% in the mark of the Theory exam and 50% in the mark of the Practice exam at the minimum.
Students who achieve a 50% in the mark of the Theory exam or a 50% in the mark of the Practice exam in the ordinary assessment, they will not have the obligation of doing the part which has been passed in the extraordinary assessment during the current academic year. The module will be considered as pass if students achieve a 50% in the final mark.
Differentiated assessment
The evaluation will be the same in all the assessments. It consists in a theory and a practice exam with the following percentages in the final mark:
- Theory Exam 50%
- Practice Exam 50%
The module will be considered as pass, if a student achieves a 50% in the mark of the Theory exam and 50% in the mark of the Practice exam at the minimum.
Basic bibliography
- Brassard, G., Bratley, P., Fundamentos de Algoritmia, Prentice-Hall, 1997.
- Cormen,T. H.; Leiserson, C. E.; Rivest, R. L.; Stein, C., Introduction to Algorithms, The MIT Press, 2009.
- Peña, R., Diseño de Programas. Formalismo y Abstracción, Prentice-Hall, 2005.
Complementary bibliography
- Aho, A. V., Hopcroft, J. E., Ullman, J. D., Data Structures and Algorithms, Addison Wesley, 1987.
- Baase, S., Computer Algorithms, Introduction to Design and Analysis, Addisson Wesley, 1988.
- Horowitz, E., Sahni, S., Fundamentals of Computer Algorithms, Pitman, 1978.
- Scholl, P. C., Algorítmica y Representación de Datos, Recursividad y Árboles, Masson, 1986.
- Torres, C., Diseño y Análisis de algoritmos, Paraninfo, 1992.
Complementary documentation
In addition to this teaching guide, the teaching team will provide extra material through the virtual teaching environment of the module:
https://www.innova.uniovi.es/innova/campusvirtual/campusvirtual.php