1. Home
  2. NOVA School of Science and Technology
  3. Mathematics and Applications
  4. Actuarial Science, Statistics and Operations Research
  5. Design and Analysis of Algorithms

Design and Analysis of Algorithms

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.

General characterization

Code

8154

Credits

6.0

Responsible teacher

Luís Manuel Marques da Costa Caires, Margarida Paula Neves Mamede

Hours

Weekly - 5

Total - 67

Teaching language

Português

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.

Bibliography

Main References

Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, and Clifford Stein. Introduction to Algorithms (3rd ed.). 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 ed.). Addison-Wesley, 2012.

S. Sridhar. Design and Analysis of Algorithms. Oxford University Press, 2014.

Dexter Kozen. The Design and Analysis of Algorithms. Springer, 1992.

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 ed.). Springer, 2008.

Steven S. Skiena and Miguel A. Revilla. Programming Challenges: The Programming Contest Training Manual. Springer, 2003.

Teaching method

There are three hours of lectures and a lab session each week. In the laboratory, students design, analyse and implement algorithms.

Evaluation method

Assessment Components

Assessment has two components: the laboratory component and the theoretical-practical component.

Laboratory Component

The laboratory component comprises three programming projects. Each programming project consists in the design, analysis and implementation of an algorithm for solving a programming contest problem, in the writing of a report and in a discussion. The first two parts (program and report) are done in teams of two students; the discussion is done individually in person. The project grade combines the group grade and the individual grades.

The laboratory component grade (LComp) is the mean of the three project grades (P1, P2 and P3):

LComp = (P1 + P2 + P3) / 3.

In order to succeed (and to have access to the exam), it is required that LComp >= 7.0 .

Discussions occur at the end of the semester, only with students who have done at least two projects.

Theoretical-Practical Component

The theoretical-practical component comprises two tests. If the mean of the test grades is less than 9.5 and LComp >= 7.0, students can do a final exam. The tests and the exam are written, open-book, and done individually in person (except the first test, which is an online test).

The theoretical-practical component grade (TPComp) is the mean of the test grades (T1 and T2) or the exam grade (Ex):

TPComp = (T1 + T2) / 2   or   TPComp = Ex.

In order to succeed, it is required that TPComp >= 9.5 .

Final Grade

The final grade (F), defined only if LComp >= 7.0, is:

  • F = TPComp,   if TPComp < 9.5;
  • F = 0.4 LComp + 0.6 TPComp,   if TPComp >= 9.5 .

All grades (P1, P2, P3, T1, T2, Ex, LComp, and TPComp) are rounded to the nearest tenth, except the final grade (F) which is rounded to the nearest whole number.

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