CSCI 356: Theory of Computing (Fall 2021)

Course Description

An introduction to the theoretical foundations of computer science, examining finite automata, context-free grammars, Turing machines, undecidability, and NP-completeness. Abstract models are employed to help categorize problems as undecidable, intractable, tractable, and efficient.

See the course outline for more information.

Course Details

Lecture Time/Place

Monday, 1:15pm–2:05pm; Wednesday, 12:15pm–1:05pm; Friday, 11:15am–12:05pm

All lectures are held in J. Bruce Brown Hall, room 236.

Textbook

M. Sipser, Introduction to the Theory of Computation. Cengage, 3rd edition, 2012.

The textbook is available for sale at the campus bookstore. Course notes will also be provided for each lecture.

Marking Scheme

You must write the final examination in order to pass the course, even if the weighted sum of your assignment and midterm examination grades is at least 50%.

News

Lectures

Week Notes Readings
1 Introduction, mathematical preliminaries Sipser, 0.1–0.2
2 Regular languages: finite automata, nondeterminism Sipser, 1.1–1.2
3 Regular languages (cont’d): regular expressions, proving nonregularity Sipser, 1.3–1.4
4 Context-free languages: grammars, ambiguity Sipser, 2.1
5 Context-free languages (cont’d): Chomsky normal form, PDAs Sipser, 2.2
6 Mid-course review, midterm examination
7 Context-free languages (cont’d): proving non-context-freeness Sipser, 2.3
8 Beyond context-free: Turing machines, variants Sipser, 3.1–3.2
9 Beyond context-free (cont’d): Church-Turing thesis; Decidability Sipser, 3.3, 4.1
Fall study break
10 Undecidability; Reducibility Sipser, 4.2, 5.1, 5.3
11 Time complexity: P, NP Sipser, 7.1–7.3
12 Time complexity (cont’d): NP-completeness; Space complexity: PSPACE, L, NL Sipser, 7.4, 8.1–8.2, 8.4

Assignments

Assignments are due at the beginning of class on the due date. Late assignments will be accepted up to the beginning of the first class following the due date. Late assignments are subject to a penalty of 10% deducted from the earned mark.

Exams

Midterm

Date: Oct. 15, 2021
Time: 11:15am–12:05pm
Place: J. Bruce Brown Hall, room 236
Content: All material from Weeks 1 to 5

Final Exam

Date: Dec. 11, 2021
Time: 2:00pm–4:30pm
Place: Mulroney Hall, Room 2034
Content: Primarily material from Weeks 6 to 12, some earlier material

Personnel

Instructor

Taylor J. Smith
Email: tjsmith [at] stfx [dot] ca
Office: Annex, Room 9A
Student hours: Monday, 2:15pm–3:15pm; Tuesday, 9:15am–10:15am