Math 166  Schedule and Homework

Tentative Schedule. Check weekly for changes.
 wk  date Monday  Wednesday  Friday
  1  4/03 0.1, 0.2  0.3, 0.4  1.1
  2  4/10  1.1  1.2  1.2-3
  3  4/17  1.3  1.4  2.1
  4  4/24 2.2  2.2  Exam
  5  5/01  2.3  3.1  3.1-2
  6  5/08  3.3, 4.1   4.1  4.2
  7  5/15  4.2  7.1  7.1
  8  5/22  7.2  7.2-3  7.3
  9  5/29  Holiday  Exam  7.4
 10  6/05  7.4 7.4-5  Review


                                Math 166   Homework (due in section)          page up for schedule
                                Late homework will normally not be accepted.           
old homework
See policy on discussing and writing up homework.
Solutions will be available at soft reserves.


Exam 5/31:  In  WLH 2205 for Section 1  and   WLH 2113 for Section 2 
Covering Chapters 2 through 4 and Section 7.1.
Closed book, but you may bring one page of notes.  Blue books NOT needed.
My old exams and solutions
Due 6/1:  7.6, 7.7, 7.13 
** This may make the closure problems (6, 7, 13) clearer:  Suppose we want to prove that NP is closed under union.  Let A and B be two languages in NP.  This means there are polynomial-time verifiers for A and B. You must show how to construct a polynomial time verifier for the union.  You could appeal to Theorem 7.17 and work with polynomial-time NTMs instead.  In problem 7.13, there exists a polynomial-time decider for A.  You must show how to use it to construct one for A*.  Use the hint and the idea in the proof of Theorem 7.14.
Last HW:  
(not to be handed in)  7.5, 7.10, 7.17 (there is a very simple solution), 7.19, 7.33

Old Homework


Due 4/6:    0.1, 0.2, 0.3, 0.4, 0.8    You may wait until 4/13 to turn this in.
Due 4/13
:  1.1, 1.2(M1), 1.3, 1.4(a,c,e,h,l), 1.5(a,b,c,d), 1.9, 1.10["show" means "prove"]
** Remember for 1.4 that your DFA must accept ALL the strings in the set AND NO OTHER STRINGS. Also, the empty string has an even number of 1's.
** The set in 1.4(c) is ALL strings that contain 0101 as a substring.
Due 4/20:  1.12, 1.13(c,e,h), 1.14(a), 1.15(a,f), 1.16, 1.24, and design an NFA that recognizes the star of the language described in 1.4(l) (You could base it on the NFA for 1.5(c) or the DFA for 1.4(l).)
** You may find it instructive to compare the complexity of the REs and DFAs in 1.4 and 1.13.
Due 4/27
:   1.17, 2.1(b,d), 2.3, 2.4 
** For some of 2.4, you may find it helpful to consider a pushdown automaton first.
Exam 4/28:  In  WLH 2005  Covering Chapters 0 and 1.
Closed book, but you may bring one page of notes.  Blue books NOT needed.
My old exams and solutions
Due 5/4:   2.5(a,e,f), 2.8, 2.15, 2.21(a)
** For 2.15, remember that, by Section 2.2, you can use either a CFG or a PDA, so choose whichever you find easier for each of the three operations.
Due 5/11: 
3.2(a,b), 3.5, 3.6, 3.7, 3.9
Due 5/18:  4.1, 4.3, 4.5, 4.10, 4.12; Show that the language in Example 2.20 is decidable.
** Hint on 4.10 (or 4.12): Explain why you can remove any edges (or rules) that contain alphabet (or terminal) symbols other than 1.  Study the DFA (or CFG) that you get after the removal.
Due 5/25:  7.1, 7.2, 7.4