CS172, Spring 2001

CS 172: Computability and Complexity
Spring 2001

[ Announcements ] [ Course Info ] [ Handouts ] [ Assignments ]

Announcements:

(05/12) Since the semester is over, all solution sets have now been restricted to password-only access. If you were enrolled in this course and still need to access the solutions, email Alex for the password.
(05/09) All homeworks have been graded and all solution sets have been posted (see below). Alex will hold informal office hours 12-2pm tomorrow (05/10) in 345 Soda; you can pick up your homeworks then.
(05/04) The final will be held 5-8pm on Friday, 05/11, in 306 Soda; like the midterms, it will be open-book. A review session has been tentatively scheduled for 12-1:30pm on Wednesday (05/09), also in 306 Soda. If you cannot attend, and would prefer it moved up to 11am-12:30pm or down to 12:30pm-2:00pm, email Alex. Solutions to MT2 and all the remaining homeworks will be posted by then.
(04/20) Midterm 2 has been graded and (FINALLY) the solutions are posted (ps / pdf). The mean was 43.6 out of 80, with standard deviation 18.6. They will be passed out after lecture on Monday 04/23 and in section later that week.
(04/09) Slideshow on NP-completeness reductions available in handouts section below
(03/15) The date for the second midterm has been set at Wednesday, 04/11/2001. The midterm will primarily cover material in chapters 4-7 of Sipser. A review session will be held on MONDAY, 04/09/2001, 7-8pm, in 306 Soda.
(03/12) Prof. Vazirani will hold extra office hours: Monday 3/12 3-5 and Tuesday 3/13 2-3.
(03/04) Clarification: Any time "<x,y>" is used, you should assume that any string constituting a valid description of form <x,y> is uniquely separable into two strings, one describing x (<x>) and one describing y (<y>). Another way to think of it is <x,y>=<x>#<y>, where the # symbol doesn't appear elsewhere in the string. (This applies to any usage of the "description" notation <x,y> (or, equivalently, <x1,x2,...,xn>) in this class; in particular, this is important for problem 4.17 on the current homework.)
(02/28) The midterms have been graded and the solutions are posted (ps / pdf). The mean was 58.9 out of 75, with standard deviation 12.6. If you did not pick up your midterm in lecture on Monday, you may do so after lecture on Wednesday or in section this week.
(02/16) The midterm review session will be held at 306 Soda, on Tuesday 02/20, 7pm-8pm. Please come with questions and/or problems.
(02/12) Exams and grading information has been posted below. The time for the final is NOT the same as that listed in the schedule of classes. Email the course staff ASAP if you cannot take the final at the time below.
(01/29) Starting with homework 2, homework will be due on Monday at 5pm, in the homework box in 283 Soda labeled "CS172"
(01/27) If you haven't gotten the Sipser text yet and need a copy of the problems for hw1, email Alex. Not having the book will not be a valid excuse for late homework.
(01/21) The section scheduled for Th3-4 will be cancelled; please attend one of the other sections instead (Th2-3, 70 Evans, or F1-2, 285 Cory) (note correction of previous typos)
(01/21) Announcements will be posted here and on the class newsgroup, ucb.class.cs172 (read-only Deja mirror)

Course Info

Professors:				TA:
Umesh Vazirani vazirani@cs.berkeley.edu Office Hours: M3-4, 671 Soda		Wim van Dam vandam@cs.berkeley.edu Office Hours: W3-4, 665 Soda		Alex Fabrikant alexf@csua.berkeley.edu Office Hours: WF2-3, 343/345 Soda

Textbooks:

[Required] Sipser, Michael, Introduction to the Theory of Computation. PWS Publishing Company, 1997. [ website ] [ errata ]
[Recommended] Lewis, Harry R., and Papdimitriou, Christos H., Elements of the Theory of Computation, 2nd ed. Prentice-Hall, 1997. [ errata ]

Grading/Exams:

25% - Homeworks (one will be dropped)
20% - Midterm 1 (Wed 02/21/2001, in class)
25% - Midterm 2 (Wed 04/11/2001, in class)
30% - Final (Fri 05/11/2001, 5pm-8pm, location TBA)

Handouts

Midterm 1 solutions (ps / pdf)
NP-completeness reductions slideshow (powerpoint / html)
Midterm 2 solutions (ps / pdf)

Assignments

Note: You do not have to turn in answers to anything marked as an "exercise" below (not in Sipser); these are provided as practice problems for you to get a better understanding of the material. Any problem marked with an asterisk (*) relies on material to be presented on Wednesday of that week.

Week 0:
1. Read Sipser up to page 43
Week 1 [HW1] (due Monday 01/29):
1. Read chapter 1 of Sipser
2. Exercises: 0.2ef, 0.3, 1.2
3. Problems: 1.4djklm, 1.5c, 1.12b, 1.14b, 1.17*, 1.24, 1.25, 1.36*, and the following problem:
  Given DFAs M1 and M2, prove that the intersection of L(M1) and L(M2) is a regular language.
4. Solutions now posted (ps / pdf / source).
Week 2 [HW2] (due Monday 02/05, 5pm, 2nd floor box):
1. Read handout on the Myhill-Nerode theorem and Sipser through page 114.
2. Exercises: 1.28, 2.1bd*, 2.4bdf*, and the following problem:
  Is the language {w in {0,1,2}*|w contains an equal number of occurrences of substrings 01 and 10} regular? Prove your answer. Note that this is an extension of problem 1.41 and should be relatively challenging.
