Computer Science 413 - Design and Analysis of Algorithms I

Winter 2008 - Philipp Woelfel

Note: This course is managed by Blackboard. Please go to my.ucalgary.ca to see more information.

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: MWF 13:00-13:50, SB 142
Tutorials: Tu 11:00-11:50, SA 145
Quizzes: Th 18:00-18:50, TBA

Contact

See my homepage.

Office Hours

Wednesdays and Fridays, 14:00-14:50 (ICT 655), or by appointment.
Please approach me right after class if you want to meet me during my regular office hours.