template-browser-not-supported

Doble Grado en Ingeniería Informática en Tecnologías de la Información / Grado en Ciencia e Ingeniería de Datos

Back Back

Algoritmia

Código asignatura
2GITICID-2-006
Curso
Segundo
Temporalidad
Primer Semestre
Carácter
Obligatoria
Créditos
6
Pertenece al itinerario Bilingüe
Yes
Guía docente

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