
CPSC 421/501 Page, Fall 2015
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.
Recent News 
We are now writing on the overhead projector and can provide
some of the contents (boards move from top right to top left to
bottom right to bottom left, since instructor is lefthanded):
2015_10_07,
2015_10_09,
2015_10_14,
2015_10_16,
2015_10_19,
2015_10_21,
2015_10_23,
2015_10_26,
2015_10_28,
2015_11_02,
2015_11_04,
2015_11_06,
2015_11_09,
2015_11_13,
2015_11_16,
2015_11_18,
2015_11_20,
2015_11_23,
2015_11_25,
2015_11_27,
2015_11_30,
2015_12_02,
2015_12_04.
(Slides are usually posted within a day of the class; slides
for future dates are never available.)

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 by covering Sections 14 of
Computability and SelfReferencing in CPSC421; this is a more general
treatment of Section 4.2 of Sipser's textbook.
We will then cover Turning machines,
parts of Chapters 3 and 4 of Sipser's textbook, and finish
the latter part of
Computability and SelfReferencing in CPSC421.
We continue with Chapters 57 and 9; regular languages (Chapter 1) and
contextfree languages (Chapter 2) will be covered briefly towards
the end of the course.

Midterm 
The midterm will be held during class hours on
October 30, 2015.
Here is
the midterm with solutions.

Learning Goals 
Learning goals along with sample exam problems are given
on the
learning goals webpage.

Handout 
We begin the course by talking about computability 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.

Homework 
All homework involving Sipser's textbook is based on the 3rd edition of
this book.
Homework #1, due Friday, September 25: Problems 7.1.1, 7.1.2, 7.2.1,
7.2.3, 7.2.7 of the handout
Computability and SelfReferencing in CPSC421.
Solutions.
Homework #2, due Friday, October 9
is given here.
Solutions.
Homework #3, due Friday, October 23: problems 3.11, 3.15 (b)(e),
3.16 (b)(d); and explain why Turingrecognizable languages are not
closed under complementation (use a fact from Chapter 4 and/or our
discussion in class).
Solutions.
Homework #4, due Friday, November 20
is given here.
Solutions.
Homework #5, due Friday, November 27
is given here.

Office Hours 
Joel Friedman, by appointment only;
Alireza Zakeri Hosseinabadi (Graduate TA, azakeri at cs dot ubc etc.):
Wed 4:305:30 ICICS X141,
Thu 5:306:30 ICICS 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 
No news is good news.

