
CPSC 421/501 Page, Fall 2014
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.
This page has the most uptodate information on the course(s) and
supersedes any other document.
Not all course material are available at all times (especially solution
sets to homeworks).
Overview 
Overview for this course.
The main text for this course is
Theory of Computation, by Michael Sipser, 3rd Edition.
We shall begin the course with a handout
Computability and SelfReferencing in CPSC421; this is a more general (and leisurely)
treatment of Section 4.2 of Sipser's textbook, that doesn't require knowing
how a Turing machine works. We will then cover Turning machines,
parts of Chapters 37 and 9; regular languages (Chapter 1) and
contextfree languages (Chapter 2) will be covered briefly towards
the end of the course.

Final Exam 
The final exam for this class will take place on December 3 at 8:30am.

Sample Exams 
We have a new document describing
our coverage of Sipser Chapters 8 and 9, and giving sample
exam problems (some of which are assigned for homework).
All the homework problems, and all the problems in
Computability and SelfReferencing in CPSC421
are good sample exam problems (some of the longer problems would be
shortened or modified so as to be solvable more quickly).
Here are some old exams, some with solutions:
 midterm 2010 (solutions),
 final 2010,
 midterm 2011 (solutions),
 final 2010,
 midterm 2014 (solutions).
(This term, the midterm was scaled as follows:
if your raw score on the midterm is r (out of 36 points), your scaled
grade is 5r if r <= 10, and 2r+30 if r >= 10.
Hence 10/36 yields a scaled mark of 50, and a 36/36 yields a scaled
mark of 102.)
More sample midterm problems
discusses the material covered by the midterm this term; this is
the material in
Computability and SelfReferencing
in CPSC421, Sipser 3.1, 3.2, Our discussion of PALINDROME,
3.3 (Terminology for describing Turing
machines), 4.2, 7.1, 7.2.

Handout 
We begin the course by talking about the Halting problem and related
``paradoxes''
with the handout
Computability and SelfReferencing in CPSC421
(last modified September 27, 2014); these notes will be modified, and have
material added to them (especially exercises).
This material will be reviewed again later in the course
(see Chapters 4 and 5 of Sipser's text).

Blogs 
I will write a
blog
to say roughly what we are covering when and to make some additional
remarks regarding class material.
This blog is usually quite skeletal, and will be modified
throughout the term.
I will summarize the topics in the handout and in Sipser's textbook
here.

Homework 
All homework involving the text is based on the 3rd edition of Sipser's book.
Homework #1, due September 15: Problems 7.1.1, 7.1.2, 7.1.4,
7.1.9(3) of the
handout.
Graded out of 14 possible points.
Solutions.
Homework #2, due September 22:
Problems (7.1.4,) 7.1.5, 7.2.1, 7.2.3, 7.2.6.
Graded out of 10 possible points.
Solutions.
Homework #3, due September 29:
Problem 7.3.1, for the language 421Simple, for Axiom 2;
Problem 7.3.1, for the language 421Simple, for Axiom 4;
7.3.3(2), 7.3.4(2) (both 421Simple and a Turing Machine).
Solutions.
Homework #4, due October 10:
Sample Midterm Problems: 5,7,16,17.
Solutions.
No more homework until a week after the midterm.
Homework #5, due November 10:
Sipser's text: 7.22, 7.25, 7.29, 7.30.
Homework #6, due November 19:
Problems 2, 6, 7 from
our coverage of Sipser Chapters 8 and 9.
Homework #7 will not be collected or graded:
Problems 9, 10, 12, 13 from
our coverage of Sipser Chapters 8 and 9.
Homework #8 will not be collected or graded:
Some problems on regular languages (Chapter 1 of Sipser's textbook):
To Be Announced.

Office Hours 
Joel Friedman (Instructor):
by
appointment, unless posted otherwise.
Office hours for the week of Oct 2024:
October 20, 9:2010:20am in Mathematics Building, room 210,
October 21, 7:458:50am CS Building (ICCS), room 304.
Alireza ZakeriHosseinabadi (TA):
Thursdays 5:306:30pm and
Friday 4:305:30pm, both in ICCS, room X139.

Essay 
Students in CPSC 501 have an
essay due on the last day of class.
Choose any topic that goes beyond something done in this course, but
please get my approval. The following topics are fine:
(1) Fuller discussion of some of the paradoxes mentioned in the
handout, including: Godel's incompleteness theorems and Russell's paradox;
(2) Discussion of a number of different types of problems (including some
that may arise in practice?) known to be
undecidable or unacceptable (unrecognizable);
(3) Methods of showing that a language is not recognizable (how many
different methods are known, for example?);
(4) Discuss the Chomsky Hierarchy (e.g., explain why Type0 grammars yield
precisely all Turingrecognizable languages, what Type1 grammars
(context sensitive) give) (see the wikipedia page);

Other News 
The
textbook
Computational Complexity: A Modern Approach, by Arora and Barak
contains the "easy" PSPACEcomplete
language discussed in class, in Section 4.2, between Definitions~4.9 and
4.10.

