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.
| Final Exam |
Our final exam is scheduled for Tuesday, December 5, 7pm, in LSK 201.
Your may bring 2 two-sided 8.5 x 11 sheets of notes for the exam.
Here is a new webpage regarding the final exam coverage and sample problems. Office hours before the exam:
|
|---|---|
| Midterm |
Here is
our midterm
and
solutions.
The median score on the midterm was 26.5 (out of 50). Marks are scaled into percentages as follows: if x is your midterm score (out of 50), your scaled mark is S(x) where (1) if 0 <= x <= 15, then S(x)= x(50%/15), (2) if 15 <= x <= 35, then S(x) = 50% + (x-15)(30%/20), and (3) if 35 <= x <= 47, then S(x) = 80% + (x-35)(20%/12). In other words, S(0)=0%, S(15)=50%, S(35)=80%, and S(47)=100%, and all other values of S are obtained by piecewise linear interpolation. |
| Midterm Practice | Here are some additional practice problems for the midterms; solutions will not be provided; some of these will be solved in class on Monday. |
| 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:
|
| 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,
10_23,
10_25,
10_27,
10_30,
11_03,
11_06,
11_08,
11_10,
11_15,
11_17,
11_20,
11_22,
11_24,
11_27,
11_29,
12_01.
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 languages: 10_04 (asymptotic tests and Pumping Lemma (1.4)), 10_06 (Myhill-Nerode). Turing machines (3.1): 10_13 (time and space: 10_18). Multi-tape machines (and countably many algorithms): 10_20. A_TM is undecidable (4.2): 10_25. TIME (7.1): 10_27, P and NP (7.2, 7.3): 10_27. Cook-Levin Thm (7.4): 11_03. Oracle Machines (in 6.3 and 9.2): 11_08. SUBSET-SUM, NP-completeness (7.4): 11_08. PSPACE, NPSPACE (8.1, 8.2): 11_17. SNEAKY-NTM, SNEAKY-PSPACE (Easy complete languages): 11_20. |
| 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 5 Solutions. Homework #6 (Due Thursday October 19, 11:59pm) Here is Homework #6. Homework 6 Solutions. 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 7 Solutions. Homework #8 (Due Thursday November 16, 11:59pm) Here is Homework #8. Homework 8 Solutions. Homework #9 (Due Thursday November 23, 11:59pm) Here is Homework #9. Homework 9 Solutions. Homework #10 (Due Thursday November 30, 11:59pm) Here is Homework #10. Homework 10 Solutions plus diagram of Turing machine in Problem 3. |
| Office Hours |
There is an online discussion of this course on
www.piazza.com.
In person office hours during the term: 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 |