| Code |
14335
|
| Year |
2
|
| Semester |
S2
|
| ECTS Credits |
6
|
| Workload |
PL(30H)/T(30H)
|
| Scientific area |
Informatics
|
|
Entry requirements |
Notion of block. Iterative and Conditional Blocks.
Notions of structured programming. C Language.
|
|
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.
|
|
Teaching Methodologies and Assessment Criteria |
In order to guarantee that students achieve the main goals expected for this course, classes will be divided into the following types:
- 2h/week theoretical classes (T) for showing the main theoretical concepts, methods and algorithms, using the board, oral discussion and data projection as main tools;
- 2h/week practical classes (PL), which will serve for applying and testing concepts learned during the theoretical classes, by problem solving and exercise sheets;
- 2h/week of tutorial sessions
Evaluation:
- The evaluation is carried out by two written tests (8 points each), and 2 practical tests (4 points)
- Final exam for admitted students
Written test 1: April, 16; 6 pm
Written test 2: Mai, 21; 6 pm
|
|
Language |
Portuguese. Tutorial support is available in English.
|