COMPSCI 3AC3

Algorithms and Complexity

Undergraduate

Basic computability models; the Church-Turing thesis, complexity classes; P versus NP; NP-completeness, reduction techniques; algorithmic design strategies; flows, distributed algorithms, advanced techniques such as …

Winter 2026 · C01

Readings

Algorithm Design Ed: 1
Kleinberg · 1 · Required
ISBN 9780321295354
Etext Introduction To The Theory Of Computation - 12 Month Access Ed: 3
Sipser · 3 · Suggested
ISBN 9781285320731; 9780357670583
Introduction To Algorithms Ed: 4
Cormen · 4 · Suggested
ISBN 9780262046305

Winter 2025 · C01

Readings

Algorithm Design
J. Kleinberg and E. Tardos · Required
Addison-Wesley
Introduction to Algorithms
T. H. Cormen, C. E. Leiserson, R. L. Rivest, and C. Stein · 4th · Recommended / optional
MIT Press
Introduction to the Theory od Computation
M. Sipser · 3rd · Recommended / optional
Cengage Learning

Winter 2025

Topics

LIST E
SOFTWARE ENGINEERING TECHNICAL ELECTIVES Basic computability models
Church-Turing thesis
Complexity classes
P versus NP
NP-completeness
Reduction techniques
Algorithmic design strategies
Flows
Distributed algorithms
Advanced techniques
Randomization

Readings

"Algorithm Design", by J. Kleinberg and E. Tardos, Addison-Wesley, $169.27
required
"Introduction to Algorithms", 4th Ed., by T. H. Cormen, C. E. Leiserson, R. L. Rivest, and C. Stein, MIT Press, 150 USD
4th Ed · recommended
"Introduction to the Theory of Computation", 3rd Ed., by M. Sipser, Cengage Learning, $167.51
3rd Ed · recommended

Sources