
CPSC 421/501 Page, Fall 2017
This page concerns CPSC 421 Section 101 and CPSC 501 Section 101.
The courses have been combined, except that CPSC 501 will have an
additional essay to write for 20% of the grade.
This page has the most uptodate information on the course(s) and
supersedes any other document.
Overview 
This is an introductory course to Computer Science Theory.
This overview describes the course
content and covers various aspects
class policy.

Textbook 
This course textbook is
"Theory of Computation," by Michael Sipser, 3rd Edition; all homework from
the textbook is based on the 3rd edition.

Additional Handouts 
Aside from the textbook, we will use the following short articles:
Directed Graphs and Asymptotic Tests,
to which I'm
currently adding exercises; the numbering of the exercises will likely
change until Homework #1 is assigned.
Computability and SelfReferencing in CPSC421.
I have also written up some additional notes regarding class material,
namely:
Tests for Language Regularity.

Midterm 
The midterm will be held during class hours on
Wednesday, November 1, 2017.
Location TBA.

Boards and Slides 
Scan of boards for:
09_11,
09_13,
09_15,
09_18,
09_20,
09_22,
09_25,
09_27,
09_29,
10_02,
10_04,
10_06,
10_11,
10_13,
10_16,
10_18,
10_20,
Reg Exp for Numbers Divisible by 3,
from 10_02,
Slides starting week of September 4.
Roughly when topics began:
Directed Graphs and Asymptotic Tests: 09_06.
Computability and SelfReferencing: 09_18.
DFA's (1.1 of [Sip]): 09_25. NFA's (1.2): 09_27.
Reg Exp (1.3): 10_02. Nonregular (1.4): 10_04.

Homework 
All homework involving Sipser's textbook is based on the 3rd edition of
this book. Homework will be submitted to
www.gradescope.com; instructions
to follow.
Homework #1 (Due Thursday September 14, 11:59pm)
Exercises A.1(3,4,6), A.2(1,2), A.3(1), A.4(1b,1d,2d), A.5(2)
from
Directed Graphs and Asymptotic Tests.
Homework 1 Solutions.
Homework #2 (Due Thursday September 21, 11:59pm)
Exercises A.8, A.9, A.11; Bonus Exercises: A.12, A.14 from
Directed Graphs and Asymptotic Tests.
Homework 2 Solutions.
Homework #3 (Due Thursday September 28, 11:59pm)
Here is
Homework #3; it has a statement of
some homework policy.
Homework 3 Solutions.
Homework #4 (Due Thursday October 5, 11:59pm)
Here is
Homework #4.
Homework 4 Solutions.
Homework #5 (Due Thursday October 12, 11:59pm)
Here is
Homework #5.
Homework #6 (Due Thursday October 19, 11:59pm)
Here is
Homework #6.
Homework #7 (Due Thursday October 26, 11:59pm)
Here is
Homework #7; it refers to
my
Final Exam from 2014 and
Final Exam from 2011.
Homework #8 (Due Thursday November 9, 11:59pm)

Office Hours 
There is an online discussion of this course on
www.piazza.com.
In person office hours:
Joel Friedman (Instructor): Tuesday, 23pm,
in Mathematics Building, room 210, or by appointment.
Rachel (TA): Tuesday, 12pm, in X337,
Noah (TA): Friday, 1112pm, in X141,
Sharon (TA): Monday, 12pm, in Table 1, DLC
TA office hours are announced on piazza and may change according to
polls taken there; they will probably stabilize in a week or so.

Other News 
No news is good news.

