CPSC 421/501 Page, Fall 2017

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 for 20% of the grade.

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

Overview This is an introductory course to Computer Science Theory. This overview describes the course content and covers various aspects class policy.
Textbook This course textbook is "Theory of Computation," by Michael Sipser, 3rd Edition; all homework from the textbook is based on the 3rd edition.
Additional Handouts Aside from the textbook, we will use the following short articles:
  • Directed Graphs and Asymptotic Tests, to which I'm currently adding exercises; the numbering of the exercises will likely change until Homework #1 is assigned.
  • Computability and Self-Referencing in CPSC421.
  • I have also written up some additional notes regarding class material, namely:
  • Tests for Language Regularity.
  • Midterm The midterm will be held during class hours on Wednesday, November 1, 2017. Location TBA.
    Boards and Slides Scan of boards for: 09_11, 09_13, 09_15, 09_18, 09_20, 09_22, 09_25, 09_27, 09_29, 10_02, 10_04, 10_06, 10_11, 10_13, 10_16, 10_18, 10_20,
    Reg Exp for Numbers Divisible by 3, from 10_02,
    Slides starting week of September 4.
    Roughly when topics began: Directed Graphs and Asymptotic Tests: 09_06. Computability and Self-Referencing: 09_18. DFA's (1.1 of [Sip]): 09_25. NFA's (1.2): 09_27. Reg Exp (1.3): 10_02. Nonregular (1.4): 10_04.
    Homework All homework involving Sipser's textbook is based on the 3rd edition of this book. Homework will be submitted to www.gradescope.com; instructions to follow.
    Homework #1 (Due Thursday September 14, 11:59pm) Exercises A.1(3,4,6), A.2(1,2), A.3(1), A.4(1b,1d,2d), A.5(2) from Directed Graphs and Asymptotic Tests.
    Homework 1 Solutions.
    Homework #2 (Due Thursday September 21, 11:59pm) Exercises A.8, A.9, A.11; Bonus Exercises: A.12, A.14 from Directed Graphs and Asymptotic Tests.
    Homework 2 Solutions.
    Homework #3 (Due Thursday September 28, 11:59pm) Here is Homework #3; it has a statement of some homework policy.
    Homework 3 Solutions.
    Homework #4 (Due Thursday October 5, 11:59pm) Here is Homework #4.
    Homework 4 Solutions.
    Homework #5 (Due Thursday October 12, 11:59pm) Here is Homework #5.
    Homework #6 (Due Thursday October 19, 11:59pm) Here is Homework #6.
    Homework #7 (Due Thursday October 26, 11:59pm) Here is Homework #7; it refers to my Final Exam from 2014 and Final Exam from 2011.
    Homework #8 (Due Thursday November 9, 11:59pm)
    Office Hours There is an online discussion of this course on www.piazza.com.
    In person office hours:
    Joel Friedman (Instructor): Tuesday, 2-3pm, in Mathematics Building, room 210, or by appointment.
    Rachel (TA): Tuesday, 1-2pm, in X337,
    Noah (TA): Friday, 11-12pm, in X141,
    Sharon (TA): Monday, 1-2pm, in Table 1, DLC
    TA office hours are announced on piazza and may change according to polls taken there; they will probably stabilize in a week or so.
    Other News No news is good news.

    UBC Math Home| Joel Friedman Home| Course Materials