CSE 105: Automata and Computability Theory
Winter 2012
Instructor:
Hovav Shacham,
hovav@cs.ucsd.edu
Textbook: Michael Sipser,
Introduction to
the Theory of Computation, 2nd ed.
Textbook: Richard Hammack,
Book of
Proof (available online)
Lectures: Mon, Wed, Fri
2:00–2:50 PM
in
PCYNH 106 CENTR 216.
Section: Wednesdays, 4:00–4:50 PM
in CENTR 113.
Final: Monday, March 19th, 3:00–5:59 PM,
in CENTR 216.
Overview
Announcements

The final exam will be closed book. However, you will be
allowed to bring in one sheet of paper,
8½″×11″, handwritten—not printed or
photocopied—filled on both sides with any information you
think you’ll need.

HS’s office hours on Thursday 1 March are cancelled;
he’ll hold makeup office hours on Wednesday 7 March instead,
from 4:00 to 6:00 PM in his office.

Starting Friday, 24 February, lectures are moved to Center
Hall, room 216.

HS’s office hours on Thursday 2 February are cancelled;
he’ll hold makeup office hours on Monday 6 February instead,
from 5:00 to 7:00 PM in his office.

The due date for problem set 1 is pushed back from Friday (27 Jan)
to Monday (30 Jan).

HS’s office hours on Thursday 19 January are cancelled;
he’ll hold makeup office hours on Monday 23 January instead,
from 4:00 to 6:00 PM in his office.
Exercises
You may collaborate with as many other students in the class on the
exercises. You should write up your solutions on your own.
Exercises are collected in class and checked off for completeness
but not graded.
 Exercise #1:
Hammack §1.1 4,15,25;
§1.2 1(a)–(e);
§1.3 4,5;
§1.4 15,16;
§1.5 9;
§1.6 2;
Hammack §2.1 4,5,6;
§2.2 1,7;
§2.5 10;
§2.7 8;
§2.10 3.
Collected: Friday, January 13th, 2012, 2:00 PM.
 Exercise #2:
Hammack §4 5,14,17,26;
Sipser 1.3, 1.4b, 1.6g, 1.7d, 1.11.
Collected: Monday, January 23rd, 2012, 2:00 PM.
 Exercise #3:
Hammack §5 7,10,15,18;
Sipser 1.20, 1.22, 1.23, 1.29.
Collected: Wednesday, February 1st, 2012, 2:00 PM.
 Exercise #4:
Hammack §6 14,15,16,17;
Sipser 2.2, 2.6a, 2.15.
Collected: Wednesday, February 15th, 2012, 2:00 PM.
 Exercise #5:
Hammack §7 5,17,22;
Sipser 3.2a, 3.5, 3.8b
Collected: Wednesday, February 22nd, 2012, 2:00 PM.
 Exercise #6:
Hammack §8 2,9,19,21;
Sipser 4.2, 4.3
Collected: Friday, March 2nd, 2012, 2:00 PM.
 Exercise #7:
Hammack §9 17,21,30;
§10 3;
Sipser 5.1, 5.2
Collected: Friday, March 9th, 2012, 2:00 PM.
Problem Sets
You must solve the problem sets on your own, without
discussing them with anyone. You must write up your solutions on
your own. Problem sets are collected in class and graded for
correctness.
 Problem set #1:
download as a PDF.
Due: Friday, January 27th
Monday, January 30th, 2012, 2:00 PM.
 Problem set #2:
download as a PDF.
Due: Friday, February 10th, 2012, 2:00 PM.
 Problem set #3:
download as a PDF.
Due: Monday, February 27th, 2012, 2:00 PM.
 Problem set #4:
download as a PDF.
Due: Wednesday, March 14th, 2012, 2:00 PM.