CloseHelpPrint
Kies de Nederlandse taal
Course module: 201900082
201900082
Advanced Algorithms and Computational Complexity
Course info
Course module201900082
Credits (ECTS)5
Course typeCourse
Language of instructionEnglish
Contact personprof.dr.ir. H.J. Broersma
E-mailh.j.broersma@utwente.nl
Lecturer(s)
Lecturer
prof.dr.ir. H.J. Broersma
Contactperson for the course
prof.dr.ir. H.J. Broersma
Academic year2020
Starting block
1B
RemarksThe course is open to students from other programmes.
Application procedureYou apply via OSIRIS Student
Registration using OSIRISYes
Aims
Apart from the main aim to provide the students with a general understanding of the different aspects involved in the analysis of algorithmic solutions to graph problems, the specific learning goals of the course are that at the end of the course:
  • the students can apply the basic notions of the analysis of algorithms and their computational complexity to a variety of graph problems
  • they can explain the difference between polynomial, NP-complete and NP-hard problems
  • they are able to apply their knowledge to a variety of graph problems
  • they can recall NP-hardness and NP-completeness proofs from the lectures
  • they can develop new proofs for variants of the treated problems
  • they can recall structural properties of special graph classes
  • they can analyse the complexity of graph problems restricted to such classes
  • they can evaluate the quality of heuristics for NP-hard problems
  • they are able to apply their knowledge to analyse the quality of heuristics
  • they can develop their own heuristics
Content
We start by introducing and addressing some seemingly analogous graph problems, like finding a shortest path versus a longest path between two given vertices, finding an Euler tour versus a Hamilton cycle, and testing a graph for 2-colourability versus 3-colourability. This should evoke the intuition that some problems are easy to solve algorithmically, whereas the analogous counterparts seem much harder to solve. We will formalize “easy” and “hard” by introducing the time complexity of an algorithm and the Big Oh notation, and define what is meant by a polynomial algorithm. We will distinguish solutions that are easy to find and that are easy to verify, as a means to define the classes P and NP in an intuitive way, and introduce NP-complete and NP-hard problems, avoiding the introduction of Turing Machines or other models of computation. The latter form a central part of the mathematically more rigorous approach in “Limits to Computing”. Polynomial reductions will be treated in detail, with many illustrative examples and exercises. For NP-hard problems, we will analyse possible heuristics for producing reasonable solutions, and for proving guaranteed quality measures, showing that some NP-hard problems allow good approximations, whereas others do not. A large part of the remaining lectures and tutorials will deal with special graph classes. The motivation is that many NP-hard problems become easy when restricted to graph classes, like tree-like graphs, planar graphs, interval graphs, and others. We will supply examples in which such classes appear naturally from application areas. We will also look at NP-hard problems that remain NP-hard, even when restricted to very special graph classes.
Assumed previous knowledge
Basic knowledge in algorithms and graph theory, as in Module 7 of the current CS/AM Bachelor programme.
Participating study
Master Applied Mathematics
Participating study
Master Computer Science
Required materials
Literature
Written and provided by the lecturer
Recommended materials
-
Instructional modes
Lecture

Tutorial

Tests
Test

CloseHelpPrint
Kies de Nederlandse taal