CSE 105: Automata and Computability Theory
Autumn 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, 2nd ed. (available for download, and
through Amazon)
Optional Textbook: Tom Stuart,
Understanding Computation
Lectures: Tuesdays and Thursdays,
3:30–4:50 PM
in SOLIS 104.
Section: Mondays, 5:00–5:50 PM
in SOLIS 104.
Section: Fridays, 11:00–11:50 AM
in PCYNH 120.
Final: Monday, December 9th, 3:00–5:59 PM,
in SOLIS 104.
Overview
Announcements

Monday, November 11th is Veterans’ Day, a holiday. Section
and office hours will not be held that day. (The same holds for
lecture, section, and office hours on Thursday and Friday of
Thanksgiving week, November 28th and 29th.)

There is a third edition of Sipser’s book, but we will be
using the second edition, which has everything we need
and is much more affordable. We will read only chapters 1 through
5. You should be able to obtain a facimile edition of just these
chapters from the bookstore for around $60. Alternatively,
consider used copies
available at
Amazon and
elsewhere.
Exercises
You may collaborate with as many other students in the class on the
exercises. You should write up your solutions on your own.
We will collect exercises in class and check them off for
completeness. In addition, we will grade one problem from
each exercise, chosen at random.
 Exercise #1:
Hammack §1.1 14,33;
§1.2 8;
§1.3 3;
§1.4 8;
§1.5 9;
§1.8 14;
Hammack §2.1 5,6;
§2.2 7;
§2.4 3;
§2.5 10;
§2.7 3;
§2.10 5;
Sipser 1.1, 1.2, 1.6h, 1.12
Collected: Thursday, October 3rd, 2012, 3:30 PM.
 Exercise #2
Hammack §4 3,7,16;
Sipser 1.9b, 1.10a, 1.14b, 1.16a, 1.19b
Collected: Tuesday, October 22nd, 2013, 3:30 PM.
 Exercise #3
Hammack §5 2,7,18;
Hammack §6 9,18;
Sipser 2.2, 2.3 (all parts), 2.6b, 2.14.
Collected: Thursday, October 31st, 2013, 3:30 PM.
 Exercise #4
Hammack §7 4,10,17,23;
Sipser 2.30 (all parts), 3.1b, 3.2d, 3.5, 3.7, 3.8b.
Collected: Thursday, November 14th, 2013, 3:30 PM.
 Exercise #5
Hammack §8 3,4,26,29;
Sipser 3.13, 4.1 (all parts), 4.2, 4.4, 4.9
Collected: Thursday, November 21st, 2013, 3:30 PM.
 Exercise #6
Hammack §9 2,7,14,20,21;
Sipser 5.1, 5.2, 5.4, 5.5, 5.7, 5.22, 5.23
Collected: Tuesday, December 3rd, 2013, 3:30 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. Think of them as takehome, openbook midterms.