Moses - Advanced Algorithmics

Display language

Diese Modulbeschreibung gilt nicht im aktuellen Semester.

Die Modulbeschreibung gilt nur für den Zeitraum WS 2014/15 - SS 2015. Die Version für das aktuelle Semester (SoSe 2024) finden Sie hier: Modulbeschreibung des SoSe 2024

Module / Version:
#40025 / #1

Validity:
WS 2014/15 - SS 2015

Default display language:
English

Module title:
Advanced Algorithmics

Credits:
9

Responsible person:
Niedermeier, Rolf

Grading:
benotet

Type of exam:
Mündliche Prüfung

Zugehörigkeit

Faculty:
Fakultät IV

Institute:
Institut für Softwaretechnik und Theoretische Informatik

Area of expertise:
34351100 FG Algorithmik und Komplexitätstheorie

Prüfungsausschuss:
No information

Kontakt

Office:
TEL 5-1

Contact person:
Nichterlein, André

E-mail address:
lehre@akt.tu-berlin.de

Website:

http://www.akt.tu-berlin.de/menue/teaching/

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 techniques, a solution strategy to efficiently solve the problem. This includes in particular strategies for solving problems that are computationally hard in the worst case. The course is principally designed to impart: technical skills 40%, method skills 50%, system skills 10%, social skills 0%

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 are: - algorithmic game theory, - algorithmic graph theory, - computational geometry, - algorithms for strings and permutations, - approximation and online algorithms, - parameterized and exact algorithms, - randomized algorithms and analysis, - streaming algorithms.

Module Components

Pflichtgruppe:

All Courses are mandatory.

Course Name	Type	Number	Cycle	Language	SWS	VZ
Advanced Algorithms	IV	0434 L 237	WiSe	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 + Prüfungsvorbereitung	15.0	12.0h	180.0h
			270.0h(~9 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 lecture consists of roughly 2/3 lecture and 1/3 tutorial parts; in the latter concrete problems are solved and an active participation (including homework) is expected.

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:

This module has no requirements.

Module completion

Grading

graded

Type of exam

Oral exam

Language

English

Duration/Extent

No information

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 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

Semester:

Zeige auch ausgelaufene Studiengänge und StuPOs

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

	Studiengang / StuPO	StuPOs	Verwendungen	Erste Verwendung	Letzte Verwendung
This module is not used in any degree program.

Students of other degrees can participate in this module without capacity testing.

Computer Science Master with focus “Reliable Systems” Computer Science diploma Technical Computer Science Master with focus “Software Engineering” Technical Computer Science diploma

Miscellaneous