Implementation of Algorithms and Data Structures (NTIN106)

Winter semester 2026/27

Overview

In this course we discuss how to implement advanced algorithms and data structures without tedious debugging. We practically use these methods on four algorithms or data structures.

NoteLanguage

The course will be taught in English or Czech depending on students’ preferences.

Schedule

Day Time Room
Wednesday 17:20 S11

Conditions to pass the course

Given programming assignments (without LLM, submit on ReCodEx)

  • invariants of an AVL tree (10 points)
  • Correctness of a solution for the shortest path problem (10 points)
  • Testing intermediate states in quicksort (10 points)
  • Red-black trees (30 points)
  • Goldberg’s algorithm for the network flow problem (30 points)

Project and presentation (10–30 points, with LLM)

  • Implement and compare some algorithms or data structures
  • Teaching materials for other courses (e.g. assignments, study materials)
  • Other related topics (discuss with the teacher)

Passing conditions: at least 100 points in total.

Organization

All students are asked to:

  1. enroll into my group in ReCodEx for homework submissions, and
  2. create a private fork of the git repository and give me (login finkj1am) access (role reporter).

Seminars

  1. Introduction (30.9.) slides
  2. Unit tests, testing representation invariants (7.10.) slides
  3. Fuzz testing, verifying results (14.10.) slides
  4. Testing intermediate states, data visualization (21.10.) slides

Literature

  • M. Mareš, T. Valla. Průvodce labyrintem algoritmů. CZ.NIC, 2017.
  • W. J. Cook, W. H. Cunningham, W. R. Pulleyblank, A. Schrijver. Combinatorial Optimization. John Wiley & Sons, 1997.
  • T. H. Cormen, C. E. Leiserson, R. L. Rivest, C. Stein. Introduction to Algorithms. MIT Press, 2001 — chapter on network flows.
  • R. Sedgewick. Left-leaning Red-Black Trees. doi:10.1.1.139.282
  • P. Ammann, J. Offutt. Introduction to Software Testing. Cambridge University Press, 2016.

Prerequisites

Advanced students of this course may benefit from attending it together with Data Structures I, which recommends this course to students who spend a lot of time debugging their programs.