Academic management

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.

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):

The summary by work modalities is described as follows:

Exceptionally, if it would be needed by the sanitary conditions, not in-person activities could be required. Under those circumstances, students will be kept informed about all changes to be made.

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.

Exceptionally, if it would be needed by the sanitary conditions, not in-person activities could be required. Under those circumstances, students will be kept informed about all changes to be made.

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