6 ECTS; 2º Ano, 1º Semestre, 28,0 PL + 28,0 TP + 5,0 OT , Cód. 814333.
Lecturer
- João Manuel Mourão Patrício (1)
(1) Lead Professor
(2) Teaching Professor
Prerequisites
Not applicable.
Objectives
1. Familiarize students with techniques for analyzing and synthesizing algorithms and data structures.
1. Understand the fundamentals of algorithm analysis and synthesis.
2. Analyze the practical implementation of algorithms and data structures.
3. Gain a comprehensive perspective on the applications of algorithms in Computer Science.
Program
1. Introduction to the concept of algorithm
2. Graphs, Directed Graphs and Networks
2.1. Definitions and fundamental properties
2.2. Adjacency matrices and incidence matrices
2.3. Edges in graphs
2.4. The reachability problem in directed graphs
2.5. Connectivity of a graph
2.6. Eulerian paths and Eulerian circuits
2.7. Hamiltonian paths and Hamiltonian cycles
2.8. Vertex colouring
3. Trees and Paths
3.1. Definition of a tree and fundamental properties
3.2. Spanning trees
3.3. Binary trees and their application to coding
3.4. Minimum-cost spanning trees
3.5. Kruskals and Prims algorithms
3.6. Determining the minimum-cost path in a network
3.7. The maximum flow problem
3.8. Dijkstras and Floyd-Warshalls algorithms
4. Sorting and Search Algorithms
4.1. Introduction to the problem
4.2. Sorting algorithms: linear insertion, binary insertion, linear selection, bubble sort and quick sort
4.3. Linear search and binary search algorithms
5. Computational Complexity and Problem Classes
5.1. Formal asymptotic analysis (Big-O, Omega and Theta notation)
5.2. Complexity classes: P, NP, NP-Complete and NP-Hard.
5.3. Polynomial reductions.
5.4. Introduction to approximation algorithms and heuristics
Evaluation Methodology
Continuous assessment A written test, accounting for 30 per cent of the mark, and a practical assignment, accounting for 70 per cent, which must include an oral presentation. The final mark for the course unit is calculated as the weighted average of the marks obtained in the defined assessment components.
The student passes the module and is exempt from the examination, in accordance with the provisions of Points 11 and 12 of Article 11 of the IPT Academic Regulations.
Final assessment A written examination, accounting for 30 per cent, and a practical assignment, accounting for 70 per cent, which must include an oral presentation. The final mark for the course unit is calculated as the weighted average of the marks obtained in the defined assessment components.
Students pass the course unit in accordance with the provisions of Points 11 and 12 of Article 11 of the IPT Academic Regulations.
Students must achieve a minimum mark of 6 in each of the assessment components.
Bibliography
- Ahuja, R. e Magnanti, T. e Orlin, J. (1993). Network Flows: Theory, Algorithms, and Applications. NJ USA: Prentice-Hall
- Balakrishnan, V. (1996). Introductory Discrete Mathematics. New York: Dover
- E. Leiserson, C. e H. Cormen, T. e Stein, C. e L. Rivest, R. (2022). Introduction to Algorithms. USA: The MIT Press; 4th edition
- Stein, C. e Rivest, R. e Leiserson, C. e Cormen, T. (2022). Introduction to Algorithms. New York: MIT Press
Teaching Method
Classes are designed to introduce topics and provide practical examples. Key topics are also explored through exercises and computer-based practical work.
Software used in class
Programming tools; productivity tools; collaborative eLearning platforms.
