Implementation of Algorithms and Data Structures

In this course (NTIN106), we discuss how to implement advanced algorithms and data structures without tedious debugging. We practically use these methods on four algorithms or data structures. The course will be in English or Czech language depending on students' preferences.

Schedule

This course will be in the winter semester 2022/23. Schedule will be negotiated; please write me your time preferences.

Conditions to pass the course

Students are expected to implement the following algorithms or data structures:
  • Red-black trees
  • Goldberg algorithm for the network flow problem
  • Blossom algorithm for the maximal matching problem in general graphs
All students are asked to enroll into my group in ReCodEx for homework submissions.

Past seminars

Literature

  • Mareš, Martin, and Tomáš Valla. Průvodce labyrintem algoritmů. CZ. NIC, zspo, 2017.
  • Cunningham, William J. Cook William H., and William R. Pulleyblank Alexander Schrijver. Combinatorial Optimization. John Wiley \& Sons. 1997
  • Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest and Clifford Stein: Introduction to algorithms, The MIT Press, 2001 Chapter on network flows
  • Robert Sedgewick: Left-leaning Red-Black Trees, doi:10.1.1.139.282
  • Ammann, Paul, and Jeff Offutt. Introduction to software testing. Cambridge University Press, 2016.