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:

1. 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.

2. Data structures: linked list, queues, stacks, binary search trees, hashing, heaps.

3. 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