Algorithms and System Utilities

How complex is our algorithm? 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 Analysis of Algorithms and Heuristic Problem Solving ourse 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. Methods, like the operational research tools, local and stochastic search are today standard optimisation approaches.

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 five assignments (dispersed throughout the semester) , and five 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.