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.

Enrol
Moodle
Log in to view the registration key for Moodle.

Messages

Juha Kärkkäinen's picture

Juha Kärkkäinen

Published, 7.3.2019 at 19:45

This is a reminder that the presentations for Seminar on Discrete Algorithms begin next Tuesday 12.3. at 12:15. All seminar participants are expected to be present.

Preliminary versions of the presentation slides are available in Moodle. The opponents (Saska for Tuomo and Antti for Massimo) should take a look at them and prepare to ask questions.

Timetable

Upload a preliminary version of your presentation one week before your talk slot (see Moodle for a link to a shared folder). Final version of the presentation can be uploaded closer to the talk.

Presentation schedule:

12.3.

The exponential time hypothesis and lower bounds for polynomial-time problems
Tuomo Lehtonen (opponent Saska Dönges)

SETH lower-bounds on pattern matching
Massimo Equi (opponent Antti Karjalainen)

19.3.

Push-relabel maximum flow algorithms
Risto Haapasalmi (opponent Massimo Equi)

Hash array mapped trie
Juhana Laurinharju (opponent Tuomo Lehtonen)

26.3.

Planning in POMDPs by SAT
Ivan Kropotov (opponent Risto Haapasalmi)

Computational mathematics: determining Schur Number Five using SAT solvers
Miika Leinonen (opponent Juhana Laurinharju)

2.4.

Cache-oblivious string search
Saska Dönges (opponent Miika Leinonen)

Interior point methods
Antti Karjalainen (opponent Ivan Kropotov)

9.4. No meeting (backup option).

16.4. Deadline for seminar reports. No meeting. You will be assigned reports of two other students for peer-review.

23.4. Easter break

30.4. Deadline for peer-reviewing of seminar reports.

14.5 Deadline for final seminar reports that have been revised based on reviewers' comments.

All the submissions and peer-review are conducted in Moodle.

DateTimeLocation
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

Other teaching

Material

Guidelines for presentation and seminar report are in Moodle. See below a latex template for seminar report. This is the same as for Master's theses, so please adjust appropriately to suite the purpose.

Conduct of the course

The following elements are required:
- Giving a preliminary topic presentation (~5 min) during period III
- Giving a seminar presentation (~40 min) on your topic during period IV
- Acting as an opponent to one other student
- Active participation in the seminar meetings
- Writing a seminar report (~15 pages) on your topic to accompany the presentation
- Peer-reviewing of seminar reports of two other students
- Revising your seminar report based on the reviewers' comments

Grading (at scale 1-5) is based on an overall assessment of all the required components.

Description

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.