COMP 3403 X1 − Fall 2006

Analysis of Algorithms

                      Classes:     16:00-17:30 Mon-Wed

Classroom:     CAR 113

                  Instructor:     Andrei Gagarin

                         Office:     CAR 411

                       E-Mail:     andrei.gagarin@acadiau.ca

             Office Hours:     14:00-15:00 Tue, 15:00-16:00 Fri

Course Webpage:

            Some course materials will be available on ACME: http://acme.acadiau.ca

Course Objectives:

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.

Textbooks:

Required:

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, 2^nd 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.

Course Evaluation:

            Four Assignments                                 40%

            Midterm                                               20%

            Final Exam                                           40%

Academic Integrity

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.