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

CS 172
Computability and Complexity

Prof. Luca Trevisan

Fall 2005
Mondays and Wednesdays 10:30-12:00
310 Soda

News

The final exam is on Tuesday, December 13, 8am, in 2 Evans
Luca has extra office hours on Monday December 12, 2-3pm, 679 Soda
12/12 Homework 10 Solutions
Homework 11 Solutions
12/8 Practice Final Solutions
12/7 Practice Final
11/28 Homework 11 is due on December 7 and is the last problem set
11/15 Homework 10 (Notice the Nov 28 deadline)
11/15 Homework 9 Solutions
11/14 Homework 8 Solutions
11/12. Practice Midterm 2 Solutions
11/9. Practice Midterm 2
11/7. Homework 7 solutions
11/3. Homework 9
11/3. Homework 5 solutions
11/3. Homework 6 solutions

Textbook

Michael Sipser
Introduction to the Theory of Computation (2nd Edition)
Thompson, 2005

If you already have the first edition (PWS, 1997), it will work just fine. There is essentially no difference in content between the two editions: a few errors have been corrected, but the first edition was already almost error-free.

Information

Course overview: prerequisites, grading, etc
Schedule of discussion sections:
Tuesdays 11:00-12:00 75 Evans
Tuesdays 2:00-3:00pm 6 Evans
Getting help: schedule of instructor and TA office hours:
Luca Trevisan: Wednesdays, 2-3pm, 679 Soda. luca@cs or by appointment
Richard Dore: Monday 1:30-2:30pm and Thursday 11:00 -12:00, 1042 Evans
Access the ucb.class.cs172 newsgroup.
From off-campus you can read the newsgroup using google

Work

Homeworks are due in the CS172 drop box in 283 Soda
Solutions are accessible only from berkeley.edu computers
1. Homework 1 [Solutions] median 82
2. Homework 2 [Solutions] median 85
3. Homework 3 [Solutions] median 90
4. Homework 4 [Solutions] median 88
5. Homework 5 [Solutions] median 89
6. Homework 6 [Solutions]
7. Homework 7 [Solutions]
8. Homework 8 [Solutions]
9. Homework 9 [Solutions]
10. Homework 10
11. Homework 11
Handouts
1. Handout 1 Notes on state minimization
2. Handout 2 Notes on Rice's Theorem
3. Handout 3 Notes on logic

Exams
- Practice Midterm 1 [Solutions]
- Midterm 1 median 81
- Practice Midterm 2 [Solutions]
- Midterm 2 median 87
- Practice Final [Solutions]

Lectures

The schedule is subject to change

	Topic	Readings	Problem sets
1: August 29	Summary of the course, Finite Automata	Chapter 0, Section 1.1	.
2: August 31	Non-deterministic automata, Regular expression	Section 1.2	Homework 1 out
September 5	No Class
3: September 7	Equivalence of regular expression and finite automata	Section 1.3	.Homework 2 out
4: September 12	Equivalence of regular expression and finite automata	Section 1.3
5: September 14	Pumping lemma	Section 1.4 Handout 1	Homework 3 out
6: September 19	Myhill-Nerode theorem	Handout 1
7: September 21	State minimization	Handout 1	Homework 4
8: September 26	Turing machines, Church-Turing thesis	Chapter 3 Turing's paper
9: September 28	Variants of Turing machines	Chapter 3	Homework 5 out
10: October 3	Halting problem	Chapter 4
11: October 5	Reducibility and more undecidability	Sections 5.1, 5.3	Practice Midterm
October 10	MIDTERM I
12: October 12	Rice's theorem and more undecidability	Handout 2	Homework 6 out
13: October 17	Godel's incompleteness theorem	Handout 3
14: October 19	A decidable logical theory	Section 6.2	.Homework 7 out
October 24	No Class
15: October 26	More on a decidable logical theory	Section 6.2	Homework 8 out
16: October 31	Kolmogorov complexity	Section 6.4	.
17: November 2	Kolmogorov complexity	Section 7.4 Section 9.3	Homework 9 out
18: November 7	The classes P and NP	Sections 7.1, 7.2, 7.3
19: November 9	NP-completeness of Circuit-SAT and 3SAT	Section 7.4 Section 9.3	Practice Midterm 2
November 14	MIDTERM II
20: November 16	More NP-completeness (Graph Problems)	Section 7.5 Handout 4	Homework 10 out
21: November 21	More NP-completeness (Numerical Problems)	Section 7.5 Handout 4
22: November 23	More NP-completeness (Hamiltonian Circuit)	Section 7.5 Handout 4
23: November 28	NL, Savitch's theorem	Sections 8.2, 8.4	Homework 11 out
24: November 30	NL-completeness	Section 8.5 Handout 5	.
25:December 4	NL=coNL	Section 8.6 Handout 5
26: December 7	Hierarchy theorems	Section 9.1 Handout 6

Weekly Theory Mettings

Wednesdays, 5:00-6:30pm, 615 Soda undergraduate reading group

Wednesdays, noon-1pm, Wozniak Lounge (Soda, 4th floor) theory lunch