Design and Analysis of Algorithms
Code
8154
Academic unit
Faculdade de Ciências e Tecnologia
Department
Departamento de Informática
Credits
6.0
Teacher in charge
Luís Manuel Marques da Costa Caires, Margarida Paula Neves Mamede
Weekly hours
4
Total hours
57
Teaching language
Português
Objectives
Knowledge
Know the fundamental graph algorithms, the required abstract data types and the data structures used to implement them efficiently.
Define and identify three algorithm design techniques: dynamic programming, greedy strategies, and transform-and-conquer.
Understand amortized analysis.
Application
Formulate a clean graph problem from a real-world problem and adapt a classical algorithm to solve it.
Choose, compare, adapt, and use suitable data structures for a given problem.
Design and analyse a dynamic programming algorithm.
Calculate the running time of an algorithm based on the amortized running times of the inner functions and perform their amortized analysis.
Evaluate solutions and justify choices.
Prerequisites
Students should have completed the following units:
- Introduction to Programming (Introdução à Programação);
- Object-Oriented Programming (Programação Orientada pelos Objectos);
- Discrete Mathematics (Matemática Discreta);
- Algorithms and Data Structures (Algoritmos e Estruturas de Dados).
Subject matter
(1) Dynamic programming.
(2) Introduction to the study of graphs. Fundamental definitions. The abstract data types undirected graph and directed graph. Implementations of graphs.
(3) Elementary graph algorithms. Depth-first and breadth-first traversals. Topological sort. Test for acyclicity.
(4) Minimum spanning trees. Kruskal’s algorithm. The disjoint sets abstract data type.
(5) Prim’s algorithm. The adaptable priority queue abstract data type.
(6) Shortest paths. The algorithms of Dijkstra and Bellman-Ford.
(7) Maximum flows. The Ford-Fulkerson method. The Edmonds-Karp algorithm. Maximum bipartite matchings. Minimum cuts.
(8) Amortized analysis. The potential method.
Bibliography
Main References
Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, and Clifford Stein. Introduction to Algorithms (3rd edition). The MIT Press, 2009.
Jon Kleinberg and Éva Tardos. Algorithm Design. Addison-Wesley, 2005.
Complementary References
Anany Levitin. Introduction to The Design and Analysis of Algorithms (3rd edition). Addison-Wesley, 2011
Steven S. Skiena. The Algorithm Design Manual (2nd edition). Springer, 2008.
Steven S. Skiena and Miguel A. Revilla. Programming Challenges: The Programming Contest Training Manual. Springer, 2003.
Teaching method
There are two hours of lectures and a lab session each week. In the laboratory, students design, analyse and implement algorithms.