Topic outline

  • Overview

    Description:

    For many important problems in computer science, no efficient (i.e., polynomial) algorithms are known. A prominent example of this is the Traveling Salesman's Problem (TSP) of finding a shortest round trip that visits a given set of locations. In this lecture, we will discuss the design and analysis of algorithms that may be exponential in the worst case, but are demonstrably faster than obvious brute force approaches. Depending on the interest of the participants, the behavior of such algorithms in practice will also be discussed.

    Keywords: Exact exponential algorithms; parameterised algorithms. 

    Learning Objectives: 

    By the end of this course, participants should be able to develop and analyze simple exact algorithms. They will also be able to understand and apply basic design techniques, such as branching, dynamic programming, inclusion-exclusion, measure & conquer, kernelization, and search trees with limited depth.

    Evaluation: 

    Grades will be determined by an oral exam at the end of the semester. A bonus of 0,3 points will be awarded to the students who obtain at least 50% of the points on the exercises. 

    Literature:

  • Course Data


    Course size:

    5 ECTS (2 SWS)

    Time & place: 

    – (most) Lectures on Tuesdays, 12:30–14:00, room SE I
    – (most) Tutorials on Fridays, 8:30–10:00, room ÜR 
    NOTE: for scheduling reasons some lectures may occur during the tutorial time slot, and vice versa!!!

    Target group:    

    Master Computer Science, Master Mathematics, Master Computational Mathematics

    Lecturers:

    Steven Chaplick (lectures), office E12
    Martin Becker (tutorials), Email: martin.b.becker@stud-mail.uni-wuerzburg.de
    Alexander Wolff (course coordinator)

    Exam:

    Oral exam (date to be determined)
    Registration required!

    Prerequisite:

    Algorithmic Graph Theory (recommended)

    NOTE: 

    Lectures will be given in English. 

  • Exercises

    View Section Modules ►Modules:Assignments: 13