Lectures:
Tue and Thu: 9:30 am-10:50 am
Instructor:
Amey Bhangale (bhangale AT cs.ucr.edu)
Office hours: Wednesdays, 8:30 - 9:30am or by appointment.
Text Book:
Introduction To The Theory Of Computation (3rd Edition) - Michael Sipser
Prerequisites by topic:
Mathematics: Asymptotic notation, counting (permutations, sets, combinations, binomial coefficients), recurrence relations (linear and divide-and-conquer), basic probability (independence, random variable, expected value), basic linear algebra (vectors, matrices, and operations on them, solving linear systems), modular arithmetic.
Data structures: linked list, queues, stacks, binary search trees, hashing, heaps.
Algorithms: Sorting algorithms (selection, insertion, bubblesort, shellsort, quicksort, mergesort, heapsort, radix-sort, bucket-sort), graph searching (DFS, BFS), connected components, strongly connected components,
Grading: Quizzes + Homework 70%, Final Exam 20%, Class participation 10%
(Homework papers need to be formatted with LaTeX. For your convenience, a LaTeX template for homework assignments will be available.)
Tentative list of topics:
1. Automata, Languages, and Computability (Prerequisites, 4 lectures):
(a) Deterministic and Non-deterministic Finite Automata. Regular Languages.
(b) Pushdown Automata and Context-Free Languages.
2. Computational Complexity (Main topics):
(a) Turing Machines. The notion of an Algorithm. Decidability and Undecidability.
(b) Time Complexity. The classes P and NP. The P vs NP question. NP-Completeness.
(c) Space Complexity. Space complexity classes and hierarachy, Savitch’s Theorem,
PSPACE and PSPACE-completeness L, NL, and NL-completeness
(d) One or more topics from the following list:
Randomness in Computation.
Circuit Complexity.
Interactive Proofs.
Approximability and Inapproximability of NP-Hard Problems.
The actual list of topics:
Week 1
Jan 5: Introduction, course overview, finite automaton
Jan 7: Regular languages, DFA, NFA, Pumping lemma for regular languages
Week 2
Jan 12: Context-Free languages, Push-down automaton
Jan 14: Pumping-lemma for Context-free languages, Turing Machines
Week 3:
Jan 19: Multi-tape TMs and non-deterministic TMs
Jan 21: Enumerators, Church-Turing Thesis, Decidable Languages.
Week 4:
Jan 26: Diagonalization, countable sets, uncountable sets.
Jan 28: Undecidable Languages, Turing-unrecognizable languages
Week 5:
Feb 2: Turing-unrecognizable languages
Feb 4: Mapping Reducibility, Time complexity
Week 6:
Feb 9: Classes P and NP
Feb 11: NP-completeness
Week 7:
Feb 16: Cook-Levin Theorem
Feb 18: More NP-complete languages
Week 8:
Feb 23: Space Complexity, Savitch's Theorem
Feb 25: PSPACE, log-space computation
Week 9:
Mar 2: NL-completeness, NL=coNL
Mar 4: Time and Space Hierarchy theorems
Week 10:
Mar 9: Alternation, Polynomial hierarchy
Mar 11: Review
Final Exam: Monday, March 15, 9:30 am - 11 am PST