Syllabus # Topic Description 1 Introduction Course contents, review of what you already know about computational complexity 2 Computational Complexity Definitions of Θ,O,Ω,o,ω, analysis of recursive algorithms, substitution method, recursive tree method,
Recipes for divide and conquer algorithms: the master theorem, the Akra-Bazzi theorem
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,
6 Amortized analysis Amortized analysis of computational complexity,
7 Analysis of multithreaded algorithms Read Chapter 27 in the textbook 8 Approximation algorithms Read Chapter 35 in the textbook, 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 neighborhood 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
- See the Lectures channel, tab Files.
Tutorials and Lab works
There are 5 assignments and students need to get 50% of points in each assignment to pass the course. Assignments bring different number of points (to be announced). Assignments 1 - 4 require a written report in PDF format submitted via eClassroom. The assigment 5 requires a report and a public presentation taking place in the last week of the semester.
- 20 June 2023 - Hour and place TBA
- 30 June 2023 - Hour and place TBA
- 25 August 2023 - Hour and place TBA
There are 5 assignments and students need to get 50% of points in each assignment to pass the course. Assigments bring different number of points (see the table below). Assignments 1 - 4 require a written report in .pdf format submitted via eClassroom. The assigment 5 requires a report and a public presentation taking place in the last week of the semester.
Assigments Assigment Points Available Deadline Assigment 1 15 27. Feb - 5. Mar. 13. Mar. Assigment 2 15 20. Mar. - 26. Mar 10. Apr. Assigment 3 15 27. Mar - 2. Apr 17. Apr Assigment 4 15 24. Apr - 30. Apr 14. May Assigment 5 40 24. Apr - 30. Apr 21. May
To pass the course you also need to obtain a total of 50% of points in 5 online quizzes.