On July 30th, 2024, due to an important database update, there will be service interruptions in the Student Self-Service and Workforce Management areas between 8 AM and 11 AM. Thank you for your understanding.

# 192.122 Algorithmic Meta-Theorems This course is in all assigned curricula part of the STEOP.\$(function(){PrimeFaces.cw("Tooltip","widget_j_id_21",{id:"j_id_21",showEffect:"fade",hideEffect:"fade",target:"isAllSteop"});});This course is in at least 1 assigned curriculum part of the STEOP.\$(function(){PrimeFaces.cw("Tooltip","widget_j_id_23",{id:"j_id_23",showEffect:"fade",hideEffect:"fade",target:"isAnySteop"});}); 2023W 2022W 2021W

2023W, VU, 2.0h, 3.0EC

## Properties

• Semester hours: 2.0
• Credits: 3.0
• Type: VU Lecture and Exercise
• Format: Hybrid

## Learning outcomes

After successful completion of the course, students are able to:

• explain the fundamental concepts behind algorithmic meta-theorems
• explain, assess, and analyze the discussed algorithms
• model and analyze unknown problems in order to apply a meta-theorem

## Subject of course

An algorithmic meta-theorem states that if a problem can be formulated in a certain logical framework, it can be solved efficiently on a certain class of problem inputs. Hence, algorithmic meta-theorems allow formulating general results beyond individual problems and use logical methods to capture whole families of problems at once. In this course, several algorithmic meta-theorems will be considered. It will be discussed how the theorems can be established and how they can be applied to individual problems.

Some of the topics covered by the course:

• Solving problems definable in first-order logic on sparse graphs.
• Solving problems definable in monadic second-order logic on tree-like graphs.
• Gaifman's theorem and Feferman-Vaught's theorem.

## Teaching methods

The core of the course consists of a series of lectures that explore topics in the studied area. The lectures are held in an informal, seminar-like setting and are interactive - students are expected to to engage in what's going on actively. Every new method and technique introduced during the lecture is demonstrated in several examples.

## Mode of examination

Immanent

The lectures and exercises take place in room FAV 01 B. The course is held in person.

## Course dates

DayTimeDateLocationDescription
Tue13:00 - 15:0031.10.2023Seminarraum FAV 01 B (Seminarraum 187/2) Kick-off Lecture
Fri09:00 - 11:0010.11.2023 - 19.01.2024Seminarraum FAV 01 B (Seminarraum 187/2) Lecture
Fri11:00 - 13:0010.11.2023 - 12.01.2024Seminarraum FAV 01 B (Seminarraum 187/2) Exercise
Fri11:00 - 13:0001.12.2023Seminarraum FAV 01 B (Seminarraum 187/2) shifted exercise
Algorithmic Meta-Theorems - Single appointments
DayDateTimeLocationDescription
Tue31.10.202313:00 - 15:00Seminarraum FAV 01 B (Seminarraum 187/2) Kick-off Lecture
Fri10.11.202309:00 - 11:00Seminarraum FAV 01 B (Seminarraum 187/2) Lecture
Fri10.11.202311:00 - 13:00Seminarraum FAV 01 B (Seminarraum 187/2) Exercise
Fri24.11.202309:00 - 11:00Seminarraum FAV 01 B (Seminarraum 187/2) Lecture
Fri24.11.202311:00 - 13:00Seminarraum FAV 01 B (Seminarraum 187/2) Exercise
Fri01.12.202309:00 - 11:00Seminarraum FAV 01 B (Seminarraum 187/2) Lecture
Fri01.12.202311:00 - 13:00Seminarraum FAV 01 B (Seminarraum 187/2) shifted exercise
Fri15.12.202309:00 - 11:00Seminarraum FAV 01 B (Seminarraum 187/2) Lecture
Fri15.12.202311:00 - 13:00Seminarraum FAV 01 B (Seminarraum 187/2) Exercise
Fri12.01.202409:00 - 11:00Seminarraum FAV 01 B (Seminarraum 187/2) Lecture
Fri12.01.202411:00 - 13:00Seminarraum FAV 01 B (Seminarraum 187/2) Exercise
Fri19.01.202409:00 - 11:00Seminarraum FAV 01 B (Seminarraum 187/2) Lecture

## Examination modalities

Exercises plus oral exam.

## Course registration

Begin End Deregistration end
21.09.2023 19:00 16.11.2023 19:00 30.11.2023 19:00

## Curricula

Study CodeObligationSemesterPrecon.Info
066 931 Logic and Computation Mandatory elective
066 937 Software Engineering & Internet Computing Not specified

## Literature

No lecture notes are available.

## Previous knowledge

Bachelor-level knowledge of graph theory, discrete algorithms and logic is assumed.

English