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:

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:  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