CPSC 421/501 Page, Fall 2021

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 presentation/report to give during the last two weeks of classes.

The current (end of July) plan is that the class this term will BEGIN FULLY IN-PERSON.

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 Dec 22: The final exam will be held in-person, in both DMP 110 (our usual classroom) and DMP 310 or only DMP 310. Seating is alphabetical by last name; room assignments will be posted on the entrance to DMP.

Dec 20: The final exam is planned to be held in-person, in both DMP 110 (capacity 120) and DMP 310 (capacity 160) or only DMP 310; stay tuned for details. You may apply to the dean of your faculty, director of your school, etc., for a deferred exam if your personal circumstances make it unreasonable to attend the in-person exam (and I will respect whatever choice you make).

Dec 16: Final Exam Study Guide 2021 is finished, aside from possibly some additional remarks at the bottom.

Dec 14: All homework solutions posted. Final Exam Study Guide 2021 should be finished today or tomorrow.

Dec 9: Homework solutions through Homework 8 posted. Final Exam Study Guide 2021 under preparation.

Dec 6: Office hours for the rest of the term announced below; office hours cancelled on Wednesday, Dec 8.

Dec 1: Homework 10 will not be collected. Remaining classes begin with presentations, then with group "office hours." The handout "The Cook-Levin and Theorem and how to solve and not to solve P versus NP" in preparation, preliminary version to be released in a day or two. Problem 8.7.4(b) of Uncomputability OR Ruining the Suprises in CPSC421: assigned on Homework 9, was edited.

Nov 17: Consult piazza.com for last minute cancellation of office hours.

Nov 2: Joel's office hour, Wednesday, Nov 3, 4-5pm, will take place in ICCS 304.

Oct 29: Exam Study Guide (Currently for Midterm 2021) is under construction. Homework 6: Solution to Problem 1 and solutions to Problems 2-6.

Oct 28: To study for the midterm and (in December) the final, see this study guide.
Office hours before the midterm, i.e., the week of Nov 1-5: Amir's Zoom office hour on Tuesday will be 6-7pm. Joel will have an additional office hour 4-5pm on Wednesday.

Oct 21: The midterm will cover material up to class today on regular languages, and excludes Turing machines. Homework 6 will be assigned on Oct 21 and due Thursday, Oct 28 at 11:59pm; solutions will be released on Friday, Oct 29.

Sept 28: No class on Sept 30 due to National Day for Truth and Reconciliation. For relavent events at UBC, you may check UBC's Orange Shirt Day website; in particular, members of the UBC STEM (Science, Coding, and Engineering) community, families and those in solidarity are welcome to participate in an Intergenerational March to commemorate Orange Shirt Day, September 30, 2021, 11:45am-2pm. A related event on Sept 29 is UBC STEM's 94 TRC Calls to Action (registration and volunteers requested).

Welcome back! Looking forward to looking at humans rather than a Zoom screen! First class will be Thursday, September 9; location (HDP) Hugh Dempster Pavilion, Room 110.
Make sure to visit Canvas at UBC and to navigate to our Zoom application, in case we need to revert to Zoom at some point (no Zoom meetings are scheduled at this point); I do not intend to record any Zoom classes that I may need to give, and we may need to transition to Zoom on short notice. If you have any issues, please post to our course piazza page.
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).
In-Person Learning The current plan (end July) is for CPSC 421/501 to begin as an in-person course, with the same structure as it had before the pandemic. I have returned to in-person research and work on campus with my students and colleagues as of mid-July; I cannot ovestate how rewarding (and more efficient) this is; I seemed to have forgotten this after some 15 months of remote/Zoom work...
UBC COVID-19 Resources UBC is maintaining a website for all COVID-19 resources, guidelines, etc. At present (late July) there is a lot of vagueness regarding the return to in-person learning at UBC; the UBC Faculty Association is seeking some clarity.

Understandably, UBC has neither a well-tested "Return to In-Peron Learning after a 1-10 Year Long Pandemic Plan" currently in place, nor a "Best Practices for a Return to In-Peron Learning after a 1-10 Year Long Pandemic" guide -- it's no one's fault. I trust that in the coming months and years the UBC community will come up with something reasonable.
COVID-19 Safety Issues Many students are understandibly uncomfortable with the anticipated full return to in-person learning this September and the uncertainty it brings. Here are some considerations.

