This course has as its aim to enhance the problem solving skills necessary when developing efficient software systems in various application areas. The course presents main algorithm analysis techniques such as recurrences and amortized analysis. Using algorithms from different areas of computer science, main algorithm design techniques are presented, including divide-and-conquer, greedy algorithms, dynamic programming, heuristic algorithms, and approximation algorithms. The algorithms covered span areas such as external memory algorithms and data structures, text search and pattern matching, advanced graph algorithms, heuristic search, and computational geometry algorithms and data structures.

The course tries to achieve a certain balance between the theory and the practice. It is not a programming course and it is not a math course.

Knowledge of Java or C++ programming, the syllabus of the Algorithms and Data Structures course on SW3 (asymptotic notation; basic knowledge of dynamic programming, divide-and-conquer algorithms, and use of recurrences; main algorithms and data structures for sorting and searching; main graph algorithms, such as BFS, DFS; and algorithms for shortest paths and minimum spanning trees).

This course has as the main aim to enhance the problem solving skills of the students necessary when developing efficient software systems in various application areas.

At the end of the course the students should:

understand and be able to apply the main algorithm design techniques including divide-and-conquer, greedy algorithms, dynamic programming, heuristic algorithms, and approximation algorithms | |

be able to analyze the efficiency of algorithms using recurrences and amortized analysis | |

be thoroughly familiar with a collection of core algorithms and
data structures for solving a number of problems from various
computer science areas, and be able to recognize the problems
that can be solved by these algorithms; the covered types of
algorithms include: * external memory algorithms and data structures for sorting and searching * algorithms and data structures for text search and pattern matching * advanced algorithms for graphs, such as maximum flow algorithms * heuristic search, such as the A*-algorithm * computational geometry algorithms and data structures, such as data structures for range searching and algorithms for line intersections, closest pairs, and convex hulls * approximation algorithms for NP-complete problems, such as the traveling salesman problem |

The course consists of 15 two-hour lectures in the mornings of mondays and thursdays with two-hour exercise classes before each lecture. You have to show up at 8:15 for the exercise classes. The exercises in exercise classes will be related to the material presented in the preceding lecture, so that you have time to work on the exercises at home.

You are very encouraged to express your criticisms, praise, remarks, comments, and questions through this anonymous form (note that it is accessable only from the .cs network computers).

Simonas Saltenis (simas@cs.auc.dk), lecturer |

Last updated Sep 6, 2004, Simonas Saltenis