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