During most of the pandemic, British Columbia maintained the laudable goal of keeping its public K-12 schools open, despite the risks involved and the terrible burden imposed -- for various reasons -- on teachers, custodians, and other school staff. As of September 2021, it's now UBC's turn to open and experience first hand the rewards (and risks) of in-person learning.

CPSC 421/501 will switch to remote/Zoom learning -- at least temporarily (and likely without recording the classes) -- if UBC closes as a whole, or I deem that COVID-19 event(s) affecting the CPCS 421/501 population require this switch (e.g., should I self-isolate). I would greatly appreciate knowing of any such events, but am aware of serious privacy considerations. I do not know if UBC could -- legally or ethically -- request or require such information, but I trust that UBC would treat any such information with the utmost respect for your privacy, as would I.

I remain cautiously optimistic for a safe and rewarding academic year at UBC, and for worldwide control of the pandemic within some 3-6 years; I hope that we may all learn from one another.
Returning to UBC Many of you are processing grief and have new responsibilities and priorities because of the pandemic. I hope that you make the right decision for you about whether or not to return to campus and when, and I will personally respect your decision; of course, I'd be happy to see you in person.
Taking CPSC 421/501 Remotely? At present I am treating CPSC 421/501 as I did before the pandemic: e.g., no video or audio class recordings, but I'll post the "board scans" from my iPad; I make (occasional) unrecorded whiteboard scribbles. There are no prerecorded video or audio lessons.

To get an idea of the course material and exams, you can look at my CPSC 421/501 courses from previous years on my Course Materials webpage; the material covered and the exams will likely be a bit different this year.

My understanding is that all exams must be attended in-person unless UBC decides otherwise.

I think you would have a much better experience by attending as many in-person classes as reasonably possible. I am aware that timely flights to Vancouver may be difficult to find right now (end July).
Diversity in Masking and Vaccination People have different views regarding masking, vaccines, etc. I urge tolerance regarding such diversity: many people are unvaccinated due to medical reasons (e.g., immune issues, past trauma, etc.) or cultural reasons (e.g., past or inheritied trauma based on actions of various governmental agencies -- even some "in the name of science").

Furthermore, many younger folks in Canada are used to consulting their peers to form reasoned opinions, and have never lived through events like wars or pandemics; for them the abundance of contradictory advice from scientists and pharmaceutical companies regarding COVID-19 (e.g., Pfizer versus Fauci regarding third doses, July 2021) is confounding, and they are not used respecting instructions from particular people the age of their parents, grandparents, or great-grandparents.

