Module CS4501-KP12, CS4501

Duration

2 Semester

Turnus of offer

each summer semester

Credit points

12

Course of studies, specific fields and terms:

• Master Entrepreneurship in Digital Technologies 2020, advanced module, specific
• Master Computer Science 2019, optional subject, advanced module
• Master IT-Security 2019, advanced module, Elective Computer Science
• Master Entrepreneurship in Digital Technologies 2014, advanced module, specific
• Master Computer Science 2014, advanced module, advanced curriculum

Classes and lectures:

• Seminar Algorithmics, Logic and Computational Complexity (seminar, 2 SWS)
• Algorithmics, Logic and Computational Complexity (exercise, 2 SWS)
• Algorithmics, Logic and Computational Complexity (lecture, 4 SWS)

Workload:

• 120 hours in-classroom work
• 160 hours private studies and exercises
• 40 hours exam preparation
• 40 hours work on an individual topic with written and oral presentation

Contents of teaching:

• recent results in algorithmics and complexity theory
• communication and circuit complexity
• structural and descriptive complexity theory
• algorithmic game theory
• nonstandard computing models
• understanding logics as a tool

Qualification-goals/Competencies:

• the students can demonstrate a deep knowledge of concepts and methods for algorithm design and complexity analysis.
• They are able to classify algorithmic problems and to select appropriate strategies for their solution
• They are able to model complex problem settings appropriately.
• They can assess and explain the importance of lower bounds for applications.

Grading through:

• Oral examination

Requires:

• Algorithmics (CS4000-KP06, CS4000SJ14)

Responsible for this module:

• Prof. Dr. Kim-Manuel Klein

Teacher:

• Institute for Theoretical Computer Science
• Prof. Dr. Rüdiger Reischuk
• Prof. Dr. rer. nat. Till Tantau
• Prof. Dr. Maciej Liskiewicz
• Prof. Dr. Kim-Manuel Klein

Literature:

• R. Reischuk : Einführung in die Komplexitätstheorie Teubner, 1990
• S. Arora, B. Barak : Computational Complexity Cambridge UP 2009
• C. Papadimitriou : Computational Complexity Addison-Wesley, 1994
• M. Huth, M. Ryan : Logic in Computer Science Cambridge University. Press 2004
• D. Kozen : Theory of Computation Springer, 2006

Language:

• German and English skills required

Notes:

Last Updated:

06.01.2025