| Study programme competencies |
| Code | Study programme competences |
| A12 | Coñecemento e aplicación dos procedementos algorítmicos básicos das tecnoloxías informáticas para deseñar solucións a problemas, analizando a idoneidade e a complexidade dos algoritmos propostos. |
| A13 | Coñecemento, deseño e utilización de forma eficiente dos tipos e estruturas de datos máis adecuados á resolución dun problema. |
| B3 | Capacidade de análise e síntese |
| C3 | Utilizar as ferramentas básicas das tecnoloxías da información e as comunicacións (TIC) necesarias para o exercicio da súa profesión e para a aprendizaxe ao longo da súa vida. |
| Learning aims | |||
| Learning outcomes | Study programme competences | ||
| To recognize the importance of studying algorithm complexity and to know how to perform empirical studies to determine that complexity. | A12 A13 |
B3 |
C3 |
| To know how to apply techniques for algorithmic complexity analysis. | A12 A13 |
B3 |
|
| To identify data structures adapted to the studied algorithms to obtain more efficient and robust implementations. | A13 |
B3 |
C3 |
| To know the most used techniques in algorithm design. | A12 |
B3 |
|
| To use different computational models and levels of abstraction needed for algorithm design. | A12 |
B3 |
|
| To understand the elements of study about computational complexity. | A12 A13 |
B3 |
|
| Contents |
| Topic | Sub-topic |
| Lesson 1. Analysis of Algorithms. Code: T1. Outline: This first lesson addresses the analysis of algorithm complexity as one of the main goals of the course. The idea is to add algorithmic efficiency to the toolbox of already familiar criteria like program structure and correctness. |
Lesson topics: 1. Analysis of the efficiency of algorithms: asymptotic notations, computation model, empirical verification of the analysis. 2. Calculation of runtimes: analysis of worst and average cases, calculation of O, resolution of recurrence relations. |
| Lesson 2. Data Structures Code: T2. Outline: In this lesson, a revision of basic data structures is proposed (stacks, lists, queues, trees, sets and graphs) to study their usage concerns regarding spatial and temporal complexities. Similarly, a deep study is done over interesting structures regarding execution times: hash tables and heaps. This last structure will be turned to when dealing with an improvement over graph algorithms and in certain dynamic programming cases. The complexity of the searching operation can be used as a leitmotif in this lesson. In the introduction of this lesson, it is important to insist on structure criteria of any application designed, motivating the use of abstract data structures and its implementation by modules. The objective is to establish general outlines of what is considered a programming discipline, which must be required from the student in the practicals. |
Lesson topics: 1. Stacks, queues and lists 2. Trees and heaps 3. Hashing 4. Disjoint sets 5. Graphs (representation) |
| Lesson 3. Algorithms on sequences and sets of data Code: T3. Outline: The problem of sorting a sequence of elements becomes, in this part of the course, an ideal excuse both for studying the complexity of various kinds of algorithms and to present different algorithm design strategies that can be extrapolated to solve other problems. One of the algorithms that merit special attention is quicksort, as it can be used to introduce the fundamental characteristic of random algorithms, which can behave in different ways on the same input. A direct consequence is that the concepts of "best case" or "worst case" for an input no longer makes sense, which is an important aspect to discuss in class. |
Lesson topics: 1. Search algorithms 2. Sorting algorithms: insertion, Shell, heapsort, mergesort, quicksort 3. Random algorithms |
| Lesson 4. Greedy algorithms Code: T4. Outline: In this lesson, greedy algorithms are studied. Once the technique is explained using its general characteristics, presented using an example, the most representative algorithms of this category will be studied: graph algorithms, a solution for the knapsack problem and a planning task problem. |
Lesson topics: 1. The knapsack problem 2. Graph algorithms: topological sorting, minimum spanning tree and shortest paths 3. Hashing |
| Lesson 5. Algorithm design by induction Code: T5. Outline: At this point, the student has already seen various algorithms that follow a divide-and-conquer strategy: mergesort and quicksort, binary search, maximum subsequence sum... the work proposed in the first part of this lesson consist in generalising the formulation of said strategy, identifying its distinct features in each of the proposed algorithms. The second unit of this lesson concerns the use of a bottom-up strategy to find a general solution from the solutions to elementary subproblems. From an efficiency viewpoint, the use of top-down techniques like "divide and conquer" will be questioned in some situations. The option of dynamic programming can yield a compromise allowing, when possible, an optimization of the amount of memory required by the algorithm. |
Lesson topics: 1. Divide and conquer 2. Dynamic programming: optimality principle, knapsack problem |
| Lesson 6. Exploring graphs Code: T6 Outline: The objective of this lesson is to give a broader insight of graph applications to undertake problems of different nature, and to take into account algorithmic techniques linked to the development of relevant areas of computer science as artificial intelligence. The graph algorithms studied in greedy algorithms lesson (T4) agree on visiting all the graph nodes. The improvement of the execution times of those algorithms that avoid the exhaustive visit of the graph nodes will be emphasized. |
Lesson topics: 1. Exploring graphs 2. Strategy games 3. Backtracking algorithms |
| Lesson 7. Computational complexity Code: T7 Outline: In this last lesson, we introduce a reasoning about the set of algorithms that can solve each kind of problem. We will deal with the complexity of problems, lower bounds for problem complexity and NP-completeness. In brief, we will address the main techniques and concepts used in the study of computational complexity. |
Lesson topics: 1. NP-Completeness, NP-Complete problems |
| Planning | ||||
| Methodologies / tests | Competencies | Ordinary class hours | Student’s personal work hours | Total hours |
| Guest lecture / keynote speech | A12 A13 B3 | 28.75 | 28.75 | 57.5 |
| Short answer questions | A12 A13 B3 | 1.25 | 6.25 | 7.5 |
| Laboratory practice | A12 A13 B3 C3 | 19 | 19 | 38 |
| Supervised projects | A12 A13 B3 C3 | 4 | 2 | 6 |
| Problem solving | A12 A13 B3 | 5 | 10 | 15 |
| Objective test | A12 A13 B3 C3 | 4 | 20 | 24 |
| Personalized attention | 2 | 0 | 2 | |
| (*)The information in the planning table is for guidance only and does not take into account the heterogeneity of the students. | ||||
| Methodologies |
| Methodologies | Description |
| Guest lecture / keynote speech | Lectures where theoretical knowledge is taught using various resources: blackboard, slides, projections, demos and virtual resources. They may include guest lectures by invited speakers. |
| Short answer questions | Tests that consist in solving exercises involving the execution of cases using the algorithms studied in the course, or their adaptation to other situations. These tests are assessed. |
| Laboratory practice | Practicals designed by the professor, based in the knowledge acquired by the student in the keynote speeches, and which therefore complement them. The students will develop this work in groups of two throughout the course, and individually in a final practical that is included in the objective test. The practicals will consist in the implementation of programs that illustrate problems related with the course contents. A report of results will be required for assessment. During the hours assigned to each practical, the reports of the previous practical will be assessed. |
| Supervised projects | Supervised projects proposed by the professor and developed by the students, either in groups or individually. |
| Problem solving | Examples will be developed on the theoretical contents of each part of the course, and doubts will be solved. The resolution of some of the problems will be assessed individually. |
| Objective test | Knowledge of the theoretical and practical contents of the course will be assessed, as well as the final individual practical assignment. |
| Personalized attention |
|
|
| Assessment | |||
| Methodologies | Competencies | Description | Qualification |
| Problem solving | A12 A13 B3 | Evaluation of two exercises where, after solving doubts, examples about content skills of the lesson will be developed. These exercises will be carried out in Small Group Tutorial (SGT) hours scheduled along the course. Sometimes, they may be finished in non-teaching hours. |
10 |
| Objective test | A12 A13 B3 C3 | Theoretical and operative knowledge of the subject will be evaluated. Individual theory exam (2h): 50% Individual practice exam (2h): 20% To take the first opportunity practice exam, it is mandatory to deliver the laboratory practices in time. |
70 |
| Laboratory practice | A12 A13 B3 C3 | Four laboratory practicals made in pairs, where it will be assessed: program structure, documentation quality, clarity, appropriateness, and result explanation. To deliver the laboratory practicals in time and form is a necessary condition to take the objective individual practical test for the first opportunity (January). Assessment is done by monitoring practical work, during the laboratory practicals sessions. |
10 |
| Short answer questions | A12 A13 B3 | Three objective tests of monitoring assessment, where the theoretical contents skills of the academic work will be evaluated. They will be made during lectures and will be pre-announced in the initial planning presented in the start of the course. |
10 |
| Assessment comments | |||
|
In the 2nd opportunity, the student may attend again the theory and practice exams (parts planned in the objective test). In the advanced opportunity of December the total grade (100%) corresponds to a specific exam with theoretical and practical issues. |
|||
| Sources of information |
| Basic |
M. A. Weiss (1995). Estructuras de Datos y Algoritmos. Addison Wesley
G. Brassard y P. Bratley (1997). Fundamentos de Algoritmia. Prentice Hall
U. Manber (1989). Introduction to Algorithms - A Creative Approach. Addison Wesley |
|
|
|
| Complementary |
R. Sedgewick (1988). Algorithms. Addison Wesley
R. Peña Marí (2005). Diseño de Programas. Formalismo y Abstracción. Tercera edición.. Pearson Prentice Hall
B. W. Kernighan y D. M. Ritchie (1991). El lenguaje de programación C, 2ª edición. Prentice Hall
T. H. Cormen, C. E. Leiserson y R. L. Rivest (1990). Introduction to Algorithms. MIT Press |
|
|
| Recommendations | ||
| Subjects that it is recommended to have taken before | ||
|
| Subjects that are recommended to be taken simultaneously | |
|
| Subjects that continue the syllabus | ||
|
| Other comments | |