Most views I've heard are not particularly difficult to understand, and worthy of at least some degree of empathy. I regard all views as worth considering, and hope that this fall we may all learn from one another.
Overview This is an introductory course to Computer Science Theory. This policy webpage describes the course policy, including the prerequisites and grading scheme.
To get an idea of the course material and exams, you can look at my CPSC 421/501 courses from previous years on my Course Materials webpage; the material covered and the exams will likely be a bit different.
References: Textbook and Handouts 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 have used the following articles from my past CPSC 421/501 (which may undergo minor revisions, corrections, etc.):
  • All but Section 7.9 of
    Uncomputability OR Ruining the Suprises in CPSC421 (last revised December 1, 2021 at 14:54, i.e., 2:54 pm).
  • This article on the Myhill-Nerode theorem. (We will use the Myhill-Nerode theorem instead of the Pumping Lemma in Section 1.4 of the textbook.)
  • We covered Sections 1-3 and part of Section 4 of article on
    The Cook-Levin Theorem and how to solve and not to solve P versus NP, (last revised December 6, 2021 at 11:05, i.e., 11:05am). Other sections of this article will indicate what you might expect to see in a grad topics course in complexity theory and/or the motivation for the topics studied therein.
    • Midterm and Final Exam The final exam study guide for 2021 is finished except for possible corrections and minor edits.
    Here are solutions to our midterm in 2021.
    Here is the Midterm 2021 Study Guide. The final exam will be held on Wednesday, December 22, 2021, 12pm, in either rooms DMP 310 and DMP 110, or only DMP 310; stay tuned for details.
    The midterm was held during class hours on Thursday, November 4, 2021. [It covered material introduced up to Thursday, October 21.] The location was in our usual classroom.
    Readings and Boards Scans The following is the rough class plan and corresponding readings; it may be modified.
    • Roughly 2 weeks: Uncomputability OR Ruining the Suprises in CPSC421. This includes material overlapping with Section 4.2 of [Sip].
      Board scans: 09_09: course policy, paradoxes (two different topics, hopefully).
      09_14: student feedback, course policy, a Godel statement, pigeon hole principle and variants, review of strings, surjections, etc.
      09_21: countable sets (finite and countably infinite), more on bijections, |S| < |T|, interpretations of strings/words and computer programs, one cannot describe all bijections from the naturals or integers to themselves, the rationals are countably infinite.
      09_23: Countability, etc., will wait until we cover Section 4.2. Sample for Homework 2, involving Profs. Humus, Pita, and Falelel, and the foods: humus (close relative of North American "hummus"), pita, and falafel. Local, randomized counting, and an application to candy.
    • Roughly 2 weeks: Chapter 1 of [Sip] (Regular languages); we will replace the Pumping Lemma in Section 1.4 with this article on the Myhill-Nerode theorem. In Section 1.3 we will not cover the algorithm to convert a DFA to a regular expression; we do explain that (1) it is not as often needed in practice as the reverse algorithm, and (2) it yields very large expressions for small DFA's like a DFA for the language {0,3,6,9,12,...} (from the 2019 section).
      09_28: National Day for Truth and Reconcilliation (concerning Canada's residential school system and related abuses), aka Orange Shirt Day: comments and UBC STEM events on September 30. DFA's and regular languages: technical definition of a DFA, depicting DFA's, some examples of regular languages, the non-regular language of words of prime length.
      10_05: Goldbach conjecture stated as equality of concatenation of languages over a one-letter alphabet; one-letter DFA's, regular and non-regular languages; review of DFA notation; classification of regular languages over a one-letter alphabet. Start discussion of DIV-BY-3.
      10_07: Why you should not sneer at single-letter alphabets; sub-linear time/space algorithms and unary representation. More on DIV-BY-3 and its variants. NFA's: examples in producing NFA's for L^* via a DFA for L.
      10_12: More examples of regular languages; formal definition of an NFA; the DFA associated to an NFA; the language of words over {a,b} whose m-th last symbol is an "a", an NFA for this language, and the reverse of this language and a DFA for that.
      10_14: Overview of Chapter 1 machine-by-machine versus language-by-language. Discussion of C_3 (words over {a,b} whose 3rd last symbol is an "a") and converting its NFA to DFA; observations about states reached and not reached in this DFA. Begin "accepting futures" of a word with respect to a language and begin regular expressions.
      10_19: Are natural languages first written then spoken, and are formal languages first written as a DFA and then translated (using the algorithm in 1.3 of [Sip]) into a regex (regular expression)? Theorem statement about languages described by regex's and recognized by DFA's. Example of DIV-BY-3 as a regular expression. Example of C_{10} and its reverse, DFA's and regex's. Regex's as in 1.3 of [Sip], and abbreviated forms. Theorem regarding converting a regex into an NFA. The Myhill-Nerode theorem: definition of AccFut_L(w), and how many states needed to recognize L (infinitely many means that L is non-regular). Example of {a^3,a^6,a^9,...}.
      10_21: Midterm covers up to today's class. More on Myhill-Nerode, the example {a^0,a^3,a^6,a^9,...} compared to {a^3,a^6,a^9,...}. The example {0^n 1^n}. The example C_2, with a view to a systematic understanding, so that C_k with k>2 can be similarly understood.
    • Roughly 1.5 Weeks: Chapter 3 of [Sip] (Turing Machines).
      10_26: Overview of Turing machines (one-tape, multi-tape, non-det, and oracle). Time complexity. Formal definition of a one-tape machine as DFA with additional power. Goals: see that poly time on a TM = poly time in the usual sense, and convincing yourself that you could build a universal TM. Example: bulding a Turing machine for C_2, conventions for diagrams of Turing machines.
      10_28: Midterm materials schedule. TM's (Turing machines): review of goals (universal machines and P). More formalities regarding TM's, "high-level vs. imp-level vs. formal." Finish C_2. TM for PALINDROME.
      11_02: Motivation for multi-tape: PALINDROME on single tape requires at least quadratic time. Begin multi-tape TMs. Discussion of supplemental midterm practice questions 5 and 6.
      11_09: Broad outline of multi-tape / non-det / oracle TM's (and any combo of these three), the language MULT, multi-tape machines for PALINDROME, MULT, and start Universal TM's.
      11_16: Broad outline of oracle TM's: HALT, HALT^HALT, HALT^HALT^HALT, ... and Baker-Gil-Soloway Theorem. Standardized TM's Construction of universal TMs.
    • Roughly 0.5 Weeks: Chapter 4 of [Sip] (Universal Turing machines, undecidable and unrecognizable problems).
      11_18: Broad outline of universal and "delightful" Turing machines, undecidability of ACCEPTANCE ahd HALTING, abstract setting of Program-Input systems as maps P x I -> {yes,no,loops}, enhanced P-I systesm, oracle TM's. Σ_{Wow!}={0,1,#,L,R}, and review of standardized TM's as encodable as words/strings over Σ_{Wow!}. Standardized alphabets and TM's. Side-by-side abstraction (enhanced P-I systems) and Turing machines, the acceptance problem, ACCEPTANCE, and the halting problem, HALT. Abstract universal programs and universal Turing machines. Abstract delightful programs and delightful Turing machines. Delightful Turing machines necessary loop on "themselves" as input. Corollary: Any universal program must attain the value loops on some input, and hence no universal program is a decider (hence ACCEPTANCE is undecidable).
      11_23: End of coverage of Section 7 (with 7.7 and 7.9 omitted this year) of Uncomputability OR Ruining the Suprises in CPSC421: Expressive Program-Input systems: motivation, axioms needed to show that ACCEPTANCE is undecidable. Universal and delightful programs in the abstract setting. The HALT hierarchy (mentioned last time).
    • Roughly 0.75 weeks Topics from Chapters 7 and 9 of [Sip] (P and NP, the Cook-Levin Theorem).
      11_25: Rough description of what [Sip] Chapter 9 says about how to solve and not to solve P versus NP. Graph colourings. Standardized graphs, 2COLOUR and 3COLOUR. Polynomial time decidable languages. Boolean formulas and SAT. NP described as polynomial verifiable languages.
      11_30: Review of the language SAT. Configuration representation of a 1-tape TM as a string over Σ_{config} = the disjoint union of Q and Γ. The nearest neighbours time evolution of configurations as a function trans Σ_{config}^3 to Σ_{config}. The Boolean logic expression for the correctness of n^k time steps of a configuration of n^k cells. Briefly remarks on Turing machines as circuits.
      CPSC 501 Presentation of Jerry Wang on Context-Free Grammars: slides of talk and of CYK Execution Trace.
    • 1 Week: More presentations (beginning at the start of class, roughly 40-60 minutes in total), followed by "office hours" (I will take questions about homework, other sample exam problems, etc.)
      12_02: Announcements regarding admin matters: midterm and homework solutions, office hours, and final exam.
      CPSC 501 Presentation of Mia Kramer and Sophie MacDonald on Quantum Computing: slides of talk and accompanying accompanying Pluto notebook.
      The ".jl" file is the Pluto notebook; instructions for Pluto can be found here.
      12_07: Administrative remarks.
      CPSC 501 Presentation of Zack Grannan on Term Rewriting: slides of talk.
      CPSC 501 Presentation of Grigorii Guz on Kolmogorov: slides of talk.
    Homework Homework will be assigned most weeks, typically due on gradescope at 11:59pm on Wedesnday. We may grade only some of the problems on the homework. 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.
    You will need to connect to the course Gradescope page via UBC Canvas.
    Individual and group homework will be assigned.
    Homework 1: There is no individual Homework 1. Group Homework 1 (groups of up to four people): Problems 8.1.1, 8.3.1, 8.3.2, 8.3.4, 8.3.9, 8.3.10 of Uncomputability OR Ruining the Suprises in CPSC421. Homework 1 is due on gradescope.com at at 11:59pm on Wednesday, September 22. Solutions.
    Homework 2: There is no individual Homework 2. Group Homework 2 (groups of up to four people): Problems 8.3.5 -- 8.3.8 of Uncomputability OR Ruining the Suprises in CPSC421. and Problems (1)--(3) of Group Homework 2 of last year's course (i.e., Fall 2020). Homework 2 is due on gradescope.com at at 11:59pm on Wednesday, September 29. Solutions.
    Homework 3: There is no individual Homework 3. Group Homework 3 is due on gradescope.com at 11:59pm Wednesday, October 6. Solutions.
    Homework 4: Will have an individual and group Homework 4, due on gradescope.com at 11:59pm Wednesday, October 13. Individual Homework 4 will consist of: Problem 1: Problem 1 on the Individual Homework 3 of 2020, and Problem 2: Exercise 1.6(b) of [Sip]. Group Homework 4 is Exercises~6.1.1 to~6.1.5 in This article on the Myhill-Nerode theorem. Individual homework solutions Group Homework Solutions.
    Homework 5: Individual Homework 5 (Problem 1 will not be collected), Group Homework 5 are due on gradescope.com at 11:59pm Wednesday, October 20. Individual homework solutions and Group homework solutions Problems 1-2, and Group homework solutions for Problems 3-5 are the same as Group homework solutions for Problems 3-5 from here.
    Homework 6: There is no individual homework 6. Group Homework 6 is due on gradescope.com at 11:59pm Thursday, October 28. Solution to Problem 1 and solutions to Problems 2-6.
    Homework 7: Individual Homework 7 and Group Homework 7 are due on gradescope.com at 11:59pm Friday, November 19. Solutions.
    Homework 8: No Individual Homework 8. Group Homework 8: is due on gradescope.com at 11:59pm Thursday, November 25. Problems 8.5.1, 8.5.3, 8.5.5, 8.5.6, 8.6.2 from a Nov 18 updated version of Uncomputability OR Ruining the Suprises in CPSC421. Solutions.
    Homework 9: No Individual Homework 9; Group Homework 9 is due on gradescope.com at 11:59pm Thursday, December 2. Solutions.
    Homework 10: Homework 10 will not be collected. Solutions.
    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.
    Office hours Dec 6-10: As usual on Monday and Tuesday, no office hours Dec 8-10.
    Office hours Dec 13-17: Dec 13: Amir, 11:30-12:30, Zoom only. Dec 16: Joel, 9:45-11:15am, in-person, ICCS x561. Dec 17: Hassan, 8:30-10am, Zoom only.
    Office hours Dec 20-21: Dec 20: Hassan, 8-9am, Amir 11am-12pm, Zoom only. Dec 21: Joel, 10-11:30am, format TBA (in-person, ICCS 238, assuming the ICCS building is open during these hours to all students; otherwise Zoom only).

    Office hours starting Sept 20:, which you can access through our UBC Canvas course website, are as follows:
    Joel (Instructor): Tuesday, 3:45-5:15pm, ICCS x561, in-person only.
    Amir (TA): Tuesday, 11am-12pm, ICCS X337 and Zoom (hybrid). Tuesday 8-9pm, Zoom. Wednesday 12:30-1:30pm, ICCS X241 and Zoom (hybrid).
    Hassan (TA): Monday 11am-12pm, ICCS X239, in-person only. Wedesnday, 3-4pm, ICCS X239 and Zoom (hybrid).
    Nov 17: Consult piazza.com for possible last minute cancellation of office hours. Nov 17: Consult piazza.com for possible last minute cancellation of office hours.
    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 Centre, privileged to work with the Musqueam First Nation (recently, as of mid-August, investigating St. Paul's Indian Residential School site [Content warning: This post discusses Indian residential schools.]); this also includes 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.
    Relevant Dates Class Starts: Sept 9. Class cancelled by instructor: Sept 16. Drop/Withdrawl: Sept 27. National Truth and Reconciliation Day (no class): Sept 30. Our midterm: Nov 4. Midterm Break: Nov 10-12 Remembrance Day (no class): Nov 11. Last day of class: Tuesday, December 7. Exam Period: Dec 11-22. Our final exam: Dec 22.

    UBC CS Home| Joel Friedman Home| Course Materials