Design and Analysis of Algorithms (2017/2018) - Departamento de Informática

Additional information: https://moodle.fct.unl.pt/course/view.php?id=4941

Description

Study of efficient algorithms for solving fundamental graph problems.

Use of three algorithm design techniques (greedy strategies, dynamic programming and transform-and-conquer).

Understanding of the basic concepts of the Theory of Complexity.

Objectives

Knowledge

Define and identify three algorithm design techniques: greedy strategies, dynamic programming and transform-and-conquer.

Know the fundamental graph algorithms, the required abstract data types and the data structures used to implement them efficiently.

Understand amortized analysis.

Define some complexity classes and understand some open problems.

Application

Design and analyse a dynamic programming algorithm.

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.

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.

Make NP-complete proofs.

Syllabus

(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 sorting.

(4) Minimum spanning trees. Kruskal’s algorithm. The disjoint sets abstract data type.

(5) Amortized analysis. The potential method.

(6) Prim’s algorithm. The adaptable priority queue abstract data type.

(7) Shortest paths. The algorithms of Dijkstra, Bellman-Ford, and Floyd-Warshall.

(8) Flow networks. Maximum flows. The Ford-Fulkerson method. The Edmonds-Karp algorithm. Maximum bipartite matchings. Minimum cuts.

(9) Introduction to the Theory of Complexity. The classes P, NP, PSPACE, and EXPTIME. The suffixes hard and complete. Problem reductions. Some open problems.

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

Michael R. Garey and David S. Johnson. Computers and Intractability: A Guide to the Theory of NP-Completeness. W. H. Freeman and Company, 1979.

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.

Prerequisites

Students should:

(a) be proficient in object-oriented programming;

(b) be familiar with the fundamental data structures (linked lists, hash tables, binary search trees, binary heaps);

(c) be able to calculate the time and the space complexities of algorithms.

Student work
  Hours per credit 28
  Hours per week Weeks Hours
Aulas práticas e laboratoriais   26.0
Aulas teóricas   39.0
Avaliação   5.0
Self study   60.0
Others   2.0
Project   36.0
Total hours 168
ECTS 6.0