Course: Analysis of Algorithms and Heuristic Problem Solving

Weekly outline

General
- Course description 2020/21 File Uploaded 30/09/20, 20:20
- Forums
- Announcements Forum
- Questions and discussions Forum
- Lectures
- Video connection to live lectures, Mondays, 11:15 - 14:00 Zoom meeting
- Lecture slides for 2020/21 Folder
- The videos of the lectures are available in MS Teams, UL FRI AAHPS team, use the code 71t44n9 for access. URL
  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.
- Videoconnection to tutorials Tuesday and Friday (2) Zoom meeting
- Learning materials
- Sedgewick & Flajolet: An Introduction to the Analysis of Algorithms URL
- Coursera: Analysis of algorithms URL
- Optimization packages in R URL
- Use of optimization package Folder
- Interesting articles Folder
- Old exams Folder
- Exams
- A sample of oral exam questions for 2020/21 exams. File Uploaded 14/01/21, 20:57
- Zoom link to oral exams URL
- Schedule for the oral exam on 18 August 2021 Scheduler
- Exam dates:
  19 January 2021
  29 January 2021
  18 August 2021
5 October - 11 October
- Lectures: Introduction
  course contents, review of what you already know about computational complexity
  
  Tutorials start on week 2. (12. Oct.)
12 October - 18 October
- Lectures: Computational Complexity
  definitions of \( \Theta, O, \Omega, o, \omega \), analysis of recursive algorithms, substitution method, recursive tree method, divide and conquer algorithms, the master theorem
- Videolecture "Analysis of recursive and divide-and-conquer algorithms" URL
- Tutorials:
- Asymptotic Notation File Uploaded 16/10/19, 15:35
- Recurrence solving: Tree method and substitution File Uploaded 15/10/18, 14:55
19 October - 25 October
- Lectures: Computational Complexity
  The Akra-Bazzi theorem, Linear recurrences with annihilators
- Assignment 1 File Uploaded 30/10/20, 21:41
- Assignment 1
26 October - 1 November
- Lectures: Probabilistic analysis and randomized algorithms
  probabilistic analysis, randomized algorithms, pseudo-random numbers
- Videolecture: Randomized algorithms URL
- Tutorials:
- Recurrence solving 2: Masters, Akra-Bazzi, Annihilators File Uploaded 22/10/18, 13:44
- Time complexity - external link URL
- Usefull equations for Masters and Akra-Bazzi File Uploaded 30/10/19, 15:50
- Substitution method example with floors and ceilings File Uploaded 30/10/20, 14:25
2 November - 8 November
- Lectures: Amortized analysis of computational complexity
- Videolecture: Amortized analysis URL
- Quiz 1
- Tutorials:
- Recurrence solving 2: Masters, Akra-Bazzi, Annihilators File Uploaded 22/10/18, 13:44
- Time complexity - external link URL
- Probabilistic analaysis File Uploaded 7/11/19, 10:28
9 November - 15 November
- Lectures: Analysis of multithreaded algorithms
- Quiz 2
- Tutorials:
- Probability analysis (continued) File Uploaded 5/11/18, 14:23
- Amortized analysis File Uploaded 13/11/19, 14:16
16 November - 22 November
- Lectures: Aproximation algorithms
  read Chapter 35 in CLRS
- Quiz 3
- Tutorials:
- Amortized analysis File Uploaded 13/11/19, 14:16
- Assignment 2 File Uploaded 18/11/20, 17:34
- Assignment 2
23 November - 29 November
- Lectures: Linear programming for problem solving
  read Chapters 29 and 35.4 in CLRS
- Tutorials:
- Approximation algorithms File Uploaded 20/11/19, 15:37
30 November - 6 December
- Lectures: Optimization and local search
  read Chapter 12 in J. Kleinberg, E. Tardos: Algorithm Design. Pearson, 2006
- Tutorials:
- Introduction to R File Uploaded 5/12/17, 15:03
- Linear programming File Uploaded 27/11/19, 15:19
- Linear programming solution File Uploaded 8/12/20, 19:56
7 December - 13 December
- Lectures: Local search and metaheuristics
  Simulated annealing
  Nash equilibrium and social choice
  Tabu search. Read the chapter in M. Gendreau, J.-Y. Potvin: Handbook of Metaheuristics, 2nd Ed., Springer 2010, link
  
  Variable neighborhood search. Read the chapter in M. Gendreau, J.-Y. Potvin: Handbook of Metaheuristics, 2nd Ed., Springer 2010, link
  
  Guided local search. Read the chapter in M. Gendreau, J.-Y. Potvin: Handbook of Metaheuristics, 2nd Ed., Springer 2010, link
- Lab exercises:
- Quadratic programming File Uploaded 4/12/19, 16:03
- Quadratic programming solution File Uploaded 13/12/20, 16:23
- Optimization File Uploaded 4/12/19, 16:04
- Optimization solution File Uploaded 13/12/20, 16:36
14 December - 20 December
- Lectures: Metaheuristics
  Variable neighborhood search, Memetic algorithms, Swarm intelligence
- Lab exercises:
- Tabu Search File Uploaded 11/12/19, 16:10
- Tabu solution File Uploaded 19/12/17, 15:20
- Metaheuristics File Uploaded 18/12/19, 16:00
- Assignment 3 File Uploaded 14/12/20, 10:23
- Assignment 3
- Assignment 4 File Uploaded 14/12/20, 10:23
- Subset Generator File Uploaded 17/12/18, 15:16
- Assignment 4
- Assignment 5 File Uploaded 16/12/20, 13:38
- Test problems File Uploaded 16/12/20, 13:47
- Results spreadsheet URL
- Assignment 5
21 December - 27 December
- Lectures: Differential evolution
- Quiz 4
- Lab exercise:
- Description of DE in textbook Computational Intelligence - An Introduction File
- Das et al. (2016): Recent advances in differential evolution – An updated survey, File
- Differential evolution File Uploaded 18/12/19, 15:55
- DE Basic Implementation File Uploaded 7/01/19, 14:50
- Continious optimization to binary optimization URL
28 December - 3 January
- We wish you a Merry Christmas and a Happy New Year!
4 January - 10 January
- Lectures: Biologically inspired metaheuristics
- Lab exercises:
- Consultation hours for Assignment 5.
11 January - 17 January
- Quizz 5
- Public presentations for Assignment 5
- Lab exercises: Solving old exams
18 January - 24 January
Not available
25 January - 31 January
Not available

Weekly outline

General

5 October - 11 October

12 October - 18 October

19 October - 25 October

26 October - 1 November

2 November - 8 November

9 November - 15 November

16 November - 22 November

23 November - 29 November

30 November - 6 December

7 December - 13 December

14 December - 20 December

21 December - 27 December

28 December - 3 January

4 January - 10 January

11 January - 17 January

18 January - 24 January

25 January - 31 January