CSC217a Design and Analysis of Algorithms

Course Outline Fall 2002

Instructor:       Prof. N. Khouzam
Office:             H160                         ext: 2414
Class Hrs:       MW 1:30-3:00 pm     Classroom: Mol10
Office Hrs:      to be posted

Course Description

This course is intended to make you familiar with most of the existing techniques for problem solving. First you learn about algorithms efficiency: how to measure it, and therefore how to improve it. Then different techniques for writing algorithms are discussed, with examples in each case. At the end, you are briefly introduced to the vast area of 'difficult' problems, or NP-complete. There is a minimal amount of programming involved. Examples in the book are in C++, however, in class, only pseudo-code will be used.


1. You must have CSC204 and Math 105 as prerequisite.
2. The course has some mathematical background. Math 108 is strongly recommended (see calendar).

Course Topics

. Algorithms and complexity
. Data structures (arrays, lists, stacks, queues, trees, heaps, sets, graphs...)
. Solving recurrence relations
. Divide and conquer algorithms
. Greedy algorithms (minimum cost spanning tree, shortest path ...)
. Graph search and traversal methods
. Network flow
. Dynamic programming
. Backtracking
. Branch and bound
. Introduction to NP-Complete problems


Foundations of Algorithms, by R. Neapolitan and K. Naimipour, 1998

Reference books

. Introduction to Algorithms, by T.H. Cormen, C.E. Leiserson and R.L. Rivest, 1990, 2001
. Algorithms and Theory of Computation Handbook, by Mikhail Atallah, 1999
. Computer Algorithms, by E. Horowitz, S. Sahni & S. Rajasekaran, Computer Science Press 1998
. Fundamentals of Algorithmics, by G. Brassard and P. Bratley, 1996
. Fundamentals of Computer Algorithms, by E. Horowitz and S. Sahni, 1978
. The Design and Analysis of Computer Algorithms, by Aho, Hopcroft and Ullman, 1974
. Algorithmics: Theory and Practice, by G. Brassard and P. Bratley, 1988
. Algorithmique, Conception et Analyse, by G. Brassard and P. Bratley, 1987

Course Evaluation

. 4 Quizzes   20%
. Midterm     30%
. Final Exam 50%

. Assignments will be regularly given out, corrected and returned. They are to help you learn and practice and pass your quizzes and exams. However, they do not count for marks.