Goals: Students will gain a deeper understanding for mathematical concepts and methods in advanced algorithmics related to state of the art research in bioinformatics. They will be acquainted with advanced tools for the development and analysis of deterministic and randomized algorithms. They are able to recognize various concepts and to apply the methods of analysis to similar problems.
Contents: This lecture introduces different sorts of algorithms and analysis methods like advanced graph algorithms, the analysis of randomized datastructures, and hashing algorithms.
- The lecture will start on October 16 and end on December 6, 2018.
- The exercises will start October 19 (Please note that the exercises are four hours)
Programming language for the programming exercises is C++ and it must compile on one of the Linux machines at the institute. More details at the first session. If you are not familiar with Linux and/or C++, look into it ASAP!
Schedule:
Date | Lecture | Lecturer |
16.10.-19.10. | Analysis Methods and algorithm design | |
16.10.2018 | Lecture 1: Types of algorithms | Reinert |
18.10.2018 | Lecture 2: Different types of analysis | Reinert |
19.10.2018 | Exercise (no assignments due) | Andreotti |
23.10.-30.11. | Graph algorithms | |
23.10.2018 | Lecture 3: Shortest paths | Bockmayr |
25.10.2018 | Lecture 4: Maximum flow | Bockmayr |
26.10.2018 | Exercise (theoretical assign. 1) | Andreotti |
30.10.2018 | Lecture 5: Matching | Bockmayr |
01.12.-20.11. | Hashing, Skiplists and tree decomposition | |
01.11.2018 | Lecture 6: Hashing I | Reinert |
02.11.2018 | Exercise (theoretical assign. 2 + programming assign. 1 due) | Andreotti |
06.11.2018 | Lecture 7: Hashing II | Reinert |
08.11.2018 | Lecture 8: Skiplists I | Reinert |
09.11.2018 | Exercise (theoretical assign. 3 due) & Review 1 | Andreotti |
13.11.2018 | Lecture 9: Skiplists II | Reinert |
15.11.2018 | Lecture 10: Tree decomposition I | Reinert |
16.11.2018 | Exercise (theoretical assign. 4 + programming assign. 2 due) | Andreotti |
20.11.2018 | Lecture 11: Tree decomposition II | Reinert |
22.11.-07.12. | Computability and Complexity | |
22.11.2018 | Lecture 12: Computability I | Bockmayr |
23.11.2018 | Exercise (theoretical assign. 5 due) | Andreotti |
27.11.2018 | Lecture 13: Computability II | Bockmayr |
29.11.2018 | Lecture 14: Complexity I | Bockmayr |
30.11.2018 | Exercise (theoretical assign. 6 due) & Review 2 | Andreotti |
04.12.2018 | Programming assign. 3 due | Andreotti |
06.12.2018 | Lecture 15: Complexity II / Rehearsal | Bockmayr/Reinert |
07.12.2018 | Exam Time: 12-14 Location: Arnimallee 22 Gr. Hörsaal |
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, the programming assignments and the reviews
- both types of assignments will be available from the assignment field on the left
- 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 six 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 collected/graded, presentation is the "test"
- and the reviews will test the theory, as well, see below
Programming assignments:
- there are three programming assignments, one is due every two weeks
- you get to work on them in groups of three, please sign up to a group ASAP ("Section info" on the left)
- every two weeks I will pick 4-5 groups at the beginning of the exercise whose code I will review with them and who have to present their programming solution to the other students
- failure to present a fully working solution more than once means failing the exercises
- programming assignments are not collected/graded, presentation/code-review is the "test"
- programs need to build with g++ (version 4.9 or newer) on a Linux system and the following flags:
-
g++ -std=c++14 -Werror -Wall -Wextra -DNDEBUG -O3 -pedantic YOURFILE.cpp
Reviews:
- there are two reviews (smaller exams)
- they are graded and you need to reach at least 50% of the combined points to pass the exercises
C++ Resources:
- A good introduction : http://www.cplusplus.com/doc/tutorial/ (read at least the Basics until the first exercise)
- detailed documentation on C++ and the standard library: http://en.cppreference.com/
- Some good links and book recommendations: https://isocpp.org/get-started