Course Program:
Subject: |
Complexity theory is the mathematics of practical computer science. Some problems have algorithms for solving them. But only some of these algorithms can be implemented using a sensible amount of resources. Which ones and why? We will try to understand this. |
Textbook: |
Michael Sipser. Introduction to the Theory of Computation. 3rd edition. Cengage Learning, 2013. |
Instructor: |
Cem Say |
Prerequisite:
CmpE 350 or equivalent (Talk to the instructor if you have taken CmpE 415 already.)
Topics:
1. Time Complexity
2. Space Complexity
3. Randomized Computation