Analysis of Algorithms and Heuristic Problem Solving

Section outline

• Select section General

  General

  Collapse all Expand all

  • Select activity Course description 2024/25

    

    Course description 2024/25 File

    Uploaded 13/02/25, 20:34
  • Select activity Forums

    Forums
    

  • Select activity Announcements

    

    Announcements Forum
  • Select activity Questions and discussions

    

    Questions and discussions Forum
  • Select activity Lectures

    Lectures
    

  • Select activity Syllabus # Topic Description 1 Introduction Course...

    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 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.

    
    
    

  • Select activity Lecture slides for 2024/25 (updated continuously)

    

    Lecture slides for 2024/25 (updated continuously) Folder
  • Select activity The videos of the 2020/21 lectures are available in MS Teams, UL FRI AAHPS team, use the code 71t44n9 for access.

    

    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.

    Not available unless: Your Email address is tb1094@student.uni-lj.si
  • Select activity QuizzesThe quizzes promote continuous learning and...

    Quizzes
    The quizzes promote continuous learning and demote procrastination. Together, one has to gain at least 50% of all quiz points (not each individual quiz) to attend the written exam. Only quizzes submitted on-time are taken into account. Wrong answers get you negative points. Do not forget to submit a quiz.
    

  • Select activity Quiz 1

    

    Quiz 1
  • Select activity Quiz 2

    

    Quiz 2
  • Select activity Quiz 3

    

    Quiz 3
  • Select activity Quiz 4

    

    Quiz 4
  • Select activity Quiz 5

    

    Quiz 5
  • Select activity Tutorials and Lab worksThere are 5 assignments and...

    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.
    

  • Select activity Learning materials

    Learning materials
    

  • Select activity Sedgewick & Flajolet: An Introduction to the Analysis of Algorithms

    

    Sedgewick & Flajolet: An Introduction to the Analysis of Algorithms URL
  • Select activity Interesting articles

    

    Interesting articles Folder
  • Select activity Old exams

    

    Old exams Folder
  • Select activity Exams

    Exams
    

  • Select activity A sample of oral exam questions for 2020/21 exams.

    

    A sample of oral exam questions for 2020/21 exams. File

    Uploaded 14/01/21, 20:57
  • Select activity Exam dates:

    Exam dates:

    • 18th June 2025 - TBA - TBA
    • 30th June 2025 - TBA - TBA
    • 27th August 2024 - TBA - TBA
  • Select activity Tutorials:There are 5 assignments and students nee...

    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

    Assignment	Points	Available	Deadline
    Assignment 1	15	24. Feb - 2. Mar.	16. Mar.
    Assignment 2	15	17. Mar. - 23. Mar	6. Apr.
    Assignment 3	15	31. Mar - 6. Apr	20. Apr
    Assignment 4	15	21. Apr - 27. Apr	11. May
    Assignment 5	40	21. Apr - 27. Apr	1. Jun

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

  • Select activity Analysis of algorithms - script

    

    Analysis of algorithms - script File
• Select section 18 February - 24 February

  18 February - 24 February

  • Select activity There are no tutorials this week.

    There are no tutorials this week.
    
• Select section 25 February - 3 March

  25 February - 3 March

  • Select activity Tutorials:Tutorials start next week.

    Tutorials:

  • Select activity Asymptotic Notation

    

    Asymptotic Notation File
  • Select activity Assignment 1

    

    Assignment 1 File
  • Select activity Assignment 1

    

    Assignment 1
• Select section 4 March - 10 March

  4 March - 10 March

  • Select activity Tutorials: (kopiraj)

    Tutorials:
    

  • Select activity Recurrence solving: Tree method and substitution

    

    Recurrence solving: Tree method and substitution File
  • Select activity Recurrence solving 2: Masters, Akra-Bazzi, Annihilators

    

    Recurrence solving 2: Masters, Akra-Bazzi, Annihilators File

    Uploaded 1/03/22, 08:58
  • Select activity Usefull equations for Masters and Akra-Bazzi

    

    Usefull equations for Masters and Akra-Bazzi File

    Uploaded 1/03/22, 08:58
  • Select activity Time complexity - external link

    

    Time complexity - external link URL
