| Código |
14335
|
| Ano |
1
|
| Semestre |
S2
|
| Créditos ECTS |
6
|
| Carga Horária |
PL(30H)/T(30H)
|
| Área Científica |
Informática
|
|
Mode of delivery |
Face-to-face
|
|
Work placements |
(Not applicable)
|
|
Learning outcomes |
This curricular unit has as objectives to acquire knowledge about:
- algorithms, in particular sorting and searching algorithms, and evaluation of the complexity of algorithms,
- data structures such as linked lists, stacks, queues, unbalanced and balanced trees, heaps and graphs,
- how to select the most appropriate data structures, given a practical problem,
- how to select the most appropriate algorithms for a given set of data structures.
Upon the conclusion of the course, students shall be able:
- to have developed skills on using algorithms, particularly in problems involving sorting and/or searching,
- to assess the efficiency of the algorithms by analyzing the technical complexity, in order to select the most efficient algorithms to solve any given problem,
- to explain the requirements of efficiency and performance for algorithms and data structures,
- to analyse the computational (spatial, temporal) complexity of programs.
|
|
Syllabus |
Algorithms
- Complexity analysis of algorithmd: Big-O
- Amortized analysis of algorithms
- Sorting algorithms in arrays
- Searching algorithms in arrays
Abstract Data Structures
- Simple linked lists
- Double linked lists
- Stacks
- Queues
- Binary trees
- Binary search trees
- N-ary trees
Balanced search trees
- Adelson-Velskii Landis (AVL)
- Red-Black
- Interval Tree
- 2-3 trees
Priority queue (Heap)
- Binary heap
- Binomial heap
Graphs
- Types of Graphs
- Data structures for graph representation
- Graph search algorithms: Breadth First Search, and Depth First Search
- Graph problems: Minimum Spanning Tree, Shortest Path, Maximum Flow, and Optimal Matching Problem
|
|
Main Bibliography |
"Competitive Programmer’s Handbook"; Antti Laaksonen; Draft July 3, 2018
"Algorithms", 4th Edition, 2011; Robert Sedgewick and Kevin Wayne; Addison Wesley, ISBN-13: 978-0321573513
"Introduction to Algorithms", 3rd Edition, 2009; Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, Clifford Stein; MIT Press, ISBN-13: 978-0262033848
"Estruturas de Dados e Algoritmos em C", 2008; António Manuel Adrego da Rocha; FCA-Editora de Informática. Coleção: Tecnologias de Informação; ISBN: 9789727222957
"Algorithms in C, Parts 1-5 (Bundle): Fundamentals, Data Structures, Sorting, Searching, and Graph Algorithms", 3rd Edition, 2001; By Robert Sedgewick; Addison-Wesley Professional; ISBN: 0201756080
"Data Structures and Algorithm Analysis", Edition 3.2 (C++ Version), 2013; Clifford A. Shaffer; Department of Computer Science, Virginia Tech.
|
| Language |
Portuguese. Tutorial support is available in English.
|