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 | Overview for this course. |
|---|---|
| Final Exam | 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. |
| Midterm | 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 and very briefly touches upon universal Turing machines and undecidability. Sample midterm 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). |
| Handout | We begin the course by talking about the Halting problem and related ``paradoxes'' 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 originally. |
| Sketchy Notes | 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. |
| Homework |
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.) Solutions. Homework #2, due September 30: Problems 11, 12, and 3. (You'll need an updated version of the handout for Problems 11 and 12.) Solutions. Homework #3, due October 7: Problems 5, 10, and 14 of the handout, and Exercise 3.8(b) of the textbook. Solutions. Homework #4, due Wednesday, October 19: Problems 3.11, 3.15, 3.16 of the textbook. Solutions. 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). Solutions. Homework #6, due Monday, November 21: Problems 7.21, 7.23, 7.27, 7.28. Solutions. |
| Office Hours | Joel Friedman (Instructor): by appointment, unless posted otherwise. |
| 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); |
| Readings/Links | |
| Other News | No news is good news. |
| UBC Math Home | | | Joel Friedman Home | | | Course Materials |