News

• Dec 7: Week 13 tutorial handout is posted below. Tutorial solution will also be posted on Piazza
• Nov 29: Homework 6 is now posted. Note that it is due on Wednesday, a day earlier than usual.
• Nov 25: Week 12 tutorial handout is posted below. Tutorial solution will also be posted on Piazza
• Nov 19: Week 11 tutorial handout is posted below. Tutorial solution will also be posted on Piazza
• Nov 17: Homework 5 is now posted
• Nov 11: Week 10 tutorial handout is posted below. Tutorial solution will also be posted on Piazza
• Nov 4: Week 9 tutorial handout is posted below. Tutorial solution will also be posted on Piazza
• Nov 3: Homework 4 is now posted
• Nov 3: Midterm solution is now posted on Piazza. For regrade request, please see the Piazza post
• Oct 24: HW3 solution is now posted on Piazza
• Oct 23: Practice midterm 1 and 2 have been posted on Piazza

Information

Lectures

Mon 4:30-6:15pm (TYW LT) Wed 5:30-6:15pm (LSK LT5)

Tutorials

Mon 2:30-3:15pm (LSK LT5) Mon 3:30-4:15pm (LSK 301) Tue 3:30-4:15 (LSB G35) Wed 4:30-5:15pm (SC L1)

Prerequisites

Discrete math CSCI2110 or ENGG2440

Textbook

Introduction to the Theory of Computation, Michael Sipser, 3rd ed (older editions also work and are much cheaper)

Forum

Please sign up on Piazza

Grading

Homeworks (30%), Midterm exam (30%), Final exam (40%)

Lectures

Schedule

	Date	Topic	Readings	Lectures	Tutorials	Problems
1	Sep 7	Introduction, finite automata	§1.1	pdf	no tutorials
2	Sep 9	Nondeterministic finite automata	§1.2	pdf
3	Sep 14	NFA to DFA, regular expressions	§1.2, 1.3	pdf	week 2	HW 1
4	Sep 16	Equivalence of DFA and regular expressions	§1.2, 1.3	pdf
5	Sep 21	Text search, closure properties	§1.1-1.3	pdf	week 3
6	Sep 23	Irregular languages	Exercise 1.48	pdf
	Sep 28	Holiday: the day after Mid-Autumn			no tutorials
7	Sep 30	DFA minimization, pumping lemma	§1.4	pdf		HW 2
8	Oct 5	Context-free grammars	§2.1	pdf	week 5
9	Oct 7	Parsing	§2.1, 7.2	pdf
10	Oct 12	Pushdown automata	§2.2	pdf	week 6	HW 3
11	Oct 14	Pumping lemma for CFGs	§2.3	pdf
12	Oct 19	LR(k) parsers	§2.4	pdf	no tutorials
	Oct 21	Holiday: Chung Yeung Festival
	Oct 26	Midterm exam			no tutorials
13	Oct 28	Church–Turing Thesis	§3.1, 3.3	pdf
14	Nov 2	Turing machines and their variants	§3.2	pdf	week 9	HW 4
15	Nov 4	Decidability	§4.1, 4.2	pdf
16	Nov 9	Undecidability and reductions	§5.1	pdf	week 10
17	Nov 11	Undecidable problems for CFGs	§5.1, 5.2	pdf
18	Nov 16	Efficient Turing machines	§7.1, 7.2	pdf	week 11	HW 5
19	Nov 18	Nondeterministic polynomial time	§7.3, 7.4	pdf
20	Nov 23	NP-completeness	§7.4, 7.5	pdf	week 12
21	Nov 25	Cook–Levin theorem	§7.4, 7.5	Andrej's
22	Nov 30	Space complexity	§8.1, 8.5, 9.1	pdf	week 13	HW6
23	Dec 2	Zero-knowledge proofs		pdf

Tentative schedule

	Date	Topic	Readings	Lectures	Tutorials	Problems
1	Sep 7	Introduction, finite automata	§1.1		no tutorials
2	Sep 9	Nondeterministic finite automata	§1.2
3	Sep 14	NFA to DFA, regular expressions	§1.2, 1.3			HW 1
4	Sep 16	Equivalence of DFA and regular expressions	§1.2, 1.3
5	Sep 21	Text search, closure properties	§1.1-1.3
6	Sep 23	Myhill–Nerode theorem	Handout
	Sep 28	Holiday: the day after Mid-Autumn			no tutorials
7	Sep 30	DFA minimization	Handout			HW 2
8	Oct 5	Context-free grammars	§2.1
9	Oct 7	Ambiguity, parsing	§2.1, 7.2
10	Oct 12	Pushdown automata	§2.2			HW 3
11	Oct 14	Pumping lemma for CFGs	§2.3
12	Oct 19	LR(k) parsers	§2.4		no tutorials
	Oct 21	Holiday: Chung Yeung Festival
	Oct 26	Midterm exam			no tutorials
13	Oct 28	Turing machines	§3.1, 3.3
14	Nov 2	Variants of Turing machines	§3.2			HW 4
15	Nov 4	Undecidability	§4.1, 4.2
16	Nov 9	Reductions	§5.1
17	Nov 11	Rice theorem, more undecidable problems	§5.1, 5.2
18	Nov 16	Efficient Turing machines	§7.1, 7.2			HW 5
19	Nov 18	NP-completeness	§7.3, 7.4
20	Nov 23	More NP-complete problems	§7.4, 7.5
21	Nov 25	NL-completeness, Savitch's theorem	§8.2, 8.5
22	Nov 30	Hardness of approximation	Handout			HW 6
23	Dec 2	Zero knowledge proofs	Handout

Tutorials

Tutorial section assignment is available here

Tutorial solutions can be found on Piazza

Homeworks

Homeworks are typically posted on Mondays every other week and due on Thursdays the following week.

Solutions should be submitted to the box labeled CSCI 3130 on the 9th floor of SHB by 11:59pm on Thursday.

Your lowest homework grade will be dropped.

Collaboration on homework is encouraged, but you must write up your own solutions, and list your collaborators on the solution sheet.

Homework solutions can be found on Piazza

Homework 1 due Thu Sep 24

Homework 2 due Thu Oct 8

Homework 3 due Thu Oct 22 (last updated on Oct 20)

Homework 4 due Thu Nov 12

Homework 5 due Thu Nov 26

Homework 6 due Wed Dec 9