Deprecated: The each() function is deprecated. This message will be suppressed on further calls in /home/zhenxiangba/zhenxiangba.com/public_html/phproxy-improved-master/index.php on line 456
CS 172: Computability and Complexity
[go: Go Back, main page]
 
CS 172
Computability and Complexity

 Prof. Luca Trevisan

Spring 2004
Tuesdays and Thursdays, 9:30-11:00am
306 Soda

  

 

Textbook

 

Information

 

Work

Note: all homeworks and solutions are off-line
(clicking on a homework or solution takes you to an `access denied' page)

     

Note: all exams and solutions are off-line

Lectures


(all homeworks and solutions are off-line)

 
 
 
  Topic Readings Problem sets
1: January 20 Summary of the course Chapter 0 .
2: January 22 Finite Automata Sections 1.1 Homework 1 out
3: January 27 Closure properties Section 1.2 .
4: January 29 Regular expressions Section 1.3 Homework 2 out
5: February 3 Pumping lemma Section 1.4
Handout 1		  
6: February 5 Myhill-Nerode theorem Handout 2 Homework 3 out
7: February 10 State minimization  Handout 2  
8: February 12 Turing machines, Church-Turing thesis Chapter 3
Turing's paper		 Homework 4 out
9: February 17 Variants of Turing machines Chapter 3 .
10: February 19 Halting problem Chapter 4 Practice Midterm
11: February 24 Reducibility and more undecidability Sections 5.2, 5.3  
February 26 MIDTERM I   Homework 5 out
12: March 2 Rice's theorem and more undecidability Handout 3  
13: March 4 Godel's incompleteness theorem Handout 4 Homework 6 out
14: March 9 A decidable logical theory Section 6.2 .
15: March 11 Kolmogorov complexity Section 6.4 Homework 7 out
16: March 16 The classes P and NP Sections 7.1, 7.2, 7.3 .
17: March 18 NP-completeness Section 7.4
Section 9.3		 Homework 8 out
March 22-26 Spring break    
18: March 30 More NP-completeness Section 7.5
Handout 5		  
19: April 1 PSPACE, Savitch's theorem Section 8.1, 8.2 Practice Midterm 2
 20: April 6 PSPACE-completeness Section 8.3
(only TQBF)		  
April 8 MIDTERM II   Homework 9 out
21: April 13 NL, NL-completeness Section 8.4,8.5
Handout 6		  
22: April 15 NL=coNL Section 8.6
Handout 6		 Homework 10 out
23: April 20 Hierarchy theorems Section 9.1
Handout 7		  
April 22 No Class   Homework 11 out
24: April 27 Randomized Algorithms Section 10.2
(no primality test)		 .
25: April 29 Randomized Algorithms and circuits Section 10.2,
Handout 8		 Homework 12 out
26: May 4 Randomized Algorithms Section 10.2  
27: May 6 Interactive proofs and Zero Knowledge Section 10.4
Handout 9		  
28: May 11 PCP theorem and applications Section 10.1, Notes  

 

 

Further Reading 

(for fun, not for credit)

Alan Turing, Alonzo Church, Kurt Gödel, Michael Rabin, Dana Scott, Steve Cook, Leonid Levin, Dick Karp, Manuel Blum

Site Meter visits since January 15, 2004