Course content

Methods for analysing the efficiency of algorithms, divide and conquer techniques, recursive solution methods. Methods for ordering, searching and sorting. Data structures for efficient retrieval of data, dynamic programming and greedy algorithms. Data structures for implementing graphs and networks, as well as methods for traversals and searches. Algorithms for finding the best path(s) and matchings, spanning trees, maximal flow and optimal circulation in networks. Methods for searching in text. Theory of problem complexity. Algorithms are expressed in a language independent fashion.

Learning outcome

To give the students a solid foundation in a broad spectrum of established algorithms with usefulness in several areas of application. The students should be able to analyse the efficiency of algorithms in order to find the best possible solution to aproblem, and they will be given training in how problems are best formulated in order to be handled in a rational manner by an algorithm. Furthermore, the students will learn how to use known algorithms and existing program modules on new problems, as well as how to develop and implement new solutions for complex problems with a basis in a practical reality.

Learning methods and activities

Lectures and individual exercises. If there is a re-sit examination, the examination form may change from written to oral.

Compulsory assignments

• Exercises

Recommended previous knowledge

The students are assumed to have basic programming skills, for example, from the course TDT4100 Object-Oriented Programming. The students are also assumed to be familiar with such concepts as functions, logarithms, limits, sets, relations, proof by induction, series and partial sums, and basic probability calculus.

Course materials

Cormen, Leiserson, Rivest: Introduction to Algorithms, The MIT Press. (This may change.)

Credit reductions