Display language

#40025 / #5

WS 2017/18 - WiSe 2021/22

English

Advanced Algorithmics

9

Niedermeier, Rolf

benotet

Schriftliche Prüfung

Zugehörigkeit


Fakultät IV

Institut für Softwaretechnik und Theoretische Informatik

34351100 FG Algorithmik und Komplexitätstheorie

No information

Kontakt


TEL 5-1

Nichterlein, André

lehre@akt.tu-berlin.de

PORD-Nr.ModultitelLPBenotungPrüfungsformPNr. (POS)Modulprüfung PORDModulprüfung PNr.
33851

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 NameTypeNumberCycleLanguageSWSVZ
Advanced AlgorithmsIV0434 L 237WSNo information6

Workload and Credit Points

Advanced Algorithms (IV):

Workload descriptionMultiplierHoursTotal
240.0h(~8 LP)
Präsenzzeit15.06.0h90.0h
Vor-/Nachbereitung15.010.0h150.0h

Course-independent workload:

Workload descriptionMultiplierHoursTotal
30.0h(~1 LP)
Prüfungsvorbereitung1.030.0h30.0h
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):

Studiengang / StuPOStuPOsVerwendungenErste VerwendungLetzte Verwendung
This module is not used in any degree program.

Miscellaneous

No information