**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.

**Important:**

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

*Textbook*

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.

*Note:*

- Assignments have to be typed, or handwritten VERY neatly if you want them corrected.
- Please note that there are no supplemental exams for this course.
- Please read pages to in the 2002/03 calendar, regarding plagiarism, academic dishonesty and attendance.