CS 341 Algorithms
Watch a video introduction to this course on YouTube.
Objectives
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.
Intended Audience
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.
Related Courses
Prerequisites: CS 240 and (MATH 239 or 249); Computer Science students only.
Antirequisites: SE 240, SYDE 423.
Cross-listed as: CM 339
Successors: CS 466.
References
Introduction to Algorithms, 3rd ed., by T. Cormen, C. Leiserson, R. Rivest, and C. Stein, McGraw-Hill, 2009.
Schedule
3 hours of lectures per week. Normally available in Fall, Winter and Spring.
Notes
- Programs and written assignments are an important component of this course.
Outline
Introduction and Analysis of Algorithms (6 hours)
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.
Algorithm Design Techniques (15 hours)
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.
Undecidability and Intractability (15 hours)
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.