Computer
Science 413 - Design and Analysis of Algorithms I
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!