272-0300-00L  Algorithmics for Hard Problems

SemesterSpring Semester 2020
Lecturers
Periodicitytwo-yearly recurring course
CourseDoes not take place this semester.
Language of instructionGerman
CommentThis course d o e s n o t include the Mentored Work Specialised Courses with an Educational Focus in Computer Science A.



Courses

NumberTitleHoursLecturers
272-0300-00 VAlgorithmik für schwere Probleme
Does not take place this semester.
2 hrs
272-0300-00 UAlgorithmik für schwere Probleme
Does not take place this semester.
1 hrs
272-0300-00 AAlgorithmik für schwere Probleme
Does not take place this semester.
1 hrs

Catalogue data

AbstractThis course unit looks into algorithmic approaches to the solving of hard problems, particularly with moderately exponential-time algorithms and parameterized algorithms.

The seminar is accompanied by a comprehensive reflection upon the significance of the approaches presented for computer science tuition at high schools.
ObjectiveTo systematically acquire an overview of the methods for solving hard problems. To get deeper knowledge of exact and parameterized algorithms.
ContentFirst, the concept of hardness of computation is introduced (repeated for the computer science students). Then some methods for solving hard problems are treated in a systematic way. For each algorithm design method, it is discussed what guarantees it can give and how we pay for the improved efficiency. A special focus lies on moderately exponential-time algorithms and parameterized algorithms.
Lecture notesUnterlagen und Folien werden zur Verfügung gestellt.
LiteratureJ. Hromkovic: Algorithmics for Hard Problems, Springer 2004.

R. Niedermeier: Invitation to Fixed-Parameter Algorithms, 2006.

M. Cygan et al.: Parameterized Algorithms, 2015.

F. Fomin, D. Kratsch: Exact Exponential Algorithms, 2010.

Performance assessment

Performance assessment information (valid until the course unit is held again)
Performance assessment as a semester course
ECTS credits5 credits
ExaminersH.-J. Böckenhauer, R. Kralovic
Typesession examination
Language of examinationGerman
RepetitionThe performance assessment is only offered in the session after the course unit. Repetition only possible after re-enrolling.
Mode of examinationoral 30 minutes
This information can be updated until the beginning of the semester; information on the examination timetable is binding.

Learning materials

 
Main linkInformation
Only public learning materials are listed.

Groups

No information on groups available.

Restrictions

There are no additional restrictions for the registration.

Offered in

ProgrammeSectionType
CAS in Computer ScienceFocus Courses and ElectivesWInformation
Computer Science TCSpecialized Courses in Respective Subject with Educational FocusWInformation
Computer Science Teaching DiplomaSpec. Courses in Resp. Subj. w/ Educ. Focus & Further Subj. DidacticsWInformation
Computer Science MasterElective Focus Courses General StudiesWInformation
Computer Science MasterFocus Elective Courses Theoretical Computer ScienceWInformation
Mathematics Teaching DiplomaCompulsory Elective CoursesWInformation