Algorithms and Complexity

Objectives

This course unit aims at preparing students to analyze algorithms (regarding correctness and usage of resources, in particular execution time), as well as to use algorithms over advanced data structures, including graphs. The unit also introduces elementary algorithmic complexity concepts, such as the notion of NP-complete problem. After completing the course students will be capable of

  • Analyzing the correctness of algorithms with respect to logical specifications (contracts), using the notion of loop invariant.
  • Analyzing the asymptotic complexity of an iterative or recursive algorithm.
  • Use the major fundamental algorithmic strategies.
  • Using efficient data structures (AVL trees, hash tables, and heaps) and designing algorithms for them. -Implement graph algorithms.
  • Identifying NP-complete problems.

Program

  1. Introduction to the analysis of program correctness: pre and post-conditions; loop invariants; program annotation.
  2. Execution time analysis: asymptotic complexity model; algorithmic strategies; recurrence equations; best case, worst case, and average case analysis; amortized analysis; case studies.
  3. Efficient data structures: AVL trees, hash tables, heaps. Efficient implementation of buffers and dictionaries.
  4. Fundamental graph algorithms; the greedy and dynamic programming algorithmic strategies.
  5. Introduction to the P, NP, and NP-complete classes of decision problems.

Bibliography

  1. Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, and Clifford Stein. Introduction to Algorithms, Fourth Edition. The MIT Press, 2022.
  2. Donald E. Knuth. The Art of Computer Programming, Volume I: Fundamental Algorithms, 2nd Edition. Addison- Wesley, 1973.
  3. Donald E. Knuth. The Art of Computer Programming, Volume III: Sorting and Searching. Addison-Wesley, 1973.
  4. Donald E. Knuth. The Art of Computer Programming, Volume II: Seminumerical Algorithms, 2nd Edition. Addison- Wesley, 1981.
  5. Robert Sedgewick, Kevin Wayne. Algorithms. Addison-Wesley, 4th edition (March 24, 2011).

Updated: