Kaisa_2012_3_photo by Veikko Somerpuro

In brief

Interested in algorithm design & analysis, constraints & optimization, or string processing & sequence analysis?

This is an MSc level seminar in the general area of discrete algorithms, giving students a wide range of topics to choose from according to their own interests. Tentative list of topics for seminar work is given below. You can also propose your own topic.

Algorithm design & analysis:
Push-Relabel Maximum Flow Algorithm, Approximation Algorithms for Metric {s,t}-Path TSP, Amortized analysis of disjoint-set forest (union-find data structure), TimSort, Dynamic Trees with Almost-Optimal Access Cost, Multiple-Choice Knapsack for Assigning Partial Atomic Charges in Drug-Like Molecules

Constraints & optimization:
Local search for bit-precise reasoning, Computational mathematics: determining Schur Number Five using SAT solvers, Using linear programming relaxations to design approximation algorithms, Parameterized algorithms / parameterized complexity of reasoning, Constraint acquisition, The stable matching problem with couples, Knowledge compilation: sentential decision diagrams, Model counting, Constraint integer programming, The exponential time hypothesis and lower bounds for polynomial-time problems

String processing & Sequence analysis:
Cache-oblivious string search, Compressed text indexing, Minimizers, Bloom filters & de Bruijn graphs, Compression & colored/weighted de Bruijn graphs, Indexes on Alignments, Indexes on graphs, Alignments on graphs, Seth lower-bounds on pattern matching (reserved), 2 ECTS projects on suffix sorting and on bitparallel algorithms

See Materials section for references related to these topics.

Log in to view the registration key for Moodle.


See Materials / Topics for the schedule.

Tue 15.1.2019
12:15 - 14:00
Tue 22.1.2019
12:15 - 14:00
Tue 29.1.2019
12:15 - 14:00
Tue 5.2.2019
12:15 - 14:00
Tue 12.2.2019
12:15 - 14:00
Tue 19.2.2019
12:15 - 14:00
Tue 26.2.2019
12:15 - 14:00
Tue 12.3.2019
12:15 - 14:00
Tue 19.3.2019
12:15 - 14:00
Tue 26.3.2019
12:15 - 14:00
Tue 2.4.2019
12:15 - 14:00
Tue 9.4.2019
12:15 - 14:00
Tue 16.4.2019
12:15 - 14:00
Tue 23.4.2019
12:15 - 14:00
Tue 30.4.2019
12:15 - 14:00

Other teaching


Contact the organizers if you want to reserve a topic.



Master's Programme in Computer Science is responsible for the course

  • Discrete Algorithms course package CSM12100
  • Module in Discrete Algorithms CSM22100
  • Algorithmic bioinformatics LSI310

The course is available to students from other degree programmes, especially from the Life Science informatics / Algorithmic Bioinformatics study track

The topics of the course are related to recently lectured courses in discrete algorithms. One should have taken at least one earlier discrete algorithms course to attend the research seminar.

To continue with a Master's thesis in computer science related to the topic of the seminar.

Academic writing courses

An ability to give scientific presentations. An ability to peer-review and give feedback on written work and on presentations. Improved scientific writing skills on discrete algorithms topics. In-depth theoretical understanding of an advanced topic in discrete algorithms and/or experience in implementing and experimentally evaluating an advanced discrete algorithm.

After or during a course covering discrete algorithms topics.

The course is offered annually in the Spring term.

The topics of the course are related to recently lectured courses in discrete algorithms.

Grading is 1..5. Presentation and written work of the seminar part are evaluated with a common grade. The 2-cr project part can be evaluated also as pass/fail.

The final grade is a weighted average of the parts.

The course is separated into a 3-cr seminar part and a 2-cr implementation project part, which can be taken independently. The seminar part includes a presentation and written work. The project is an implementation of an algorithm and its evaluation, reported as a (poster) presentation and short report.