IA166 Fixed-Parameter Algorithms

Faculty of Informatics
Spring 2014
Extent and Intensity
2/2. 4 credit(s) (plus extra credits for completion). Recommended Type of Completion: zk (examination). Other types of completion: k (colloquium).
Teacher(s)
Sebastian Ordyniak, PhD (lecturer), prof. RNDr. Petr Hliněný, Ph.D. (deputy)
Guaranteed by
prof. RNDr. Mojmír Křetínský, CSc.
Department of Computer Science – Faculty of Informatics
Supplier department: Department of Computer Science – Faculty of Informatics
Timetable
Wed 16:00–17:50 G191m
Prerequisites
A good understanding of algorithms and their worst-case analysis. A basic understanding of Graph Theory.
Course Enrolment Limitations
The course is offered to students of any study field.
Course objectives
The course expands on courses Algorithm design I and Algorithm design II, and it couples IA101 Algorithmics for Hard Problems with a focus on the design of fixed-parameter algorithms for hard computing tasks. The course systematically explains, combines, and compares the main possibilities for designing efficient fixed-parameter algorithms.
Syllabus
  • 1. Parameterized Complexity (Basic Theory, Examples and Interpretation)
  • I. Algorithmic Techniques: Bounded Search Tree
  • 2. Basic Ideas, Analyzing the size of the Search Tree
  • 3. Bounded Search for Vertex Cover, d-Hitting Set, Maximum Satisfiability
  • II. Kernelization
  • 4. Formal Definition, Basic Idea and Examples
  • 5. Kernelizations for Vertex Cover, d-Hitting Set, Maximum Satisfiability
  • 6. Combining Kernelization and Bounded Search Tree Algorithmic Techniques: Reduction to Problem Kernel
  • 7. Lower Bounds for Kernelization
  • III. Further Algorithmic Techniques
  • 8. Integer Linear Programming, Shrinking Search Trees by Dynamic Programming
  • 9. Color-Coding, Hashing (Examples: Longest Path/Cycle),Iterative Compression (Examples: Vertex Cover, Feedback Vertex Set)
  • IV. Applications
  • 10. Computational Biology: Phylogenetic Trees, Structure Comparision for RNA
  • 11. AI: non-monotonic Reasoning, Satisfiability
Language of instruction
English
Further comments (probably available only in Czech)
Study Materials
The course is taught only once.
The course is also listed under the following terms Spring 2013.
  • Enrolment Statistics (recent)
  • Permalink: https://is.muni.cz/course/fi/spring2014/IA166