CPSC 421/501 Page, Fall 2019

This page concerns CPSC 421 Section 101 and CPSC 501 Section 101. The courses have been combined, except that CPSC 501 students have an additional essay to write for 20% of the grade.

This page has the most up-to-date information on the course(s) and supersedes any other document.

Materials below may have errors! Errors will be corrected either here or in class. If you are not attending my classes: use these materials at your own risk!

News	The final exam is on Dec 10, Tuesday, at 7pm in DMP 310. See final exam study guide just below. Office hours in December: Dec 3 (Tue): Joel (location ICCS X561), 3-4pm. Dec 4 (Wed): Joel (location ICCS X530), 3-4pm. Dec 5 (Thu): Adam: 1-2:30pm (DLC, Table 6). Dec 6 (Fri): Joel (location ICCS 104), 10:30-11:30am. Dec 6 (Fri): Adam: 2-3:30pm (DLC, Table 6). Dec 9 (Mon): Joel (location ICCS 104), 9:30-11:00am. Dec 9 (Mon): Adam 1:00-2:30pm (DLC, Table 6). Dec 9 (Mon): Yuchong (location ICCS X341), 3:00-4:30pm. Dec 10 (Tue): No office hours. Final exam at 7pm in DMP 310.
Final Exam Study Guide	Your may bring 2 two-sided 8.5 x 11 sheets of notes for the exam. Practice problems for the final exam include all homework problems for credit, the study guide for the midterm, plus the following study guide for the final.
Midterm Study Guide	Our midterm will be on Wednesday, October 30, during class hours (3-4pm). The location is SWNG 121 (SWNG is located at West Mall 2175). Topics covered on the midterm: Self-Referencing, Uncountability and Uncomputability in CPSC 421; Chapter 1 of [Sip] plus the Myhill-Nerode theorem explained in this article, but with Section 1.4 omitted. Chapter 3 of [Sip], specifically: all of 3.1, and the part of 3.3 after Hilbert's problem (i.e., describing graphs, Turing machines, etc.) [3.2 is omitted, including multi-tape Turing machines]. Practice problems for the midterm include all homework problems for credit, and this additional midterm practice (problems may be added to this list). Solutions will not be released; some solutions or hints will be given to problems that do not resemble anything assigned on the homework or solved in the textbook. Here are solutions to the mideterm.
Overview	This is an introductory course to Computer Science Theory. This policy webpage describes the course policy, including the prerequisites and grading scheme.
References	The required course textbook is "Theory of Computation," by Michael Sipser, 3rd Edition; all homework from the textbook is based on the 3rd edition. Tentatively we will cover most of Chapters 1, 3-5, and 7, and part of Chapters 8 and 9. Aside from the textbook, we will use the following article(s): The course will begin with material from: Self-Referencing, Uncountability and Uncomputability in CPSC 421; this version is a draft which may modified. Some other topics covered in class are not covered adequately (or at all) by the textbook and handouts; and students should use class notes for these topics: This article on the Myhill-Nerode theorem. (We will skip Section 1.4 of the textbook on the Pumping Lemma.) These notes on SNEAKY-NP, a language that is NP-complete for simple reasons, and SNEAKY-PSPACE, that is similarly PSPACE-complete.
Midterm	The midterm was held during class hours on Wednesday, October 30, 2019. Here are solutions to the mideterm.
Readings and Boards Scans	Sept 4-16: Self-Referencing, Uncountability and Uncomputability in CPSC 421; this is similar to (but goes beyond) parts of Chapter 0 of [Sip] and the part of Section 4.2 of [Sip] on diagonalization. Board scans: 09_04, 09_06, 09_09, 09_11, 09_13, 09_16. Sept 18 - Oct 2: Chapter 1 of [Sip] (Regular languages); we will omit Section 1.4 and instead cover this article on the Myhill-Nerode theorem. Board scans: 09_18, 09_20, 09_23, 09_25, 09_27, 09_30, 10_02. On Oct 2 we derived a regular expression for DIV-BY-3. Starting Oct 4: Chapter 3 of [Sip] (Turing Machines, Descriptions of Problems). Board scans: 10_04, 10_07, 10_11, (much of) 10_16. Starting Oct 16: Chapter 4 of [Sip] (Universal Turing machines, Decidability); more examples of undecidable problems (some in Chapter 5 of [Sip]). Board scans: (some of) 10_16, 10_18, 10_21, 10_23. Starting Oct 25 (roughly 2 weeks): Chapter 7 [Sip] (P and NP). Board scans: 10_25, 10_28, 11_01, 11_04, 11_06, 11_08, 11_13. Starting Nov 15 (roughly 1.5 weeks): Chapter 8 [Sip] (Space), Sections 1-3. Board scans: 11_15, 11_18. 11_20. On 11_22 we discussed a "sneaky" language that is NP-complete for simple reasons (but is otherwise not interesting), and mentioned its "sneaky" counterpart that is PSPACE-complete. These notes are a writeup of what was discussed. Starting November 25 (roughly 2 classes): Oracle Turing machines, co-NP, P^SAT contains NP and co-NP, and half of the Baker-Gill-Soloway (Section 9.2): for any PSPACE language, B, we have P^B = NP^B. Board Scans: 11_25, 11_27, 11_29, plus some notes made on the 2017 Final Exam.
Homework	Homework will be assigned most weeks, posted on Thursday and due the next Thursday (at 11:59pm). Late homework will not be accepted; however, your three lowest scores will be dropped in the overall homework computation. All homework involving Sipser's textbook is based on the 3rd edition of this book. Homework will be submitted and graded using gradescope.com. I will enroll you in gradescope.com, using the name "A Student" and your "a1b2c" at ugrad.cs.ubc.ca email address. Homework generally consists of (1) exercises for credit, (2) optional (and more difficult) exercises not for credit, and (3) some sample exercises with solutions (to give you an idea of how much detail your explanations should have). Homework 1 is due on gradescope.com at 11:59pm Thursday, September 19. Solutions. Homework 2 is due on gradescope.com at 11:59pm Thursday, September 26. Solutions. Homework 3 is due on gradescope.com at 11:59pm Thursday, October 3. Solutions. Homework 4 is due on gradescope.com at 11:59pm Thursday, October 10. Solutions. Homework 5 is due on gradescope.com at 11:59pm Thursday, October 17. Solutions. Homework 6: Problems 1 and 2 on Midterm 2017 [the format of Midterm 2019 will likely be similar, but the topics covered in 2017 and 2019 differ], and Problems 1(d), 1(e), and 6 on additional midterm practice. Solutions to Problems 1 and 2 of Midterm 2017 are here; the soltion to the other two problems are here. Homework 6 will not be collected or graded. Homework 7 is due on gradescope.com at 11:59pm Thursday, November 7. Solutions. Homework 8 is due on gradescope.com at 11:59pm Thursday, November 14. Solutions. Homework 9 is due on gradescope.com at 11:59pm Thursday, November 21. Solutions. All other homework will not be collected (or graded). Recommended homework/study: Final Exam 2017, all problems except the last true/false question of problem 1 (see the study guide for the final). Additional homework/study: other problems on this study guide.
Piazza and Office Hours	There will be an online discussion of this course on www.piazza.com; use this link to sign up (for both CPSC 421 and 501). Please post all questions related to the course material to our piazza site. For office hours in December, please see the top of this page.
Diversity and Equity	UBC is trying in earnest to encourage diversity and alleviate biases and inequities to which some members of its community are subjected; this includes, for example, UBC's Indian Residential School History and Dialogue Center, and well as the Computer Science Department's various programs described on its Diversity in CS webpage. I try to act reasonably free of bias; for example, I do not view sexual orientation or gender as set in stone from birth or as classified by some fixed, finite set of choices; I try to use language accordingly. I will undoubtedly goof upon occasion, and I welcome feedback on these and related matters.

UBC CS Home

Joel Friedman Home

Course Materials