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 up-to-date information on the course(s) and supersedes any other document.
| Final Exam | The final exam for this class will take place on December 8 at 8:30am in MCLD 228. Addtional office hours before the exam: 3:00-5:00pm on Friday (Dec 4), Course Review; 3:00-5:00pm on Monday (Dec 7), Problem Solving; both in ICICS X836. Topics Covered: See learning goals webpage. |
|---|---|
| Board Scans | 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 left-handed): 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 1-4 of Computability and Self-Referencing 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 Self-Referencing in CPSC421. We continue with Chapters 5-7 and 9; regular languages (Chapter 1) and context-free 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 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. |
| 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 Self-Referencing 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 Turing-recognizable 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. Solutions. |
| Office Hours | Additional office hours before the final exam: Friday, December 4, 3-5pm, Course Review (Alireza Zakeri Hosseinabadi), location ICICS X836. Monday, December 7, 3-5pm, Problem Solving, Joel Friedman and Aireza Zakeri Hosseinabadi, location ICICS X836. Alireza Zakeri Hosseinabadi (Graduate TA, azakeri at cs dot ubc etc.): Wed 4:30-5:30 ICICS X141, Thu 5:30-6:30 (used to be ICICS X139, special to Dec 3: ICICS X836). |
| 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 | No news is good news. |
| UBC Math Home | | | Joel Friedman Home | | | Course Materials |