There are no seminars after week 8. Use the extra time for example for projects of finishing of homework.

8th Week – Python Bindings & Lua Interpreter

Download the zip file

This task consists of two independent parts. In the first one, you will create Python bindings for a simple graph library written in C++. In the second part you will implement game of life in such a way, that the user interface and core of the game is implemented in C++, but the app is scriptable via Lua.

Do not get scared, there is not much code you have to write.

Python Bindings

In this part of the exercise you will try to implement Python bindings for a really simple graph library. This whole exercise is located in the python-bindings directory.

You can find the library in the file graph.hpp. The graph is represented by an adjacency list in each vector. The Node class is parametrized by the type of data associated with nodes and edges. The Graph class provides a method for adding new vertices and it allows to walk the graph in DFS manner. When a vertex is visited or left, a user provided callback is called.

The demo is compiled using CMake. Simply run the following command to compile it:

mkdir -p build
cd build
cmake ..
make -j8

Note that the cmake .. might take a while to complete since the pybind11 dependency is downloaded (and FetchContent doesn’t show progress bar).

To execute the Python demo, just run:

PYTHONPATH=path_to_your_build_directory python3

The goal is to basically make executable by implementing python bindings for the library.

First, create Python classes PlainGraph and PlainNode mapping to Graph< std::string, Nothing > and Graph< std::string, Nothing >::NodeT respectively. The user should be able to create a graph, add nodes and add neighbors. Also, they should be able to walk the graph by supplying arbitrary Python functions as callbacks.

Second, try to implement the Python classes Graph and Node. These should represent a graph where vertex and edge data can be arbitrary Python values.

Some tips

Game of Life with Lua

Your goal for this exercise is to practice writing Lua bindings in C++. You will create a working Game of Life that uses Lua scripts for the definition of the initial state of the game and for controlling the game itself. This game is quite simple – just read the wiki: You only have to implement the Lua bindings. GUI and game mechanics are implemented.

You should install the SDL2 GUI library, the project itself is a standard CMake project.

Note: If you get linker errors with undefined references to SDL functions, try changing the target_link_libraries line as suggested in the comment in the CMakeLists.txt. (The problem seems to be version- or platform-dependent.)

Execute the game as:

./game_of_life test.lua

Existing code

window.hpp contains cell_state and game_window types. cell_state is an enum that represents the state the cells can be in - ALIVE or DEAD. game_window is a GUI that you will use for visualization of the game. This window can initialize itself and provides you with game_window::cell_matrix type. You should use the cell_matrix type as storage for the actual state of the game. If you want to visualize the cell_matrix just use method form the GUI window: game_window::draw_cell_matrix.

main.cpp contains two functions that represent the mechanics of the game. liveness counts living cells around a specific cell in the matrix. gol_iterate executes one iteration of GoL over the provided matrix and returns a new matrix.

The idea is to iteratively update the game state and draw it.

What you should implement

You have a GUI window to visualize the game and functions for game mechanics. You have to fill in the lua bindings.

The file test.lua is a simple example file that initializes the basic GoL game and executes it. The binding expects that there is only one cell-matrix in the app. For the Lua script, we only use numbers for setting the cell state – 1 means alive, 0 means dead.

Your list of tasks for the bindings is to introduce the following items into the Lua context; these are used by the script provided in this exercise: * variables width and height: the actual dimensions of cell-matrix (The API uses the term global for variables that are accessible from the top level of Lua scripts.) * function set: takes three arguments as input – x and y coordinates and state of cell – and sets the state of the cell at the internal matrix at the coordinates * function get: takes two arguments as input – x and y, returns the state of the cell in the internal matrix * function gol_iterate: executes one iteration of GoL over the internal matrix * function draw: draws the actual state of the cell-matrix in the GUI window * function sleep: allows the app to sleep for 100ms (tip: SDL_Delay)

You should also implement the part of the code that loads the file provided as an argument to the binary and executes it. The simple implementation uses global variables, you have more instructions for avoiding them in the sources zip file.


And one last thing: share your custom Lua scripts!


The solutions are available.

7th Week – Threading

Threads in GDB quick guide

Parallel queue

Your task this week is to implement a simple thread-safe queue and in doing so get familiar with the basic synchronization primitives from the C++ standard library.

Basic task

Implement class Queue< T > as thread-safe wrapper for std::deque using mutexes and condition variables. It should support following operations:

Write also a simple multi-threaded program which tests the capabilities of your queue (multiple readers/writers). Before you start, it might be useful to read the relevant parts of cppreference.

Bonus task

When using blocking operations (such as pop) it is often useful to be able to interrupt blocked threads. Add a support for queue shutdown:

