Navigation To modulepage
Display language

Advanced Algorithmics

9

English

#40025 / #5

WS 2017/18 - WiSe 2021/22

Fakultät IV

TEL 5-1

Institut für Softwaretechnik und Theoretische Informatik

34351100 FG Algorithmik und Komplexitätstheorie

Niedermeier, Rolf

Niedermeier, Rolf

lehre@akt.tu-berlin.de

POS-Nummer PORD-Nummer Modultitel
170590 33851 Advanced Algorithmics

Learning Outcomes

Students who have completed this module can design and analyze algorithms for computational problems arising in various application contexts. When facing a concrete computational problem, they are able to choose, from a wide range of advanced techniques, a strategy to efficiently solve the problem. This includes strategies for solving problems that are computationally hard in the worst case. In particular, the students know about current research topics in algorithmics.

Content

Introduction to advanced and modern topics of algorithm design and analysis, with a particular emphasis on coping with presumable worst-case intractability. Particular topics include: - algorithmic game theory, - algorithmic graph theory, - approximation and online algorithms, - computational geometry, - computational social choice, - distributed algorithms, - online algorithms, - parameterized and exact algorithms, - randomized algorithms and analysis, - universal solvers.

Module Components

Pflichtgruppe:

All Courses are mandatory.

Course Name Type Number Cycle Language SWS VZ
Advanced Algorithms IV 0434 L 237 WS No information 6

Workload and Credit Points

Advanced Algorithms (IV):

Workload description Multiplier Hours Total
Präsenzzeit 15.0 6.0h 90.0h
Vor-/Nachbereitung 15.0 10.0h 150.0h
240.0h(~8 LP)

Course-independent workload:

Workload description Multiplier Hours Total
Prüfungsvorbereitung 1.0 30.0h 30.0h
30.0h(~1 LP)
The Workload of the module sums up to 270.0 Hours. Therefore the module contains 9 Credits.

Description of Teaching and Learning Methods

The course consists of roughly 2/3 lecture and 1/3 tutorial parts; in the tutorials concrete problems are solved together.

Requirements for participation and examination

Desirable prerequisites for participation in the courses:

a) obligatory: basic knowledge on algorithm design b) desirable: basic understanding of P vs. NP classification

Mandatory requirements for the module test application:

No information

Module completion

Grading

graded

Type of exam

Written exam

Language

English

Duration/Extent

90 min

Duration of the Module

The following number of semesters is estimated for taking and completing the module:
1 Semester.

This module may be commenced in the following semesters:
Wintersemester.

Maximum Number of Participants

This module is not limited to a number of students.

Registration Procedures

Please register at QISPOS or directly at the Examination Office

Recommended reading, Lecture notes

Lecture notes

Availability:  unavailable

Electronical lecture notes

Availability:  available
Additional information:
Slides will be made available during the lecture period

Literature

Recommended literature
*Current research literature specified during the lecture. Basic textbooks:
Cormen, Thomas H.; Stein, Clifford; Leiserson, Charles E.; Rivest, Robert L.: Introduction to Algorithms. 3rd Edition, 2009, The MIT Press
Kleinberg, Jon; Tardos, Éva: Algorithm Design, 2006, Pearson/Addison-Wesley
Niedermeier, Rolf: Invitation To Fixed-Parameter Algorithms. 2006, Oxford University Press
Skiena, Steven S.: The Algorithm Design Manual, 2nd Edition, 2008, Springer Verlag
Williamson, David P.; Shmoys, David B.: The Design Of Approximation Algorithms. 2011, Cambridge University Press

Assigned Degree Programs

This module is used in the following Degree Programs (new System):

Miscellaneous

No information