Academic management

This subject belongs to the field of Programming, and transversely, to the common module of Computer Science. This course is taught in the second semester of the second year and is closely related to the Data Structures course, which is taught in the first semester of the same year.

Like the rest of the courses in the field of programming, it is a very practical course, since almost 50% of contact hours are labs.

This course explores the idea of computational complexity (which has been raised by other courses), that is essential to compare the efficiency of different algorithms. Furthermore, different techniques of algorithms design are addressed to solve computationally complex problems. It is, together with Data Structures, a bridge between basic programming courses and courses that address specific problems: Intelligent Systems, Design of Programming Languages, Entertainment Software and Video Games, and Software for Mobile Devices.

To address this course it is recommended to have acquired the competences of the following courses of first year: Introduction to Programming, Automata and Discrete Mathematics, and Programming Methodology, and the following course of second year: Data Structures. Note that it is also important to study Technologies and Programming Paradigms simultaneously with Algorithms since the latter one is also a second term course of the second year.

Specific competences

• Bas.3. Ability to understand and master the basic concepts of discrete mathematics, logic, algorithms and computational complexity, as well as their application for solving engineering problems.
• Com.6. Knowing and applying basic algorithm procedures of computer technologies to design solutions to problems, analysing the suitability and complexity of the proposed algorithms.
• Com.8. Capacity to analyse, design, construct and maintain efficient and safe robust applications, choosing the most appropriate programming paradigm and languages.
• Com.14. Knowledge and application of the fundamental principles and basic techniques of parallel, concurrent, distributed and real-time programming.
• ISW.1. Capacity to develop, maintain and evaluate software services and systems that meet all the user's requirements and behave reliably and efficiently, are accessible for development and maintenance and comply with quality standards, by applying the theories, principles, methods and practices of Software Engineering.

General competences

• CG-1. Capacity to design solutions to problems.
• CG-4. Capacity for analysis and synthesis.
• CG-7. Capacity for written communication.
• CG-11. Capacity for teamwork.

Learning outcomes

• RA.P-3. To analyse, design, develop, select, evaluate and maintain applications and computer systems, ensuring reliability and quality, applying the theories, principles, methods and practices of Software Engineering, choosing the most appropriate paradigm and programming languages, considering the limitations derived from the cost, time, the existence of systems already developed and the organizations themselves. [Com.1] [Com.8] [Com16] [ISW.1] [ISW.2] [ISW.4] [ISW.6] [CG-1] [CG-3] [CG-4] [CG-11] [CG-14] [CG-20] [CG-26] [CG-28]
• RA.P-4. To understand and apply basic algorithmic procedures, best suited data types and structures for solving a problem, analysing the relevance and complexity of them. [Bas.3] [Com.6] [Com.7] [CG-3]
• RA.P-5. To know and apply fundamental principles and basic techniques of parallel, concurrent, distributed and real time programming. [Com.14] [CG-11]
• RA.P-6. Ability to solve integration problems based on strategies, standards and available technologies. [ISW.3] [CG-1][CG-4] [CG-6] [CG-22]
• RA.P-7. To document and present the solution to a problem through text and diagrams, meeting norms and standards of software design and developing software using either Spanish or English. [CG-10] [CG-7]

1. Principles of Algorithms
   1. Concepts
   2. Analytical complexity
   3. Empirical execution times
2. Sorting.
   1. Basic sorting algorithms
   2. Fast sorting algorithms
   3. Analysis and comparison of sorting algorithms
3. Algorithm design techniques
   1. Divide and Conquer (Recursion)
   2. Greedy algorithms
   3. Dynamic programming
   4. Backtracking
   5. Branch and bound algorithms 
4. Parallel algorithms
   1. Parallel divide and conquer
   2. Parallelization of other techniques
   3. Advanced algorithms (Tree games and other techniques)

Following the philosophy of European credits, the course will have class and non-class activities, which will be followed up by the faculty.

The in-person activities will have five modalities:

1. Expository classes, to present the fundamentals of the subject and guide students in their autonomous work.
2. Classroom practices / seminars, to achieve an active and collaborative learning, integrating classroom and virtual work.
3. Labs, to do different projects in which algorithms for solving various problems posed will be designed and implemented. These projects require non-contact work of students.
4. Group tutorships, to track the students to identify gaps and guide students to solve them.
5. Evaluation sessions, to do exams both theoretical and practical with computer to assess students’ knowledge.

Exceptionally, online teaching activities might be established if the general health situation requires so. In that case, students will be informed in due course.

Ordinary call

Minimum Attendance. It is necessary to attend a minimum of 80% of the labs.

Assessment of learning is done through a process of continuous assessment based on:

• Theory Mark (TM): This mark is composed of two parts:
  1. First exam (FE). About mid-semester there will be an exam in which approximately half of the theoretical content will be evaluated.
  2. Second exam (SE). Coinciding with the final exam of the ordinary call, there will be an exam in which approximately the second half of the theoretical content will be evaluated.

            TM = 0.5 * FE + 0.5 * SE

            However, students have the option to take SE with all the theoretical content of the whole course, so the final mark will be calculated as follows:

            TM = SE

• Lab Mark (LM): This mark is composed of two parts:
  1. Continuous assessment of laboratory work (CAL). It is done by defending the work that has been carried out by each student during the whole academic year. The teacher will keep track of the work done by each student and may propose changes or additions to the developed tasks during lab sessions. It is necessary to have a minimum attendance of 80% and a minimum of 80% of the requested deliveries to obtain a mark in this part.
  2. Lab exam (LE).
     • Students that DO NOT pass the continuous assessment in the labs but pass the theoretical exam, can take a final practical exam. This assessment will provide the whole laboratory mark. So, in this case: LM = LE
     • On the other hand, all the students with continuous assessment of laboratory work CAL >= 5 may take an optional exam to get up to 3 extra points: LM = 0.7 * CAL + 0.3 * LE

Once both have been passed (TM and LM), the course is passed with the following final grade:

 FG = 0.5 * TM + 0.5 * LM

In the event of not achieving any of the conditions required to pass the course, and having taken assessments weighted by at least 50% of the total weight of the course, the final grade will be calculated as:

FG = Minimum (4, 0.5 * TM + 0.5 * LM)

All partial marks of both theory and labs without delivery will be considered as 0 and the same formula will be applied.

If the student has passed any of the previous two parts (TM or LM), the mark is kept for the extraordinary call.

Extraordinary call and differentiated assessment model

There will be a written exam to obtain TM.

There will also be a practical exam with a computer to obtain LM.

If both are equal to or greater than 5, the course is passed with the following final grade:

FG = 0.5 * TM + 0.5 * LM

If either condition (TM>=5 or LM>=5) is not met, the final grade will be calculated as:

FG = Minimum (4, 0,5 * TM + 0,5 * LM)

Advance extraordinary call

No previous mark is kept, and the assessment exams will be conducted as in the extraordinary call.

Exceptionally, online evaluation activities might be established if the general health situation requires so. In that case, students will be informed in due course.

• Cormen, T.H. [et al.]. Introduction to algorithms. 3rd ed. Cambridge: MIT Press, 2009. ISBN 9780262033848.
• Dasgupta S.; Papadimitriou C.; Vazirani U. Algorithms. Boston: Mc Graw Hill Higher Education, 2006. ISBN 9780073523408.
• Oliet, Narciso Martí, Yolanda Ortega Mallén, and Alberto Verdejo López. Estructuras de datos y métodos algorítmicos. 2a edición: 213 ejercicios resueltos. Edición: 1. Madrid: Ibergarceta Publicaciones S.L., 2013.
• ARROYO, Julio GONZALO, and Miguel RODRÍGUEZ ARTACHO. Esquemas Algorítmicos: Enfoque Metodológico y Problemas Resueltos. Madrid: UNED, 1997.
• G. Brassard, P. Bratley. Fundamentos de Algoritmia. Prentice Hall, 1997.

The course will be available in the virtual campus of the University of Oviedo, which will provide teaching materials, tasks created for individual work, and exercises that will be requested during the teaching period.