ECE 606 - Algorithms - Fall 2013
Instructor - Mahesh Tripunitara, tripunit@uwaterloo.ca
Philosophy - Algorithms are at the very foundations of computing. It is important that one understands how to design them, and analyze them for correctness and efficiency. It is important also that one recognizes whether a problem is intractable so one does not naively seek efficient solutions where none may exist. This course will be driven by computational complexity classes. The intent is to provide students with training to recognize the complexity of problems, and take an appropriate approach to solving them.
Content - Introduction: data structures, algorithms, correctness criteria, non-existence result. Complexity classes - L, NL, P, NP, PSPACE, EXPTIME, EXPSPACE, DECIDABLE, UNDECIDABLE. The class P, and examples of analysis of worst- and expected-case efficiency. Optimization vs. decision problems, the class NP, Cooke and Karp reductions, the polynomial hierarchy. Recognizing optimal substructure, dynamic programming, when not to be naive. Reconciling NP-completeness - NP as an upper-bound, reduction to SAT and SAT solvers. Reconciling PSPACE-completeness – model checking, PSPACE as an upper-bound. The class of counting problems in NP, #P. Approximation algorithms for NP-complete problems - gap preserving reductions.
Prerequisite - An undergraduate course in data structures and algorithms, similar to ECE 250.
Marking - In-class quizzes: 50%, Final exam: 50%.
Text book - None required. Material will be drawn from various sources. Some books will be on reserve at the library. These include:
- Introduction to Algorithms, Cormen et al, 2 or later ed.
- Introduction to Automata Theory, Languages, and Computation, Hopcroft et al, 2 ed.
- Computational Complexity: A Modern Approach, Arora & Barak.
- Approximation Algorithms, Vazirani.
- Model Checking, Clarke et al.