3. Problems: 1.23, 1.27, 1.38, 1.41 (note: the alphabet is {0,1}), 2.1ac*, 2.4aceg*, and the following problem:
  Given two DFAs, provide a polynomial-time algorithm to (a) check their equivalence, and (b) if they are not equivalent, find a counter-example.
4. Extra-credit: 1.42
5. Solutions now posted (ps / pdf / source).
Week 3 [HW3] (due Monday 02/12, 5pm, 2nd floor box):
1. Read Sipser to the end of chapter 3, and the CFG parsing algorithm on pp. 240-241.
2. Exercises: 2.6bd, 3.5*
3. Problems: 2.2b, 2.5c, 2.14, 2.18bd, 3.14ab*, 3.19*
4. Solutions now posted (ps / pdf / source).
Week 4 [HW4] (due Tuesday 02/20, 5pm, 2nd floor box):
1. Read this sentence. (i.e. no new reading in Sipser)
2. Exercise: 3.8a
3. Problems: 3.11, 3.12, 3.13, 3.16, and this problem (ps / pdf).
4. Solutions draft now posted (ps / pdf / source).
Week 5 (no assignment due):
1. Read chapter 4 in Sipser.
2. Exercises: 4.1ef, 4.5, 4.7
Week 6 [HW5] (due Monday 03/05, 5pm, 2nd floor box):
1. Read this sentence. (i.e. no new reading in Sipser)
2. Exercise: 4.9, 4.16
3. Problems: 4.17, 4.18, 5.6*, 5.9*, 5.15*, and these 2 problems (ps / pdf).
4. Solutions now posted (ps / pdf / source).
Week 7 [HW6] (due Monday 03/12, 5pm, 2nd floor box):
1. Read chapter 5, and sections 6.1-6.2 in Sipser.
2. Exercises: 5.7, 5.11, 6.5
3. Problems: 6.2*, 6.12, and these 3 problems (ps / pdf).
4. Solutions now posted (ps / pdf / source / code for problem A).
Week 8 [HW7] (due Monday 03/19, 5pm, 2nd floor box):
1. Read sections 6.1, 6.2, 6.4 in Sipser
2. Problems: 6.5, 6.11 (Hint: use Th(N, +) is decidable), 6.16
3. Solutions now posted (ps / pdf / source).
Week 9 [HW8] (due Monday 04/02, 5pm, 2nd floor box):
1. Read sections 7.1-7.4 in Sipser.
2. Exercises: 7.6, 7.7
3. Problems: 7.8, 7.10, 7.11, 7.14, 7.17*, 7.19*
4. Extra-credit: 6.18
5. Solutions now posted (ps / pdf / source).
Week 10 [HW9] (due Monday 04/09, 5pm, 2nd floor box):
1. Read sections 7.5, and 8.1-8.3 in Sipser.
2. Exercises: 7.26, 7.28, 7.34
3. Problems: 7.21, 7.22, 7.23, 7.29, 7.32
4. Extra-credit: 7.40
5. Solutions now posted (ps / pdf / source).
Week 11 (no assignment due):
1. Read section 8.4-8.6 in Sipser.
2. Exercises: 8.1, 8.4, 8.7, 8.8
Week 12 [HW10] (due Monday 04/23, 5pm, 2nd floor box):
1. Review sections 8.1-8.3, and read sections 9.1-9.2 in Sipser (you may skip the section on EXPSPACE-completeness).
2. Exercises: 8.4, 9.1
3. Problems: 8.9, 8.13, 9.2, 9.10, and Give a simple criterion to decide, given a number n, whether player 1 has a winning strategy in the divisor game introduced in class on Monday. The players take turns subtracting a proper divisor (for example 1,2,3,4,6 are the proper divisors of 12. 1 has no proper divisors) of the number left by their opponent. The winner is the last player able to perform such a subtraction.
4. Solutions now posted (ps / pdf / source).
Week 13 [HW11] (due Monday 04/30, 5pm, 2nd floor box):
1. Read sections 10.2 and 10.4 in Sipser.
2. Problems: 10.6, 10.7, 10.11, 10.19
3. Solutions now posted (ps / pdf / source).
Week 14 [HW12] (due Monday 05/07, 5pm, 2nd floor box):
1. Read section 10.4 in Sipser.
2. Problems:
  1. Give an arithemtization of CNF formulae such that F <-> 0; T <-> 1; z <-> x; z complement <-> 1-x; "and" <-> ?; "or" <-> ?; "there exists" <-> ?
  2. Fill in the details of the following proof that IP is a subset of PSPACE. A language L is in IP iff there is a probabilistic verifier V: on input x, the maximum probability with which a prover can make V accept is greater than 2/3 if x is in L, and at most 1/3 if x is not in L. This may be thought of as a game between the prover and verifier, where the prover chooses each move to maximize the acceptance probability, whereas the verifier averages across his available moves. The game can be represented by a tree whose alternate levels are labeled MAX and AVERAGE. Show that the value of this tree (which is the maximum probability with which the prover can make the verifier accept x) can be computed in polynomial space using depth first search.
  3. Show that IP_norandom, defined just like IP but with the verifier having no access to random bits, is equal to NP.
3. Solutions now posted (ps / pdf / source).

Last modified: Friday, 01-Jun-2001 13:33:28 PDT / alexf@csua