Code |
12121
|
Year |
3
|
Semester |
S2
|
ECTS Credits |
6
|
Workload |
PL(30H)/T(30H)
|
Scientific area |
Informatics
|
Entry requirements |
Knowledge about C programming language.
|
Mode of delivery |
Direct
|
Work placements |
Not applicable
|
Learning outcomes |
This curricular unit has as objectives: - to acquire knowledge about algorithms, in particular recursive, sorting and searching algorithms, and hash tables; - evaluation of the complexity of algorithms; - to acquire knowledge about data strutures with sequential acess (linked lists, stacks, queues and jumps lists) and non-sequential acess (binary trees). At the end of this curricular unit the student should be able - to solve problems using C and he/she should understand the concepts studied; - to developed skills on using algorithms, particularly in problems involving recursion, 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 idealize, schematize and implement data structures and their algorithms in order to solve problems.
|
Syllabus |
A - Computational Complexity of Algoritms 1. Big-O 2. Amortized analysis B – Data Structures 1. Lists 2. Stacks 3. Queues 4. Binary trees and Binary search trees C – Advanced Trees 1. Balanced binary search trees: AVL and Red-Black 2. 2-3 search trees 3. Interval Trees 4. Heaps: binomial and Fibonacci D - Graphs 1. Types of Graphs 2. Data structures for graph representation 3. Graph search algorithms: Breadth First Search and Depth First Search 4. Graph problems: Minimum Spanning Tree, Shortest Path, Maximum Flow, and Optimal Matching Problems E - Strings 1. String Sets 2. String sorting: Radix Sort 3. String searching: Binary Search 4. Exact sub string matching: Knuth-MorrisPratt and Boyer-Moore 5. Prefix Tree, Suffix Tree, and Suffix Arrays
|
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.
|