CMSC452 - Elementary Theory of Computation
Course Information
Given a problem, how hard is it? This is a profound question that permeates all of computer science.
We explore this question with an eye towards proving what computers CANNOT do, or CANNOT do
with some bound on time or space or some other resource. This question has been the source of
may GREAT IDEAS in computers science!
| Instructor | Section | Day & Time | Location |
|---|---|---|---|
| William Gasarch | 0101 | TuTh 11:00AM - 12:15PM | IRB 2107 |
Course Prerequisite(s)
Prerequisite: Minimum grade of C- in CMSC351; and permission of CMNS-Computer Science department. Or must be in the (Computer Science (Doctoral), Computer Science (Master's)) program.
Informal prerequisites: You liked CMSC250!
Class Webpage
Spring 2017
Hours Per Week
Languages Used
Recommended Prior Experience
Projects, Exams, or other Assessments
HW 20%- there will be about 10 of these
Two Projects, 10 % each so 20%
Midterm 30%
Final 30 %
These are all approx
Course Topics
1) Conquering infinity: Countable and uncountable sets. Mention ind of CH from ZFC. (1 week)
2). Regular Languages: DFA’s, NFA’s, Regular expressions, pumping lemma, applications to pattern matching. GREAT IDEA: A simple model of computation that is surprisingly powerful. (3 weeks)
3. P and NP: Turing Machines, Cook-Levin Theorem (SAT is NP-complete). Reductions. Some Complexity Theory. Ways to prove that a problem probably does not have a fast exact solution. Ways around NP-completeness. Mention other classes above NP. GREAT IDEA: Being able to prove that some problems DO NOT have fast algorithms. (3 weeks)
4. The power of randomness: Comm Complexity, Poly Identity testing, Interactive proof systems. GREAT IDEA: Randomness is a surprisingly powerful computational aid. (2 weeks)
5 . Decidable and enumerable Languages: Turing Machines and the HALTING problem. Ways to show that some problems are undecidable! Mention Hilbert’s 10th problem and Godel’s theorem. GREAT IDEA: There are some problems that cannot be solved AT ALL. (2 week)
7. Optional Topics: Zero Knowledge, PAC learning, Byz Generals problem, Property Testing, (Note- those topics may be put into the section on Randomness), Cryptography
