CSE 105

Summer 2005

 

Theory of Computability

 

 

 

Announcements

 

- Discussion sections for weeks 3 and 5 are moved to Wednesday 1400-1550, Center 214.

 

Important information

Protected Student Web Page :  Link to web site with additional information for students.

Syllabus can be found here.

 

Course Information

 

Lecture:

Room: Center 216

Time: 12:30 – 1:50 PM; M,Tu,W,Th

 

Discussion Section:

Center 216:  Thurs 2:00 – 3:50 PM (Leo)

 

Instructor: 

    John Glick, Ph. D.

Office Hours: Computer Science and Engineering Building (EBU3B), Room 2204
Monday and Wednesday 9:30-10:30, and Monday 2 - 4. However, my office will not be available until July 5th (or maybe a little after). I will put a note on the website when I can get into my office. Until then my after class office hours will be wherever we can find near the classroom, and my morning office hours will have to be by email appointment.

Email: jglick@cs.ucsd.edu

 

TAs:

Leo Porter

Office:  EBU1-2521

Office Hours: Tu/Th 10:00AM - 12:00 noon

Email: leporter@cs.ucsd.edu

 

Jan Voung

Office:  EBU1-2521

Office Hours:  Tues 2:00 – 4:00 PM (weeks 2-5)

                        Fri 1:00 – 3:00 PM (week 1 only)

Email: jvoung@cs.ucsd.edu

 

Nan Zang

Office:  EBU1-2601

Office Hours:  Wed 2:00 - 4:00 PM (weeks 1, 2, and 4)

                        Wed 9:00 -  11:00 AM (weeks 3 and 5)

Email: nzang@cs.ucsd.edu

 

Office Hour/Class Summary

       All TA OH are held in EBU1-6307. See above for professor’s office locations.

 

                                                                   Weeks 1, 2, 4

 

Monday

Tuesday

Wednesday

Thursday

Friday

0900 - 1000

Dr. Glick (9:30-10:30)

 

Dr. Glick (9:30-10:30)

 

 

1000 - 1100

Dr. Glick (9:30-10:30)

Leo

Dr. Glick (9:30-10:30)

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)

Nan

Discussion**

Jan (week 1 only)

1500 - 1600

Dr. Glick

Jan (weeks 2,4)

Nan

Discussion**

 

1600 - 1700

 

 

 

 

 

1700 - 1800

 

 

 

 

 

                   * Class is from 12:30-1:50pm             ** Discussion is from 2 - 3:50pm

 

Weeks 3, 5

 

 

Monday

Tuesday

Wednesday

Thursday

Friday

0900 - 1000

Dr. Glick (9:30-10:30)

 

Nan 9-11, Dr. Glick (9:30-10:30)

 

 

1000 - 1100

Dr. Glick (9:30-10:30)

Leo

Nan 9-11, Dr. Glick (9:30-10:30)

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 12:30-1:50pm             ** Discussion is from 2 - 3:50pm

 

 

                                                      

 

Class Schedule

 

Class #

Date

Day

Lecture Topic

Homework
Due

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

Holiday – No class

-

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

Mid-term 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 Ch. 5.1

#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

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 = w1w2...wn, the reverse of w, written wR, is the string w in reverse order, wn...w2w1.  For any language A, let AR = {wR | w Î A}.  Show that if A is regular, so is AR.

1.32.  Let

Sigma3 = {[0,0,0],[0,0,1],[0,1,0],…,[1,1,1]}

Sigma3 contains all size 3 columns of 0s and 1s. A string of symbols in Sigma3 gives three rows of 0s and 1s.  Consider each row to be a binary number and let

            B = {w is an element of Sigma3* | 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 BR is easier. You may assume the result claimed in 1.31.

 

Homework 2, due Wednesday July 6th

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 right-side 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 right-side 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 11th

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 14th

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 20th

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 25th

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 27th

5.1, 5.4, 5.7, 5.10, 5.12, 5.14, 5.33

Turn in: 5.1, 5.12