analyse NP-completeness of an algorithmic problem;
use advanced algorithm analysis methods, such as amortised analysis and probabilistic analysis;
use advanced algorithm design methods in order to approach hard algorithmic problems in a pragmatic way, such as by using randomised algorithms (such as universal hashing), approximation algorithms, stochastic local search (such as simulated annealing and tabu search), integer programming, propositional satisfiability (SAT), and SAT modulo theories (SMT).
NP-completeness. Advanced techniques in algorithm analysis and design such as amortised and probabilistic analysis, universal hashing, integer programming, simulated annealing, tabu serach, probabilistic satisfiability (SAT). Connections to modern research in algorithmics.
Lectures, lessons and exercises.
Written and oral presentation of assignments, 2 credits, and written and oral exam, 3 credits.
The course cannot be included in a degree together with the courses Algorithms and data structures (DV)3/III (1DL104, 1DL113, 1DL030) and Advanced algorithmics (1DL480).