|
Teaching GuideTerm Faculty of Computer Science |
| Grao en Enxeñaría Informática |
 Subjects |
| Algorithms |
| Contents |
|
|
|
| Identifying Data | 2017/18 | |||||||||||||
| Subject | Algorithms | Code | 614G01011 | |||||||||||
| Study programme |
|
|||||||||||||
| Descriptors | Cycle | Period | Year | Type | Credits | |||||||||
| Graduate | 1st four-month period |
Second | Obligatoria | 6 | ||||||||||
|
||||||||||||||
| 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 |
|
