CSE 105
Theory of Computation
(Spring, 2006)
Home | Syllabus |
Schedule | Exams |
Homework | Sections
Instructor: Neil Rhodes 
(nrhodes@cs.ucsd.edu)
Office hours: Tuesday 2:00-3:00, Thursday 6:45-7:45 in EBU3B 2208.
TAs: Lawrence Cayton 
(lcayton@cs.ucsd.edu)
Office hours: Monday 11-12, Thursday 10:30-11:30, EBU3B B260A.
Lucas Lee (lalee@cs.ucsd.edu)
Office hours: Monday 10-11, Tuesday 9-10, EBU3B 240A.
Please use the web board for questions related to the class.
Announcements
Check these announcements frequently. It will contain the latest information concerning possible changes
in office hours, reading assignments, etc.
Jun 14: Neil will have office hours today, Wednesday, from 3-5 in my office, 2208.
On Monday, June 12: from 10-11am in room 240A (regular hours/place), 11am-12pm 260A (regular hours/place for lawrence)
On Tuesday, June 13: from 9-11am in room 240A (regular hours/place just longer)
Jun 11: Lucas will have regular and extended office hours as follows:
On Monday, June 12: from 10-11am in room 240A (regular hours/place), 11am-12pm 260A (regular hours/place for lawrence)
On Tuesday, June 13: from 9-11am in room 240A (regular hours/place just longer)
May 21: My (Lawrence's) apologies for cancelling section on friday. I had to get stitches at last minute. In case you were unable to attend the 3pm section, review section 4.2 of the text. We went over diagonalization, the existence of unrecognizable languages, and the undecidability of the halting problem. I will have your quizes in my office hours and at section next week.
May 18: Homework has been modified: problems from chapter 5 were removed (since we didn't
get that far in lecture today).
May 11: Solution to the midterm is posted.
May 10: Lawrence's office hours on thursday, 5/11 are cancelled
May 8:
Last Thursday's lecture had an error in the proof that {0^n | n is prime} is not context-free.
The problem was that multiplying p1,..,pk and adding 1 doesn't necessarily yield a prime. It could also
yield a composite number with a different prime factor (some pj where j > k).
An easier proof is as follows:
- Adversary choose p.
- We choose s=0^{prime greater than p}
- Adversary chooses s=vwxyz with |wy| > 0.
- Our general string is of the form vw^ixy^iz = 0^(s-|wy| + |wy|*i). We choose i = |s| - |wy|.
The length of |vxz| is divisble by i, and so is |wy|*i. Thus, we can rewrite our new string as 0^((s-|wy|)(1+|wy|)).
Thus, there are a composite number of 0's.
- Since our new string is not in the language, the language is not pumpable.
But all context-free languages are pumpable, so our language is not context-free.
May 4:
I've posted a study guide containing what you should know for the midterm at the Exams page.
May 2:
Lawrence's thurs (5/4) office hours are extended to 10-12.
April 18:
From now on, lecture will be in SOLIS 104 (west of the library).