You need to activate javascript for this site.
Menu Conteúdo Rodapé
  1. Home
  2. Courses
  3. Bioengineering
  4. Algorithms and Data Structures

Algorithms and Data Structures

Code 9102
Year 2
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 - Abstract Data Structures
1. Simple links lists
2. Stacks
3. Queues
4. Binary trees
5. Binary search trees
C – Balanced binary search tree
1. Binary insertion
2. Adelson-Velskii Landis (AVL)
3. Red-Black
D - Balanced search tree
1. 2-3 tree
2. Interval tree
E - Priority queue (Heap)
1. Binary heap
2. Binomial heap
3. Fibonacci heap
F - 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
G - 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 Main:
- "Estruturas de Dados e Algoritmos em C", Tecnologias de Informação, António Manuel Adrego da Rocha, FCA - Editora Informática, 2008
- "Linguagem C", Luís Damas, FCA - Editora de Informática, 1999
Complementary:
- "Algorithms in C, Parts 1-5 (Bundle): Fundamentals, Data Structures, Sorting, Searching, and Graph Algorithms", By Robert Sedgewick, Addison-Wesley Professional; 3rd Edition, 2001
- "Elementos de Programação com C", 3ª Edição Actualizada e Aumentada, Pedro Guerreiro, FCA - Editora Informática, 2006
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.
Last updated on: 2021-06-13

The cookies used in this website do not collect personal information that helps to identify you. By continuing you agree to the cookie policy.