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.

Times and Places (please see Calendar):
  • 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: