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)(2)
(1) Docente Responsável
(2) Docente que lecciona
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 Algorithms
2. Graphs, Digraphs, and Networks
2.1. Fundamental Definitions and Properties
2.2. Adjacency Matrices and Incidence Matrices
2.3. Connections in Graphs
2.4. The Reachability Problem in Digraphs
2.5. Graph Connectivity
2.6. Eulerian Paths and Eulerian Circuits
2.7. Hamiltonian Paths and Hamiltonian Cycles
2.8. Vertex Coloring
3. Trees and Paths
3.1. Tree Definition and Fundamental Properties
3.2. Spanning Trees
3.3. Binary Trees and Application to Codes
3.4. Minimum-Cost Spanning Trees
3.5. Kruskal's and Prim's Algorithms
3.6. Finding the Minimum-Cost Path in a Network
3.7. Maximum-Flow Problem
3.8. Dijkstra's and Floyd-Warshall's Algorithms
4. Sorting and Search Algorithms
4.1. Problem Statement
4.2. Sorting Algorithms: Linear Insertion, Binary Insertion, Linear Selection, Bubble Sort, and Quick Sort
4.3. Linear Search and Binary Search Algorithms
5. Optimization Models
5.1. Brief Introduction to Operations Research Problems and Concepts
5.2. Problems with Linear Structures: Formulation, Classification, and Geometric Interpretation
5.3. Transportation Problems
5.4. Assignment Problems
6. Introduction to Complexity: Classes P and NP; NP-Complete Problems; Cook's Theorem; Study of Some NP-Complete Problems; Approximation Algorithms for NP-Hard Problems
Evaluation Methodology
Assessment by attendance - A written test, weighing 30%, and a practical assignment, weighing 70%. The final grade for the course is calculated by the weighted average of the grades obtained in the defined assessment components.
The student passes the course and is exempt from an exam, in accordance with the provisions of Points 11 and 12 of Article 11 of the IPT Academic Regulations.
Final assessment - A written exam, weighing 30%, and a practical assignment, weighing 70%. The final grade for the course is calculated by the weighted average of the grades obtained in the defined assessment components.
The student passes the course in accordance with the provisions of Points 11 and 12 of Article 11 of the IPT Academic Regulations.
Students must achieve a minimum grade of 6 in each assessment component.
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
- Júdice, J. e Martins, P. e Pascoal, M. e Santos, J. (2006). Optimização em Redes. Acedido em 29 de setembro de 2023 em https://www.co.it.pt/~judice/Articles/SebOR2006.pdf
- Ramalhete, M. e Guerreiro, J. e Magalhães, A. (1994). Programação Linear. Portugal: Porto Editora
- Stein, C. e H. Cormen, T. e E. Leiserson, C. e L. Rivest, R. (2022). Introduction to Algorithms. (Vol. 1). (pp. 1-1292). USA: The MIT Press; 4th edition
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.
