Methods of Algorithm Design
Algorithmics is the art of problem solving. We are confronted with it in both our everyday life as well as in the buisness world. Examples include simple navigation problems, automatic filtering of the flood of information in the Internet, or compelx optimization problems in the buisness world. Since this is a key expertise of any computer scientist, this lecture will introduce you to know several standard methods as well as recent research results from different branches like approximation algorithms, online algorithms, as well as randomized and combinatorial algorithms. This includes both a overview of these topics as well as an in-depth study and mathematical analysis of classical and recent algorithmic results.
Further information about the module can be found in STiNE.
- The student slides of the seminar are now available below.
- The tentative seminar programm can be found below.
- The sixth and final exercise sheet is now available, see below.
- There are updated information about the exam and the block seminar, see the corresponding slides below.
- The fifth exercise sheet is now available, see below.
- The fourth exercise sheet is now available, see below.
- Also, concerning the question that arised during the lecture with respect to the claim used to prove Theorem 4: On the board I mistakenly mixed up the direction of the inequality for OPT. We obviously do not need a lower bound on OPT but an upper bound! In Exercise 1 of Sheet 4, where you have to prove that claim, the statement is correct.
- The third exercise sheet is now available, see below.
- The second exercise sheet is now available, see below.
- The lecture starts on Monday, April 1st at 8:15 AM.
- Time & Place:
- Monday, 8:15 AM - 9:45 AM in F-132
- Wednesday, 8:15 AM - 9:45 AM in F-132
- will be discussed during first lecture
If slides are used during the lecture, they will be made available here after the lecture. However, note that most content will be written on the blackboard and will not be available here. So take notes and read the course's accompanying book (see below).
The block seminar is scheduled for August 17th and August 18th (Saturday/Sunday). You can find a tentative schedule in this PDF file. Please note that this schedule might change. So have your talk ready on Saturday, even if your talk is scheduled for Sunday.
The seminar thesis must be submitted until the end of August.
Further information regarding the seminar can be found on the corresponding slides.
All student slides will be available for download after the seminar.
- Presentation 1
- Presentation 2
- Presentation 3
- Presentation 4
- Presentation 5
- Presentation 6
- Presentation 7
- Presentation 8
- Presentation 9
- Presentation 10
- Presentation 11
- Presentation 12
- Presentation 13
There are two blocks for oral examinations:
- Block 1: July 22nd (Monday) to July 26th (Friday)
- Block 2: September 16th (Monday) to September 22th (Friday)
- Assignment of Exam Slots:
- Solved Exercises:
- remember that you must solve at least 40% of all exercises and present at least one solution
- as of 2019-06-24, all "active" students (those who checked at least one exercise on Sheets 3, 4, or 5) fulfill these constraints (but there will be more exercises!)
- if you're unsure, ask me
- Final Registration:
Further information regarding the exam can be found on the corresponding slides.
Exercise sheets appear here approximately every second Wednesday. Exercises must be prepared and are to be presented and discussed by students one week later.
Further information regarding the exercise sheets can be found on the organizational slides.
- Exercise Sheet 1
- Exercise Sheet 2
- Exercise Sheet 3
- Exercise Sheet 4
- Exercise Sheet 5
- Exercise Sheet 6
This course is based on the following books (main literature bold):
- Allan Borodin and Ran El-Yaniv. 1998. Online Computation and Competitive Analysis. Cambridge University Press, New York, NY, USA.
- The Design of Competitive Online Algorithms Via a Primal-Dual Approach. Now publishers Inc.
- Vijay V. Vazirani. 2010. Approximation Algorithms. Springer Publishing Company, Incorporated.