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 2023/24. It is scheduled on Tuesdays at 15:40 in S305 at Malá Strana.

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

  • 3.10.: Introduction, assignments, overview of testing, unit testing, red-black trees
  • 10.10.: Testing data consistency
  • 17.10.: Fuzzy testing
  • 24.10.: More testings: Manually created trees for testing and tree/graph visualization
  • 31.10.: Discussion on implementation of Red-Black trees
  • 7.11.: Goldberg's algorithm: Theory
  • 14.11.: Goldberg's algorithm: Implementation
  • 21.11.: Goldberg's algorithm: Discussion
  • 28.11.: Discussion; Error handling
  • 5.12.: Maximal matching: Theory
  • 12.12.: Maximal matching: Implementation

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.

Examples of tests

Assignments given in other courses may be useful as examples how to write tests. Hint: Use git's history to see assignments in previous years.