Lectures:
Mon and Wed: 6:30-7:50PM
WAT 2240
Instructor:
Amey Bhangale (bhangale AT cs.ucr.edu)
Office hours: Wednesdays, 4:00 - 5:00PM 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: Homework (4) 40%, Final Exam 40%, Class participation 20%
(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):
(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