Implementation of Algorithms and Data Structures

In this course (NOPT056), 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 will be negotiated; see below.

Schedule

This course was scheduled on Wednesdays from 14:00 at the corridor S301 at Mala 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.

Plan of the course

  • 17.2.: Introduction, assignments, overview of testing, unit testing, red-black trees
  • 24.2.: Introduction for new students, representation of binary trees
  • 2.3.: Testing data representation, testing using larger amount of data, data visualization
  • 9.3.: Fuzz testing
  • 16.3.: Manually created data in memory, discussions
  • 23.3.: Goldberg algorithm: theory
  • 30.3.: Goldberg algorithm: implementation
  • 7.4.: Cancelled
  • 14.4.: Intrusive linked list, exception handling, discussions
  • 21.4.: Discussions
  • 28.4.: Maximum matching algorithm: theory
  • 4.5.: Maximum matching algorithm: implementation
  • 11.5.: Cancelled
  • 18.5.: Discussions, details of implementation the Maximum matching algorithm

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.