CSE 105
Summer 2005
Theory of Computability
 Discussion sections for weeks 3 and 5 are moved to Wednesday 14001550, Center 214.
Protected Student Web Page : Link to web site with additional information for students.
Syllabus can be found here.
Lecture:
Room: Center 216
Time:
Discussion Section:
Center 216: Thurs
Office Hours: Computer
Science and
Monday and Wednesday
Email: jglick@cs.ucsd.edu
TAs:
Office: EBU12521
Office Hours: Tu/Th
10:00AM 
Email: leporter@cs.ucsd.edu
Office: EBU12521
Office Hours:
Tues
Fri
Email: jvoung@cs.ucsd.edu
Office: EBU12601
Office Hours: Wed
Wed
Email: nzang@cs.ucsd.edu
Office Hour/Class Summary
All TA OH are held in
EBU16307. See above for professor’s office locations.
Weeks 1, 2,
4

Monday 
Tuesday 
Wednesday 
Thursday 
Friday 
0900  1000 
Dr. Glick ( 

Dr. Glick ( 


1000  1100 
Dr. Glick ( 
Leo 
Dr. Glick ( 
Leo 

1100  1200 

Leo 

Leo 

1200  1300 
Class* 
Class* 
Class* 
Class* 

1300  1400 
Class* 
Class* 
Class* 
Class* 
Jan (week 1 only) 
1400  1500 
Dr. Glick 
Jan (weeks 2,4) 

Discussion** 
Jan (week 1 only) 
1500  1600 
Dr. Glick 
Jan (weeks 2,4) 

Discussion** 

1600  1700 





1700  1800 





* Class is from
Weeks 3, 5

Monday 
Tuesday 
Wednesday 
Thursday 
Friday 
0900  1000 
Dr. Glick ( 




1000  1100 
Dr. Glick ( 
Leo 

Leo 

1100  1200 

Leo 

Leo 

1200  1300 
Class* 
Class* 
Class* 
Exam* 

1300  1400 
Class* 
Class* 
Class* 
Exam* 

1400  1500 
Dr. Glick 
Jan 
Discussion** 


1500  1600 
Dr. Glick 
Jan 
Discussion** 


1600  1700 





1700  1800 





* Class is from
Class # 
Date 
Day 
Lecture Topic 
Homework 
Week 1 

1 
6/27 
M 
Introduction; DFA, Assignment: Read 1.1 and 1.2 
 
2 
6/28 
Tu 
NFA, Assignment: Read 1.3
and 1.4 and HW 1 
 
3 
629 
W 
DFA > NFA: Read 1.3 
 
4 
6/30 
Th 
Regular Expressions and
HW 2 Read 1.4 
#1 
Week 2 


7/4 
M 

 
5 
7/5 
Tu 
Pumping Lemma Read 2.1 
 
6 
7/6 
W 
Context Free
Languages/Grammars, HW 3 Read 2.2 
#2 
7 
7/7 
Th 
Push Down Automata, Read
2.3 
 
Week 3 

8 
7/11 
M 
PDA/CFG Equivalence 
#3 
9 
7/12 
Tu 
Pumping Lemma – CFL Read
3.1, 3.2 
 
10 
7/13 
W 
Turing Machine Intro 
 
11 
7/14 
Th 
Midterm Exam – Ch. 1 and 2 
#4 
Week 4 

12 
7/18 
M 
Turing Machine Defn. and Varients, Read Ch. 3 
 
13 
7/19 
Tu 
Turing decidability/recognizability, Read Ch. 4 
 
14 
7/20 
W 
EDFA, EQDFA, Read 
#5 
15 
7/21 
Th 
Decidability continued –
ATM Read 5.3 
 
Week 5 

16 
7/25 
M 
5.1, Undecidability/Reductions
Read 5.3 (skip 5.2) 
#6 
17 
7/26 
Tu 

 
18 
7/27 
W 

#7 
19 
7/28 
Th 
Final Exam 
 
Homework 1, due June 30th.
Sipser:
1.4e, 1.5b, 1.6c, 1.31, 1.32, 1.36, 1.38, and 1.40. Turn in problems 1.31 and 1.32.
For problem
1.31, use a construction proof in which you construct a DFA or NFA. For problem 1.36, you can assume n is finite.
1.31: For any string w = w_{1}w_{2}...w_{n}, the reverse of w, written w^{R}, is the string w in reverse order, w_{n}...w_{2}w_{1}. For any language A, let A^{R} = {w^{R}  w Î A}. Show that if A is regular, so is A^{R}.
1.32. Let
Sigma_{3} = {[0,0,0],[0,0,1],[0,1,0],…,[1,1,1]}
Sigma_{3} contains all size 3 columns of 0s and 1s. A string of symbols in Sigma_{3} gives three rows of 0s and 1s. Consider each row to be a binary number and let
B = {w is an element of Sigma_{3}*  the bottom row of w is the sum of the top two rows}.
For example, {[0,0,1],[1,0,0], and [1,1,0]} is an element of B but
{[0,0,1],[1,0,1]} is not an element of B
Show that B is regular. (Hint: Working with B^{R} is easier. You may assume the result claimed in 1.31.
Homework 2, due Wednesday July 6^{th}
1.7a, 1.7e, 1.17a,b, 1.18i, 1.19a, 1.57, 1.60, plus an extra problem coming soon. Turn in the extra problem and (1.60 or 1.57). In other words, you can turn in (the extra problem and 1.57) OR (the extra problem and 1.60).
Extra Problem:
Lucy and Charlie are sitting at a table. On the table
is a square tray with four glasses at the corners. Charlie's
goal is to turn all the glasses either rightside up or upside down.
However, Charlie is blindfolded and he is wearing mittens. He does not know the initial state of the
glasses. If they are initially all turned the same way, then Charlie
automatically wins. In his turn, Charlie may grab one or two glasses and
turn them over; however, because of the blindfold and the mittens he cannot see
or feel whether the glasses he grabbed are rightside up or upside down.
He can, however, choose whether to grab adjacent glasses or diagonally opposite
glasses (or just one glass). If the glasses
are all turned the same direction, Lucy announces that Charlie has won.
Otherwise, Lucy may rotate the tray, just to make Charlie's goal harder.
Find the shortest sequence of actions by Charlie that is guaranteed to win the
game, no matter how Lucy plays. Prove that your solution is correct and
is the shortest possible.
First solve the problem with an NFA. Then covert it to
a DFA that is equivalent. Then write down your answer, with the
proof of correctness and optimality. If you just write down a sequence of
moves, you will not get credit.
Homework 3, due Monday July 11^{th}
1.29abc, 1.44, 1.46c, 1.61, 2.4e, 2.6a, 2.6b
Turn in: 1.29b, 2.6b
Homework 4, due Thursday July 14^{th}
2.2ab, 2.5bc, 2.16, 2.18a, 2.19, 2.22, 2.30a, 2.30b, 2.38
Turn in: 2.2ab, 2.30a
Homework 5, due Wednesday July 20^{th}
3.1d, 3.3, 3.5, 3.6, 3.7, 3.8b, 3.9, 3.13
Turn in: 3.9, 3.13
Homework 6, due Monday July 25^{th}
4.2, 4.2, 4.3, 4.11, 4.12, 4.21, 4.22
Turn in: 4.3, 4.12 or 4.3, 4.22
Homework 7, due Monday July 27^{th}
5.1, 5.4, 5.7, 5.10, 5.12, 5.14, 5.33
Turn in: 5.1, 5.12