Science 413 - Design and Analysis of Algorithms I
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
design of efficient algorithms, for example Greedy Algorithms, Divide and Conquer, or Dynamic Programming.
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
Design, Jon Kleinberg and Éva
Tardos, Addison Wesley - Pearson Education 2006. ISBN 0-321-29535-8.
See the corresponding paragraph
in the University Calendar.
13:00-13:50, ST 127
Tutorials: Tu 11:00-11:50 (ST 061) and Th 18:00-18:50 (ST 027)
See my homepage.
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.
Mondays and Wednesdays,
13:50-14:50 (ST 127 or ICT 655), or by appointment.
Please approach me right after class if you want to meet me during my
regular office hours!