Semester  Winter 2019/2020 [ Other terms: · Sommer 17 · Sommer 15 · Sommer 12 · Sommer 09 ] 
Module #  INFALG14 
Event #  INFALG015 , INFALG016 
Programmes  Master Wirtschaftsinformatik, Master InformationsSystemtechnik, Master Informatik 
IBR Group(s)  ALG (Prof. Fekete) 
Type  Vorlesung/Übung 
Lecturer  
Assistants  Phillip Keldenich Wissenschaftlicher Mitarbeiter keldenich[[at]]ibr.cs.tubs.de +49 531 3913112 Room 318 
Hiwi  
Credits  5 
Hours  2+1+1 
Time & Place  Lecture: Tuesdays, 15:0016:30, SN 19.2 
Start  Lecture: October, 29th; Tutorial: November, 13th; Homework Discussion: November, 20th 
Prerequisites  Prerequisites are knowledge of algorithms and data structures, basic graph problems and graph algorithms (e.g., as provided in the lecture "Netzwerkalgorithmen"); basic knowledge from theoretical computer science (NPcompleteness) are helpful, but will definitely be supplemented. 
Certificates  (Homework assignments during the semester, and)* an oral exam at the end. (*=Studienleistung) 
Content  Many interesting and natural algorithmic problems (e.g., the Traveling Salesman Problem) are NPcomplete  hence, we cannot expect to find a "perfect" algorithm that (i) always and (ii) fast finds (iii) an optimal solution. However, hard problems still need to be solved! In this class we consider algorithms that do not necessarily find an optimal solution, but that (i) always and (ii) fast find a (iii) provably good solution. Among the topics of this class are:

General Information
Video recordingsThe lectures are videotaped; videos will typically be published on this website the day after the lecture. The video is available as h264encoded mp4 that should be supported by any reasonable video player, and a newer, better and smaller h265encoded mkv which requires a relatively recent video player. A note for Firefox users: Some versions of Firefox do not support playback of sound in the video due to the channel layout; if you do not have sound in the browser, just download the video and use a regular video player such as VLC or mplayer.
Homework SetsThere will be biweekly mandatory homework, which will typically be released on wednesdays. LiteratureThe first part of the lecture will be on basic results for which the following books can be useful.
The second part of the lecture will be on recent results for which the corresponding papers will be announced in due time. Mailing ListThere will be a mailing list. We will distribute the homework sets and other announcements via this list, so, please subscribe! You may also want to check out the algstuds mailing list which is similiar to csstuds but for algorithmic students. 