Jaak Vilo, Kallol Roy
Algorithmics (MTAT.03.238) is an obligatory course in the Computer Science MSc curriculum. As such it is intended to remind everyone of the foundations of algorithms and data structures but also to go beyond and teach some more advanced concepts (like succinct data structures, for example).
The course aims at linking different aspects into a more coherent understanding of how various concepts are linked. Secondly, it aims not just to enhance knowledge and understanding but also to practice programming skills by encouraging self-implementations. The course provides modelling of computational problems and covers basic algorithms, algorithmic paradigms and data structures. Our course emphasizes the intricate relationship between algorithms and programming through the basic performance measures of complexity. The overall goal we aim to achieve is to broaden the understanding of the students in order to feel confident to write programs that allow them to accomplish goals.
Along with programming the course also has the task of writing homework reports and an overview of some single novel research paper by preparing a 2-page summary of it. This prepares our students to write their theses or papers for future conferences.
With the exam, we have experimented for the last three years with an exam performed fully at home, at students’ own pace. Exams have to be performed individually. While it is hard to ensure no collaboration ever happens, the focus is on trust and hope that every student studies for their own benefit. Some of the feedback is generally given at the end of the exam.
An absolute high point of the course is the presentation of projects at the end of the course. Projects are usually performed in small teams of 2-3 people, but occasionally one-person projects or even 4 can participate. Thus it is hard to assess the contribution of each person, yet groups should in general achieve more. Final end product of a project has in the past been presented as a report or slide deck. But over the last few years, the course has settled to the format of a poster and an interactive poster session. Then everybody has a chance to speak intensively as well as look at other students’ results.
This year some of the projects that might be interesting to fellow students are:
Game Entropy – Herman Rull and Daniel Würsch challenged other students to play against their code which can be played at https://kodu.ut.ee/~herman99/entropy/ (GitHub). This is a game proposed for the programming contest CodeCup 2023.
Eduard Rudi, Karl-Johan Pilve and Kaspar Kadalipp wrote a comparison of algorithms for Poddavki (Äraandmine in Estonian; also known as Giveaway checkers, Suicide checkers, Anti-checkers or Losing draughts; see Wikipedia). The project and game playing algorithms are available from GitHub.
Popular word games (Wordle, Scrabble) are conquering the world. But different languages may require different setups. Martin Vainikko calculated a suitable configuration of Boggle for Estonian and wrote a solver for that. I wonder if the game could now be actually produced and sold for the Estonian market that by definition is very small compared to large languages.
Rasmus Lellep and Joshua Katigbak tackled the full Rubik’s cube – this is clearly so much harder than a 2x2x2 (Pocket) cube that was fully solved by ca half of students during the home exam. In the project, 6 first layers were achieved. The main challenge is how to encode each of the 43,252,003,274,489,856,000 theoretical states the cube can be in (compared to some 3.6M for a Pocket cube). Even if there is a single bit used to record whether the state has been observed before or not, that would require over 5 Exabytes of total memory.
As always, shortest path algorithms, those used in GPS and maps navigation systems are interesting. One project by Kyrylo Riazantsev and Ralf Tambets looked at those methods and validated on Tartu open street maps (project home).
Anton Slavin generated music from random inputs by applying genetic algorithms to convert that random piece as much towards “looking like music” as possible. Code and examples – https://github.com/tonysln/music-gen
Donatas Vaiciukevičius, Dzvenymyra-Marta Yaris and Nikita Fordui did some good old fashioned ASCII art generation but used genetic algorithms for that. The project is available on GitHub.
Kermo Saarse and Taras Ivantsiv provided different algorithms to generate perfect mazes: github.com/kermo-git/MazeAlgorithms
Figure: Tartu Town hall was created as ASCII art using genetic algorithms.
