COMP 3403 X1 − Fall 2006
Analysis of Algorithms
Classes: 16:00-17:30 Mon-Wed
Classroom: CAR 113
Instructor: Andrei Gagarin
Office: CAR 411
Office Hours: 14:00-15:00 Tue, 15:00-16:00 Fri
Some course materials will be available on ACME: http://acme.acadiau.ca
This course will provide an introduction to design and analysis of computer algorithms. Topics will include:
ü Review of asymptotic notation and mathematical essentials;
ü Recurrence equations;
ü Analysis of sorting algorithms;
ü Graph algorithms;
ü General algorithm design techniques;
ü Introduction to NP-completeness.
S. Baase and A. van Gelder, Computer Algorithms: Introduction to Design and Analysis, 3rd Edition, Addison-Wesley, 1999.
Secondary references (recommended):
Cormen, Leiserson, Rivest, and Stein, Introduction to Computer Algorithms, 2nd Edition (available at the bookstore).
A.V. Aho, J.E. Hopcroft, and J. Ullman, The Design and Analysis of Computer Algorithms, Addison-Wesley, 1974.
M.R. Garey and D.S. Johnson, Computers and Intractability: A Guide to the Theory of NP-Completeness.
Four Assignments 40%
Final Exam 40%
Please, read the relevant section of the undergraduate calendar on Academic Integrity. It will be strictly enforced. In particular:
· If you copy a solution to an assignment question, you are guilty of an academic offense. This includes solutions from classmates, the Internet, or textbooks.
· If you use any unauthorized resources during the midterm or the final exam, you are guilty of an academic offense.
· If you knowingly help a classmate to cheat, you are guilty of an academic offense.
The penalties for cheating are:
· For the first offense: you will receive -100% for the assignment/exam. In addition your mark will be truncated to B (about 70%).
· For the second offense: you will receive a mark of 0% for the course.