Computation Complexity and Heuristic Programming

Weekly outline

• General
  

  General

  • Course description 2019/20 File Uploaded 30/09/19, 18:18
  • Forums
    

  • Announcements Forum
  • Questions and discussions Forum
  • 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
  • Lecture slides for 2019/20 Folder
  • Old exams Folder
  • Tutorials:

    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	14. Oct - 18. Oct.	28. Oct. - 1. Nov.
    Assigment 2	15	28. Oct. - 1. Nov.	11.  Nov. - 15. Nov.
    Assigment 3	15	18. Nov. - 22. Nov.	2. Dec. - 6. Dec.
    Assigment 4	15	2. Dec. - 6. Dec.	16. Dec - 20. Dec.
    Assigment 5	40	9. Dec. - 13. Dec.	13. Jan - 17. Jan.

    
    

    To pass the course you also need to obtain a total of 50% of points in 5 online quizzes.

• 30 September - 6 October
  

  30 September - 6 October

  • Lectures: Introduction
    course contents, review of what you already know about computational complexity

    
    

    Tutorials start on week 3. (16. Oct.)
    

• 7 October - 13 October
  

  7 October - 13 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
• 14 October - 20 October
  

  14 October - 20 October

  • Lectures: Computational Complexity
    The Akra-Bazzi theorem, Linear recurrences with annihilators
    
    

  • Tutorials:
    

  • Asymptotic Notation File Uploaded 16/10/19, 15:35
  • Recurrence solving: Tree method and substitution File Uploaded 15/10/18, 14:55
  • Assignment 1 File Uploaded 16/10/19, 15:42
  • Assignment 1
• 21 October - 27 October
  

  21 October - 27 October

  
  

  • Lectures: Probabilistic analysis and randomized algorithms
    probabilistic analysis, randomized algorithms, pseudo-random numbers
    
    

  • Videolecture: Randomized algorithms URL
  • Quiz 1
  • Tutorials:
    

  • Recurrence solving 2: Masters, Akra-Bazzi, Annihilators File Uploaded 22/10/18, 13:44
  • Time complexity - external link URL
• 28 October - 3 November
  

  28 October - 3 November

  No lectures due to public holidays.
  

  • 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
• 4 November - 10 November
  

  4 November - 10 November

  • Lectures: Amortized analysis of computational complexity

  • Lectures: Analysis of multithreaded algorithms
    

  • Read Chapter 34 in the textbook Cormen et al: Introduction to Algorithms, 2009 on P, NP and NP-complete problems. The contents shall be fairly familiar to you from your previous education, so answer the questions in Quiz 2.
    
    

  • Videolecture: Amortized analysis URL
  • Quiz 2
  • Tutorials:
    

  • Probabilistic analaysis File Uploaded 7/11/19, 10:28
  • Assignment 2 File Uploaded 5/11/19, 10:42
  • Assignment 2
• 11 November - 17 November
  

  11 November - 17 November

  • Lectures: Aproximation algorithms
    read Chapter 35 in CLRS
    

  • Quiz 3
  • Tutorials:

  • Amortized analysis File Uploaded 13/11/19, 14:16
• 18 November - 24 November
  

  18 November - 24 November

  • Lectures: Linear programming for problem solving
    read Chapters 29 and 35.4 in CLRS
    

  • The code of LP example in R File Uploaded 15/11/19, 09:24
  • Tutorials:

  • Approximation algorithms File Uploaded 20/11/19, 15:37
  • Assignment 3 File Uploaded 18/11/19, 10:45
  • Assignment 3
• 25 November - 1 December
  

  25 November - 1 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
  • Non Tidyverse make_my_graph function File Uploaded 27/11/19, 17:13
  • Linear programming solution File Uploaded 27/11/19, 15:19
• 2 December - 8 December
  

  2 December - 8 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
  • Optimization File Uploaded 4/12/19, 16:04
• 9 December - 15 December
  

  9 December - 15 December

  • Lectures: Metaheuristics
    Variable neighborhood search, Memetic algorithms, Swarm intelligence
    

  • Quizz 4
  • Lab exercises:
  • tabu search File Uploaded 11/12/19, 16:10
  • Tabu resitev File Uploaded 19/12/17, 15:20
  • Assignment 4 File Uploaded 10/12/19, 11:28
  • Subset Generator File Uploaded 17/12/18, 15:16
  • Assignment 4
• 16 December - 22 December
  

  16 December - 22 December

  • Lectures: Differential evolution
    

  • 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
  • Metaheuristics File Uploaded 18/12/19, 16:00
  • Assignment 5 File Uploaded 17/12/19, 16:31
  • Problems to solve File Uploaded 17/12/19, 16:33
  • Assignment 5
  • Spreadsheet for results URL
• 23 December - 29 December
  

  23 December - 29 December

  • We wish you a Merry Christmas and a Happy New Year!
    

• 30 December - 5 January
  

  30 December - 5 January

  Not available
• 6 January - 12 January
  

  6 January - 12 January

  
  

  • Lectures: Biologically inspired metaheuristics
    

  • A survey paper on biologically inspired metaheuristics File Uploaded 9/01/20, 18:47
  • Quizz 5
  • Lab exercises: Differential evolution
    

  • Differential evolution File Uploaded 9/01/18, 15:56
• 13 January - 19 January
  

  13 January - 19 January

  Lab sessions: Preparation for exam/Solutions to old exams.
  

  • Exam 25.1.2018 File Uploaded 15/01/20, 15:50
  • Exam 9.2.2018 File Uploaded 15/01/20, 15:52
• 20 January - 26 January
  

  20 January - 26 January

  Public presentation of the assignment