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.
Messages
Timetable
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.
Other
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.