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 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 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 Self-Referencing 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 3-7 and 9; regular languages (Chapter 1) and context-free 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 in DMP 110. Here is a draft of a sheet of notes that you will be given with the final exam; please let me know if you have questions, corrections, etc. Office hours before the exam: 2:30-4:00pm on Monday (Dec 1) in ICCS room 202, and 2:30-4:00pm on Tuesday (Dec 2) in Mathematics Building, room 210. For study material, you should look at
  • More sample midterm problems for material up to the midterm (this covers the textbook up to Section 7.2 in the textbook);
  • Sections 7.3-7.5 in the textbook (Cook-Levin Theorem and NP Completeness): sample exam problems are to determine if a language is NP-complete, using fairly straightforward reductions; see most of the problems in Section 7, including Homework 5 and, for example, 7.21, 7.23, 7.24, 7.26. The other sample exam problem would be to outline the Cook-Levin Theorem;
  • after Chapter 7: our coverage of Sipser Chapters 8 and 9 and our coverage of Sipser Chapter 1;
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 Self-Referencing 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:
  1. midterm 2004 (solution q4, solutions q1&2, solutions q3&5),
  2. final 04 (brief solutions to some of the problems),
  3. midterm 2007 (solutions, which refer to sol to HW 1 that year, and sol to HW 2 that year, ),
  4. final 2007,
  5. midterm 2009 (solutions),
  6. midterm 2010 (solutions),
  7. final 2010,
  8. midterm 2011 (solutions),
  9. final 2011,
  10. 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 Self-Referencing 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 Self-Referencing 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. Solutions: page one, page two.
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: you should be able to do (1)--(6) of our coverage of Sipser Chapter 1.
Office Hours Joel Friedman (Instructor): Office hours before the exam: 2:30-4:00pm on Monday (Dec 1) in ICCS room 202, and 2:30-4:00pm on Tuesday (Dec 2) in Mathematics Building, room 210.
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 Type-0 grammars yield precisely all Turing-recognizable languages, what Type-1 grammars (context sensitive) give) (see the wikipedia page);
Other News The textbook Computational Complexity: A Modern Approach, by Arora and Barak contains the "easy" PSPACE-complete language discussed in class, in Section 4.2, between Definitions~4.9 and 4.10.

UBC Math Home| Joel Friedman Home| Course Materials