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 2024/25. The schedule of the course will be negotiated by emails, so students are ask to send me their time preferences.

Conditions to pass the course

Students are expected to write tests for three small assignments and then implement one advanced algorithm and one data structure.
  • Consistency of an AVL tree
  • Correctness of a solution for the shortest path problem
  • Feasibility of a solution for a routing problem
  • Red-black trees
  • Goldberg algorithm for the network flow problem
Advanced students can also try to implement Blossom algorithm for the maximal matching problem in general graphs. All students are asked to
  • enroll into my group in ReCodEx for homework submissions, and
  • create a private fork of git repository and give me (login finkj1am) access (role reporter).

Past seminars

  • 2.10.: Introduction, assignments, overview of testing, unit testing, testing consistency of stored data
  • 9.10.: Creating data in memory, visualize trees and graphs
  • 15.10.: Fuzzy testing, verifying correctness of a solution
  • 22.10.: Verifying intermediate results
  • 29.10.: Verifying randomized algorithms
  • 5.11.: Recursion
  • 12.11.: Goldberg algorithm: Theory and invariants for testing

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.