Watch a video introduction to this course on YouTube.
To study efficient algorithms, effective algorithm design techniques and approaches to handling situations in which no feasible algorithms are known. The course is intended to give the student experience in program design and to emphasize both pragmatic and mathematical aspects of program efficiency.
CS 341 is a required course for all CS major academic plans and is normally completed in a student's 3B term. A course in algorithms and algorithm design is considered essential for all Computer Science graduates. CS 234 is available for students in other plans and covers a subset of the topics of this course and CS 240.
Prerequisites: CS 240 and (CS 245 or SE 112/212) and MATH 239/249; Computer Science students only.
Antirequisites: SE 240, SYDE 423.
Cross-listed as: CM 339
Successors: CS 466.
Introduction to Algorithms, 3rd ed., by T. Cormen, C. Leiserson, R. Rivest, and C. Stein, McGraw-Hill, 2009.
3 hours of lectures per week. Normally available in Fall, Winter and Spring.
Review of previously encountered algorithm design approaches including divide and conquer. Solution of basic recurrence relations arising in such methods. The notions of average case and worst case behaviours.
A systematic study of design methods including greedy algorithms, dynamic programming, approaches to exploring graphs, backtracking, and branch and bound. Application of these techniques to a variety of problems commonly occurring in practice. Implementation of some examples and discussion of related issues.
Algorithmically reducing one problem to another as a means of developing algorithms and proving lower bounds. The undecidability of the halting problem. Proving other problems undecidable via reductions. Reductions between decision and optimization problems. The idea of polynomial time and its independence of many machine models. The classes P and NP and their relationship. Polynomial reducibility and NP-Completeness. A selection of NP-hard problems and proofs of this status.
David R. Cheriton School of Computer Science
University of Waterloo
Waterloo, Ontario, Canada N2L 3G1
Tel: 519-888-4567 x33293
Fax: 519-885-1208
Contact | Feedback: cs-uops@cs.uwaterloo.ca | David R. Cheriton School of Computer Science | Faculty of Mathematics
Last modified: Wednesday, 15-Feb-2012 10:40:46 EST
