CPSC 421/501 Page, Fall 2011
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 up-to-date 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 for this course.
The final exam will be on Wednesday, December 7, at noon in
Forest Sciences Centre, room 1221.
Office hours before the exam will be on Tuesday, December 6,
12:00-1:30pm, in the Mathematics Building, room 210
( ** not Computer Science ** ).
Here are some
extra sample problems for the final
exam; the homework, midterm,
and sample midterm questions should also be useful for studying.
Additional material to be covered since the midterm includes:
(1) P, NP, Cook-Levin, NP-completeness, and poly-time reductions,
(2) The following topics from Chapter 1: the definition of a DFA,
and the Myhill-Nerode Theorem.
The midterm will take place on Friday, October 28, 2011.
It will cover all material covered up to Friday, October 14, 2011;
this includes Turing machines and universal Turing machines, and
how Turing machines fit the axioms in the handout; this does not
include multi-tape Turing machines (covered on Monday, October 17).
In other words, we are covering (1) all the handout, (2) Section 3.1 of the
textbook, (3) how to encode a Turing machine as a natural Turing machine
and therefore as a string,
(4) the constrction of a universal Turing machine; notice that Section 4.2
of the text also covers the counting arguments of the handout
briefly touches upon universal Turing machines and undecidability.
questions are now available.
The midterm and solutions
are no available; the scaling piecewise linearly interpolates, sending
0 to 0, 10 to 50, 20 to 72, and 40 to 100
(hence replaces x by: 5x if x <= 10, 2.2 x + 28 if 10 <= x <= 20,
and 1.4 x + 44 if x >= 20).
We begin the course by talking about the Halting problem and related
with the handout
Ruining the Surprises in CPSC421
(last modified September 28, 2011); these notes
may be modified, and
this material will be reviewed again later in the course
(see Chapters 4 and 5 of Sipser's text);
here is the
original handout that was on the website
We shall first follow the handout and then the text. I make some
very sketchy notes
on roughly what we will cover roughly when.
These notes are a rough plan, and may be modified many times
during the semester; material may be added and/or deleted.
All homework involving the text is based on the 2nd edition.
Homework #1, due September 23: Problems 1,4,6 of the handout.
(Because we spent more time on counting, Problem 4 can be handed in with
Homework #2, due September 30: Problems 11, 12, and 3.
(You'll need an updated version of the handout for Problems 11 and 12.)
Homework #3, due October 7: Problems 5, 10, and 14 of the
handout, and Exercise 3.8(b) of the textbook.
Homework #4, due Wednesday, October 19: Problems 3.11, 3.15, 3.16
of the textbook.
Homework #5, due Monday, November 14: Problems 7.7, 7.12, 7.36, and
7.37. (7.36 and 7.37 probably don't deserve the stars that they get
in Sipser's text).
Homework #6, due Monday, November 21: Problems 7.21, 7.23, 7.27, 7.28.
Joel Friedman (Instructor):
appointment, unless posted otherwise.
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 Type-0 grammars yield
precisely all Turing-recognizable languages, what Type-1 grammars
(context sensitive) give) (see the wikipedia page);
No news is good news.