CS 360: Introduction to the Theory of Computing (Spring 2024)

Final Exam Details

Date: 2024-08-06
Time: 16:00-18:30
Room: PAC 8
Coverage: Modules 1-8, Module 9, up to and including slide 47. The following topics will NOT appear:
- Full proofs of the major Theorems, e.g. Kleene's Theorem, its alanog for CFLs and PDAs, etc.
- Constructing a CFG generating the language that an arbitrary PDA accepts
- Converting an arbitrary CFG into CNF
- Decision problems for CFLs
- Post's correspondence problem
Other Details:
- There will be assigned seating for this exam. See Odyssey for your seat assignment.
- Most of the questions will be free-form answer. There will also be a few True/False questions, which you will answer on a provided Crowdmark multiple choice page at the end of you exam booklet.
- Here is a link to Page 1 of the exam.
- Past Final Exam
  - Here is the Final Exam from the 2010 Fall term.
  - I will post solutions on LEARN, by the end of 2024-08-02.

Schedule of Lectures

We will adjust this schedule as required.

All lectures will be in MC 4060, at the scheduled times of 10:00-11:20 on Tuesdays and Thursdays.

There will be a Final Exam during the Final Exam period, which will cover the entire course.

Week	Lectures		Assignments and Exams	Module(s)
Week	Part 1	Part 2	Assignments and Exams	Module(s)
1: May 6–10	terminology, techniques of proof	finite automata Pre-read Module 2, up to slide 30	N/A	1, 2
2: May 13–17	finite automata Pre-read Module 2, to the end	regular languages and regular expressions Pre-read Module 3, up to slide 20	Crowdmark Assignment 1 available	2, 3
3: May 20–24	N/A (Victoria Day makeup)	regular languages and regular expressions Pre-read Module 3, to the end	Crowdmark Assignment 1 due May 24 at 11:59 PM EDT Marked Quiz 1 available	3
4: May 27-May 31	properties of regular languages Pre-read Module 4, up to slide 28	properties of regular languages Pre-read Module 4, to the end	Marked Quiz 1 due May 31 at 11:59 PM EDT Crowdmark Assignment 2 available	4
5: June 3–7	context-free grammars and languages Pre-read Module 5, up to slide 25	context-free grammars and languages Pre-read Module 5, up to slide 43	Crowdmark Assignment 2 due June 7 at 11:59 PM EDT Marked Quiz 2 available	5
6: June 10–14	context-free grammars and languages Pre-read Module 5, up to the end	pushdown automata Pre-read Module 6, up to slide 21	Marked Quiz 2 due June 14 at 11:59 PM EDT Crowdmark Assignment 3 available	5, 6
7: June 17-21	pushdown automata Pre-read Module 6, up to slide 46	pushdown automata Pre-read Module 6, up to slide 57	Crowdmark Assignment 3 due June 21 at 11:59 PM EDT Marked Quiz 3 available	6
8: June 24–28	pushdown automata Pre-read Module 6, up to the end	properties of context-free languages Pre-read Module 7, up to slide 19	Midterm Exam June 27, 16:30-18:20 Marked Quiz 3 due June 28 at 11:59 PM EDT Crowdmark Assignment 4 available	6, 7
9: July 1–5	properties of context-free languages Pre-read Module 7, up to slide 37	properties of context-free languages Pre-read Module 7, up to the end	Crowdmark Assignment 4 due July 5 at 11:59 PM EDT Marked Quiz 4 available	7
10: July 8–12	introduction to Turing machines Pre-read Module 8, up to slide 19	introduction to Turing machines Pre-read Module 8, up to slide 30	Marked Quiz 4 due July 12 at 11:59 PM EDT Crowdmark Assignment 5 available	8
11: July 15–19	introduction to Turing machines Pre-read Module 8, up to slide 46	introduction to Turing machines Pre-read Module 8, up to the end	Crowdmark Assignment 5 due July 19 at 11:59 PM EDT Marked Quiz 5 available	8
12: July 22–26	undecidability Pre-read Module 9, up to slide 24	undecidability Pre-read Module 9, up to slide 49	Marked Quiz 5 due July 26 at 11:59 PM EDT Crowdmark Assignment 6 available	9
13: July 29–30	undecidability Pre-read Module 9, up to the end	N/A	Crowdmark Assignment 6 due July 30 at 11:59 PM EDT	9