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: