
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.
Final Exam 
Our final exam is scheduled for Tuesday, December 5, 7pm, in LSK 201.
Your may bring 2 twosided 8.5 x 11 sheets of notes for the exam.
Here is
a new webpage regarding the final exam
coverage and sample problems.
Office hours before the exam:

Friday: 15:1016:00, ICCS X141 (Noah).

Monday: 10:0012:00, DLC (Noah).

Monday: 12:0014:00, DLC (Sharon).

Monday: 14:0016:00, ICCS X861 (Joel).

Tuesday: No office hours.

Midterm 
Here is
our midterm
and
solutions.
The median score on the midterm was 26.5 (out of 50). Marks are scaled
into percentages as follows: if x is your midterm score (out of 50),
your scaled mark is S(x) where (1) if 0 <= x <= 15, then
S(x)= x(50%/15), (2) if 15 <= x <= 35, then S(x) = 50% + (x15)(30%/20),
and (3) if 35 <= x <= 47, then S(x) = 80% + (x35)(20%/12).
In other words, S(0)=0%, S(15)=50%, S(35)=80%, and S(47)=100%, and all
other values of S are obtained by piecewise linear interpolation.

Midterm Practice 
Here are some additional
practice problems for the midterms;
solutions will not be provided;
some of these will be solved in class on Monday.

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.

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,
10_23,
10_25,
10_27,
10_30,
11_03,
11_06,
11_08,
11_10,
11_15,
11_17,
11_20,
11_22,
11_24,
11_27,
11_29,
12_01.
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 languages: 10_04 (asymptotic tests
and Pumping Lemma (1.4)), 10_06 (MyhillNerode).
Turing machines (3.1): 10_13
(time and space: 10_18).
Multitape machines (and countably many algorithms): 10_20.
A_TM is undecidable (4.2): 10_25.
TIME (7.1): 10_27, P and NP (7.2, 7.3): 10_27.
CookLevin Thm (7.4): 11_03.
Oracle Machines (in 6.3 and 9.2): 11_08.
SUBSETSUM, NPcompleteness (7.4): 11_08.
PSPACE, NPSPACE (8.1, 8.2): 11_17.
SNEAKYNTM, SNEAKYPSPACE (Easy complete languages): 11_20.

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 5 Solutions.
Homework #6 (Due Thursday October 19, 11:59pm)
Here is
Homework #6.
Homework 6 Solutions.
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 7 Solutions.
Homework #8 (Due Thursday November 16, 11:59pm)
Here is
Homework #8.
Homework 8 Solutions.
Homework #9 (Due Thursday November 23, 11:59pm)
Here is
Homework #9.
Homework 9 Solutions.
Homework #10 (Due Thursday November 30, 11:59pm)
Here is
Homework #10.
Homework 10 Solutions plus
diagram of Turing machine
in Problem 3.

Office Hours 
There is an online discussion of this course on
www.piazza.com.
In person office hours during the term:
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.

