1 |
Introduction |
Course contents, review of what you already know about computational complexity |
2 |
Computational Complexity |
Analysis of recursive algorithms, substitution method, recursive tree method, Recipes for divide and conquer algorithms: the master theorem, the Akra-Bazzi theorem http://videolectures.net/mit6046jf05_introduction_algorithms/ |
3 |
Linear recurrences |
Solving linear recurrences with annihilators
|
4 |
Probabilistic analysis |
Indicator random variables, probabilistic analysis of algorithms |
5 |
Randomized algorithms |
Randomized algorithms, pseudo-random numbers, http://videolectures.net/mit6046jf05_leiserson_lec04/ |
6 |
Amortized analysis
|
Amortized analysis of computational complexity, http://videolectures.net/mit6046jf05_leiserson_lec13/ |
7 |
Analysis of multithreaded algorithms |
Read Chapter 27 in the textbook |
8 |
Approximation algorithms |
Read Chapter 35 in the textbook, and revise P and NP algorithms by reading Chapter 34 |
9 |
Linear programming for problem solving |
Read Chapters 29 and 35.4 in the textbook
The code of LP example in R Datoteka |
10 |
Optimization and local search |
Read Chapter 12 in J. Kleinberg, E. Tardos: Algorithm Design. Pearson, 2006 |
11 |
Metaheuristics
|
Simulated annealing, Nash equilibrium and social choice, tabu search, variable neighbourhood search, guided local search Read the corresponding chapters in M. Gendreau, J.-Y. Potvin: Handbook of Metaheuristics, Springer, 2010 TABU search, VNS, GLS
|
|
12 |
Population methods |
Memetic algorithms, swarm intelligence
|
13 |
Differential evolution |
Optimization with differential evolution
Description of DE in textbook Computational Intelligence - An Introduction
Das et al. (2016): Recent advances in differential evolution – An updated survey, Datoteka Datoteka |
14 |
Biologically inspired metaheuristics |
many optimization methods taking inspiration in the nature and society
A survey paper on biologically inspired metaheuristics Datoteka |
15 |
Machine learning for combinatorial optimization
|
For some problems, heuristics can be obtained by collecting execution data and applying machine learning algorithms to guide the search. |