Please note that the notion of “future” is somewhat vague in parallel programming. E.g. it is admissible that a pop which is executed in parallel with kill will return a value if the queue is not empty and it is also admissible it will throw an exception. It is, however, not admissible it will block.


The solution is available.

6th Week

There are two tasks for this week both of them concerning templates and possibly concepts:

Both of these can make use of concepts, but can be also solved without them. Concept-based solution will probably be shorter and easier to read. If you decide to use concepts, it would be a good idea to refresh your knowledge of requires expressions and on Lecture 2.

Furthermore, you are encouraged to read lecture codes and ask if anything is not clear to you.

Pretty Printer

Write an overloaded function (e.g. format) which is capable of pretty-printing values of different types. It is best to use helper class (e.g. Formatter which has overload member function format and serializes the output to std::stringstream. This class can then be used in format). The advantage of this approach is that member functions can be mutually recursive without needing declarations before use.

Auto-Deriving operator +

Download the zip file It contains implementation of Eq and Ord SFINAE helpers as shown in the lecture as well as concept-based alternatives.


The solution is available.

5th Week

Download the zip file As there are no dependencies this week, we do not provide CMake build file.



In ast.h you are provided with basic interface of part of AST (abstrax syntax tree) implementation which represents nodes for constants and binary operators. Once expression over such nodes is created (see ast.cpp for example) many operations can be done with it, for example it can be printed, or it can evaluated.

Your task is to create printer and evaluator which walk through the AST and perform given operation, try to use different techniques:


The solution is available:

4th Week

Download the zip file There are two exercises in this week, one on iterators and one or ranges. We recommend you do both of them, but they might be longer than two hours together. If you are not familiar with implementation of iterators, you should definitely do the iterators exercise.


The first assignment is to write forward iterators for given implementation of block linked list (a linked list which allocates several items in each node to achieve better compromise between iteration speed and insertion speed).


For the ranges, you are given several smaller tasks to familiarize with the area. Currently, this task requires GCC 10, use the one on Aisa if you don’t have your own.

Since the documentation is not particularly easy to read, we give you some useful points here:


You will find outline for these tasks in the zip file for this exercise. You will also find a basic tests for them there. To simplify the examples, we write ranges and tuples into curly brackets and we write ranges of characters using the string literal notation even if they are not actually strings.

  1. getLonger(range, length) – takes a range of sized ranges and returns a range of those sized ranges that are longer than given length.

    getLonger({ "hi", "ahoj", "hello"}, 3) ⇝ { "ahoj", "hello" }
    getLonger({ { 1, 2, 3 }, { 1 }, { } }, 2) ⇝ { { 1, 2, 3 } }
  2. summarizePassing(range, limit) – takes a range of pairs (name, points) and a minimum needed to pass a course and produces a range of strings of form “name: points pts” for students that have at least limit points.

    summarizePassing({ { "A", 42 }, { "B", 1 }, { "C", 25 } }, 25)
        ⇝ { "A: 42 pts", "C: 25 pts" }

    Hint: you can use std::to_string to convert number to string.

  3. everyNth( range, n ) – takes a range and a positive number and returns a range that contains every n-th element of the input range (starting with the first).

    everyNth("hello", 2) ⇝ "hlo"
    everyNth({ 0, 1, 2, 3, 4, 5, 6 }, 3) ⇝ { 0, 3, 6 }
  4. diagSeq() – returns an infinite range that is result of concatenations of sequences [0], [0, 1], [0, 1, 2], …

    diagSeq() | take(11) ⇝ { 0, 0, 1, 0, 1, 2, 0, 1, 2, 3, 0 }
  5. diagSums() – returns an infinite range of sums of diagSeq(). I.e., the n-th element of the result contains sum of elements 0…n for diagSeq.

    diagSums() | take(11) ⇝ { 0, 0, 1, 1, 2, 4, 4, 5, 7, 10, 10 }


Commented solutions are available.

3rd Week


The solutions are available.

2nd Week – Concepts, C++17 Library additions

Download the zip file The zip contains source files and CMake build file. If you don’t want to use CMake you will need to get Catch2 manually.

ArraySet with Concepts

Your first task it to implement missing parts of an ArraySet – a data structure that stores a (sorted) set in an array. This data structure is well suited for cases when we want to check if an element is in a set much more often than insert a new one or in cases where the set size is small.

This task uses C++20 concepts. It is tested to work both in g++ 10 and clang 10, but if you have older GCC/clang it will not work. If you have MS Visual C++, it might work, but we have not tested it. If your compiler does not work with the concepts you need, please use GCC 10 on Aisa.