• Select section 11 March - 17 March

  11 March - 17 March

  
  

  • Select activity Tutorials:

    Tutorials:
    

  • Select activity Recurrence solving 2: Masters, Akra-Bazzi, Annihilators

    

    Recurrence solving 2: Masters, Akra-Bazzi, Annihilators File

    Uploaded 7/03/25, 09:05
  • Select activity Usefull equations for Masters and Akra-Bazzi

    

    Usefull equations for Masters and Akra-Bazzi File

    Uploaded 7/03/25, 09:04
• Select section 18 March - 24 March

  18 March - 24 March

  • Select activity Tutorials:

    Tutorials:
    
  • Select activity Probabilistic analaysis

    

    Probabilistic analaysis File

    Uploaded 7/11/19, 10:28
  • Select activity Assignment 2

    

    Assignment 2 File

    Uploaded 23/03/25, 17:17
  • Select activity Assignment 2

    

    Assignment 2
• Select section 25 March - 31 March

  25 March - 31 March

  • Select activity Tutorials:

    Tutorials:
    

  • Select activity Amortized analysis

    

    Amortized analysis File

    Uploaded 13/11/19, 14:16
• Select section 1 April - 7 April

  1 April - 7 April

  • Select activity Tutorials:

    Tutorials:

  • Select activity Approximation algorithms

    

    Approximation algorithms File
• Select section 8 April - 14 April

  8 April - 14 April

  • Select activity Tutorials:

    Tutorials:

  • Select activity Assignment 3

    

    Assignment 3 File

    Uploaded 13/04/25, 09:57
  • Select activity Assignment 3

    

    Assignment 3
  • Select activity Linear programming

    

    Linear programming File

    Uploaded 11/04/25, 11:19
• Select section 15 April - 21 April

  15 April - 21 April

  • Select activity Tutorials:

    Tutorials:

    Threre are no tutorials this week.

• Select section 22 April - 28 April

  22 April - 28 April

  • Select activity Tutorials:

    Tutorials:

    Quadratic programming and simulated annealing.

  • Select activity Quadratic programming

    

    Quadratic programming File
  • Select activity Simulated annealing - Rastrigin

    

    Simulated annealing - Rastrigin File
  • Select activity Simulated Annealing - TSP

    

    Simulated Annealing - TSP File
  • Select activity Simulated Anneling - 0 - 1 knapsack

    

    Simulated Anneling - 0 - 1 knapsack File
• Select section 29 April - 5 May

  29 April - 5 May

  Not available
• Select section 6 May - 12 May

  6 May - 12 May

  Current week

  • Select activity Lab exercise:

    Lab exercise:

  • Select activity Local search

    

    Local search File

    Uploaded 9/05/25, 08:37
  • Select activity Guided local search

    

    Guided local search File

    Uploaded 9/05/25, 08:37
  • Select activity Variable neighborhood search

    

    Variable neighborhood search File

    Uploaded 9/05/25, 08:38
  • Select activity Assignment 4

    

    Assignment 4 File
  • Select activity Assignment 4

    

    Assignment 4
  • Select activity 4th Assignment Demo

    

    4th Assignment Demo File
  • Select activity Assignment 5

    

    Assignment 5 File
  • Select activity Assignment 5

    

    Assignment 5
  • Select activity Link to the results spreadsheet

    

    Link to the results spreadsheet URL
  • Select activity Example of .txt submisson file with coordinates

    

    Example of .txt submisson file with coordinates
  • Select activity 5th Assignment Demo

    

    5th Assignment Demo File
• Select section 13 May - 19 May

  13 May - 19 May

  Not available
• Select section 20 May - 26 May

  20 May - 26 May

  Not available
• Select section 27 May - 2 June

  27 May - 2 June

  Not available
• Select section 3 June - 9 June

  3 June - 9 June

  Not available
• Select section 10 June - 16 June

  10 June - 16 June

  Not available