Analysis of Algorithms and Heuristic Problem Solving
Section outline
-
-
-
Syllabus # Topic Description 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 Datoteka10 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, GLS12 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 Datoteka14 Biologically inspired metaheuristics many optimization methods taking inspiration in the nature and society
A survey paper on biologically inspired metaheuristics Datoteka15 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. -
The videos of the 2020/21 lectures are available in MS Teams, UL FRI AAHPS team, use the code 71t44n9 for access. URL
See the Lectures channel, tab Files.
-
-
-
-
-
-
-
-
-