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 17 and end on December 7, 2017.
  • The exercises will start October 20 (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
17.10.-19.10. Analysis Methods and algorithm design
17.10.2017 Lecture 1: Types of algorithms Reinert
19.10.2017 Lecture 2: Different types of analysis Reinert
20.10.2017 Exercise (no assignments due) Hauswedell
24.10.-02.11. Graph algorithms
24.10.2017 Lecture 3: Shortest paths Bockmayr
26.10.2017 Lecture 4: Maximum flow Bockmayr
27.10.2017 Exercise (theoretical assign. 1) Hauswedell
02.11.2017 Lecture 5: Matching Bockmayr
03.11.2017 Exercise (theoretical assign. 2 + programming assign. 1 due)  Hauswedell
07.11.-23.11. Hashing, Skiplists and tree decomposition
07.11.2017 Lecture 6: Hashing I Reinert
09.11.2017 Lecture 7: Hashing II Reinert
10.11.2017 Exercise (theoretical assign. 3 due) & Review 1 Hauswedell
14.11.2017 Lecture 8: Skiplists I Reinert
16.11.2017 Lecture 9: Skiplists II Reinert
17.11.2017 Exercise (theoretical assign. 4 + programming assign. 2 due)  
21.11.2017 Lecture 10: Tree decomposition I Reinert
23.11.2017 Lecture 11: Tree decomposition II Reinert
24.11.2017 Exercise (theoretical assign. 5 + programming assign. 3 due) Hauswedell
28.11.-07.12. Computability and Complexity
28.11.2017 Lecture 12: Computability I Bockmayr
30.11.2017 Lecture 13: Computability II Bockmayr
01.12.2017 Exercise (theoretical assign. 6 due) & Review 2 Hauswedell
05.12.2017 Lecture 14: Complexity I Bockmayr
07.12.2017 Lecture 15: Complexity II Bockmayr
08.12.2017 Exam  
19.04.2018 2nd Exam  

 

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: