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