Computer Science 413 - Design and Analysis of Algorithms I

Fall 2009 - Philipp Woelfel

Course Summary

For many problems that we want to solve with the help of computers, we have to design efficient algorithms. Although the problems encountered can be very diverse, many efficient algorithms for various problems are based on similar ideas and techniques. In this course we study fundamental techniques for the design of efficient algorithms, for example Greedy Algorithms, Divide and Conquer, or Dynamic Programming.

Whenever we design an algorithm, it is important to verify that the algorithm is correct, and that it is efficient. In fact, determining the efficiency and correctness of an algorithm is often a crucial part of the algorithm design process. Therefore, we study how to analyze algorithms, how to distinguish inefficient from efficient ones, and how to prove correctness.

For some "hard" problems, efficient algorithms do not exist, or at least it is unlikely that we can design algorithms that solve these problems efficiently. If we are able to identify such problems, then we can avoid useless attempts to find efficient algorithms for hard problems. Instead, we can focus on alternative approaches, for example by remodelling the problem, or designing algorithms that find close-to-optimal solutions instead of optimal ones. Therefore, we study how to identify some computationally hard problems.

Textbook

Algorithm Design, Jon Kleinberg and Éva Tardos, Addison Wesley - Pearson Education 2006. ISBN 0-321-29535-8.

Requirements

See the corresponding paragraph in the University Calendar.

Time Table

Lectures: TR 09:30-10:45 (CHC 105)
Tutorials: Mo 11:00-11:50 (ST 055), Mo 15:00-15:50 (ST 055), Tu 14:00-14:50 (ENC 033)
Quizzes: Th 18:00-18:50

Contact

See my homepage.

Forum

News and handouts will be posted to the course forum. If you have questions that may be interesting to all students, please ask them there.

Office Hours

Tuesdays and Thursdays, 10:45-11:45 (CHC 105 or ICT 655), or by appointment.
Please approach me right after class if you want to meet me during my regular office hours!