In this lecture we will introduce concepts and methods of advanced algorithmics relevant to current reseach in bioinformatics. We will discuss Methods for the development and analysis of deterministic and randomised algorithms and foundations of compact data structures. Finally, the lecture will encompass concepts for parallel and vectorized computing. In more detail we will cover:
- Introduction into different kinds of algorithms and analysis methods
- Foundations of compact data structures
- Graph theory and graph algorithms
- Analysis of randomized algorithms and data structures
- Introduction into parallel and vectorized computing
- Concepts, paradigms and frameworks for distributed computing
The lecture will be online in my private room:
https://fu-berlin.webex.com/meet/kreinert
The tutorium will be at:
https://fu-berlin.webex.com/fu-berlin/j.php?MTID=md138b450263c9cc5e31101f05fb47990
You find videos and slides HERE.
| Date | Topic |
|---|---|
| 03.11. | L: Types of algorithms and their analysis I |
| 10.11. | L: Types of algorithms and their analysis I |
| 17.11. | L: Compact data structures: Entropy and Coding |
| 24.11. | L: Compact data structures: Arrays |
| 01.12 | L: Compact data structures: Bitvectors with rank and select I |
| 08.12 | L: Compact data structures: Bitvectors with rank and select II |
| 15.12 | Review I |
| 05.01. | L: Hashing I |
| 12.01. | L: Hashing II |
| 19.01. | L: Graph algorithms : Shortest path |
| 26.01. | L: Graph algorithms : Network flow |
| 02.02. | L: Graph algorithms : Bipartite Matching |
| 09.02 | L: Vectorized and parallel computing I |
| 16.02. | Review II |
| 23.02. | Examination: 16-18, Großer HS A22 |
General notes regarding the exercises:
- to pass the course, you need to pass the exam in the end, and you need to pass the exercises (formal requirement "Aktive Teilnahme")
- to pass the exercises you need to pass the theoretical assignments and the reviews ((a total of 50% of the points)
- if you successfully passed the exercises in a previous semester, i.e. all the requirements, you do not need to take the exercises again (although it is highly recommended)
- however partial results from previous semesters cannot be taken into account, e.g. if you only passed programming but not the review, you need to take programming again, as well.
Theoretical assignments:
- there are assignment sheets with 3-4 tasks each, every week one sheet is due
- I will ask at least two students (not groups) in advance to prepare each task and then explain it during the exercise
- every student will be asked at least once, but most will be asked twice
- failure to present a task more than once means failing the exercises (it's ok if the solution is not perfect, that's why I ask two students, but it should be close)
- assignment sheets are not graded, presentation is the "test"