Your tasks is to fill-in blanks in the implementation – construction, search and insertion. Furthermore, you are expected to add use of concepts to the ArraySet. ArraySet should have one template argument: ArraySet<T> in a manner similar to std::set<T> (except we have dropped the allocator and comparator part). Unlike std::set, ArraySet should use concepts to check that its type argument is actually usable – it is a comparable type and it is also movable and move constructible (so it can be stored in a vector). We have not yet covered move semantics – for now it is sufficient to say that movable and move constructible are weaker constraints then copyable and copy constructible and therefore any object that can be copied can be also moved (just possibly not very efficiently).

All the places you should fill in are marked in the source code. We recommend you have a look at the <concepts> header.

There are some simple unit tests available for this task, you can run them by make arrayset-run-test if you use our CMake.

RPN Calculator with std::variant and std::optional

In this exercise we will create a modular calculator using the Reverse Polish notation (RPN). The RPN expressions contain numbers and operators in postfix form. We will be writing them into a brace-enclosed list, for example { 3, 2, "-" } represents a mathematical expression 3 − 2 and { 3, 2, "-", 4, "+" } represents (3 − 2) + 4. Please note that RPN does not need brackets.

In C++ we can represent RPN expressions using a vector of variants, where each variant can contain either a number or a string (long or std::string_view in our implementation.). To make the program more compact, we create a type alias for such a vector: rpn::program.

We want to create an evaluator for such expressions – rpn::calculator. Furthermore, we want this evaluator to be modular, i.e., to support addition of operations. To do so, we define a virtual base class rpn::base_op and derive various operations from it (see the source). These operations can be registered using rpn::calculator::register_op.

RPN calculation can be done using a stack – we go over the input program (left to right) and every time we see a number, we push it to the stack. Every time we see an operation, we perform it (removing its arguments from stack) and push it results to the stack. If an operation uses more than one argument, we need to apply the arguments in the right order – the argument on the top of the stack is the rightmost argument of the operation. Let’s have an example: we use program { 3, 2, "-", 4, "+" }:

  1. push 3 to the stack: [3] (stack is in square brackets with top on the right)
  2. push 2 to the stack: [3, 2]
  3. apply on the stack: 3 − 2 ≡ 1, so stack is now [1]
  4. push 4 to the stack: [1, 4]
  5. apply + on the stack: 1 + 4 ≡ 5, so stack is now [4]

The top (rightmost) element of the stack at the end of the computation is its result.

Your task is to implement the missing functionality in the rpn::calculator. The parts you should implement are marked with TODO. The source also specifies in comments what these parts should do. The rest of the file is also commented.

There are some simple unit tests available for this task, you can run them by make rpn-run-test if you use our CMake. You can also look at the tests for examples of use of our calculator.


The solutions are available.

1st Week – CMake, Code analysis, Debugging

CMake Basics

Look at CMakeLists.txt in the aforementioned zip, particularly its usage part for now. This file it is a CMake build description for fixthis.cpp. Use CMake to build the fixthis target in a separate build dir. Then use CMake to build fixthis with an address sanitizer.

Code Analysis, Debugging

  1. Look at fixthis.cpp and try fixing all the problems you can find. Use relevant tools such as clang-tidy, valgrind, and sanitizers.

    • Compile without optimizations and with the -g (debug info) flag for best reports from sanitizers and valgrind. (When using cmake both of these conditions are ensured by using the CMAKE_BUILD_TYPE=Debug setting.)
    • Do not use valgrind on programs compiled with sanitizers (it will eat all memory).
  2. Look at the files problem{1..7}.cpp. Each of these files contains a specific error that can easily occur in C++ programs (cases 6 and 7 are simplified versions of errors from production code). Sometimes the error can be a crash, sometimes it can mean the program behaves differently than one would expect from the code (the intention can be also marked in the names of functions!).

    • Use compiler, clang-tidy, debugger, valgrind or code inspection, or any other tool you fancy to uncover the error.
    • You do not need to fix these errors, some of them cannot be fixed without a rewrite which is impossible for the abstracted cases presented here.
    • Please note that problem7.cpp expects to be run in the directory where its source code resides.

Extra: Revision, More CMake

If you want more, or if you are not sure about your C++ skills, do also the following tasks.

  1. Implement a doubly-linked list using the template given in linkedlist.h. Write your own test for this implementation using Catch2. Some tests are provided in linkedlist.cpp (but write your own first).
  2. Write a CMake build file for the linked list exercise (or some other simple C++ program)
    • use the CMakeLists.txt from the first task as a basis;
    • use the CMake documentation if needed.


The solutions are available. Each of the problem{1..7}.cpp codes has a corresponding solution file which comments the problem.

  1. In fact, if you are calling the view using the std::view::X path, you are not calling a constructor directly, but instead calling it through a helper object.↩︎