Short Description

This course has as its aim to enhance the problem solving skills necessary when developing efficient software systems in various application areas. Using concrete examples the course demonstrates the use of 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. Once in awhile we will do some advanced analysis of the complexity of an algorithm or prove its correctness, but we will not, for example, spend time on proving lower bounds of problems.

Prerequisites

Knowledge of Java or C++ programming, selected topics of the Database course on SW4 (B-trees and R-trees), 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).

Goals and Content

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

Practical information

The course consists of 15 two-hour lectures with two-hour exercise classes before each lecture. Here is the schedule. We will meet in 0.2.12 for the lectures. 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.

Anonymous comments

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

Course teacher

Simonas Saltenis (simas [at]  cs.aau.dk)