What computers really can compute? Which problems can they solve? Which algorithms are practically useful? Shall we buy two (five?) times faster computer to solve our problem in a reasonable time or we have to design a completely new algorithm? Is this possible?

The Computational Complexity and Heuristic Programming course first presents theoretical knowledge about the algorithmic complexity, teaches you to analyze programs and gives you the competence to answer the above questions.

You will learn that some of practically interesting problems are too difficult for today's computers. Well, we want to solve them anyway, at least some of them and at least approximately. "Heureka! (I have found!)" yelled the Archimedes, when stepping into a bath he suddenly understood that the volume of water displaced must be equal to the volume of the part of his body he had submerged (and in his enthusiasm ran naked through the streets). Heuristic methods are (probably for that reason) approaches which give us useful approximate solutions to difficult problems, mostly without theoretical background. Some of these approaches have at least a guarantee about the quality of the solution, for example approximation algorithms. Other methods, like the operational research tools, local and stochastic search are today standard optimisation approaches for scientific, technical, and business problems.

The aim of the course is to offer practical knowledge about algorithm analysis and present standard and novel heuristic methods, so that a student facing a new difficult problem is able to decide which approach to use and can solve it using one of the optimization libraries.

Practical part is in the form of programming assignments, solving problems, and web quizzes. Assistant is available for consultations. The grade of practical work is a joint grade of assignments, which have to be finished on time and graded with at least 50% of points. The precondition for passing practical work is achieving at least 50% of points in web quizzes.

The final course grade consists of practical work grade (50%) and written exam (50%), in both parts one has to achieve at least 50% of points. Oral exam is optional.

- nosilec: Marko Robnik Šikonja