Département d'informatique

Description

In this course, we teach the main principles of algorithmic design, study classic algorithmic problems and introduce the most important algorithms for solving them.

Algorithmic design principles are general approaches for developing algorithms. In particular, we consider recursive and inductive methods, divide-and-conquer, backtracking and dynamic programming.

Over the years, a number of algorithmic problems have established themselves as classical problems of computer science, and elegant data structures and algorithms have been developed to solve these problems. In this course, we consider the following problems, data structures and algorithms:

• Sort: merge sort and quicksort
• Search: symbol tables, binary search trees, balanced search trees, hash tables
• Graphs: spanning trees, shortest paths, maximum flows
• Strings: String search, tries, regular expressions, data compression

Applications from practice illustrate the concepts.

Preconditions

Basic programming skills in some programming language. We will be primarily using Python, but other languages are permitted and welcome.

Learning objectives

The students gain a basic understanding of the design and analysis of data structures and algorithms.

Comments

In general, the course consists of two hours of lecture followed by two hours of classroom exercises, which are overseen by the teachers and their assistants.

Textbooks

• Algorithms, Robert Sedgewick und Kevin Wayne, Addison-Wesley, 4th edition, 2011
• Introduction to Algorithms, Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, Clifford Stein, The MIT Press, 3rd edition, 2009