Computing Science 320

Foundations of Computer Science

Course outline


Instructor: Dr. Gara Pruesse
Office:  Bldg 315, Room 218
Office Hours: TBA
TBA
Contact:  (250) 753-3245 Local 2337
  Gara.Pruesse [at] viu [dot] ca
Lecture:  Tue, Thu, 1:00-2:30 in Building 210, Room 240
Seminars:  Tue 9:30-10:30 (Section N01) or 10:30-11:30 (Section N02) in Building 210, Room 240


Text:  The following is the required text for the course:

Introduction to the Theory of Computation, 3rd Edition (2nd is also acceptable)
by Michael Sipser. Thomson Course Technology. ISBN 978-0-534-95097

The following open-access, free online text can be used supplementary material for the course:
Theory of Computation by Anil Maheshwari Michiel Smid (U. of Ottawa)

Various other texts may be useful to help the student understand the material, including the following book by Goddard, which has the virtue of being easy to understand and is a recommended read for those who find the material very challenging (though our treatment of Push-Down Automata differs from Goddard's):

Goddard, Wayne. Introducing the Theory of Computation   ISBN 978-0-7637-412-9 ISBN10 0-7637-4125-6



Students are responsible for receipt of announcements made in person in class. Students are responsible for material covered in class.

Content

The following is the general schedule for guidance only.
Week Topic Sipser chapter(s)
Week 1 Review of Sets, functions, etc.; Introduce Strings and Languages Chapter 0 and Chapter 1.
Week 2 Regular language; closure under union; Non-Determinism; algorithm for converting NFA to DFA. Ch 1
Week 3 Regular Expressions. Kleene's Theorem; Algorithms for converting among re, DFA, NFA. Pumping Lemma. Enumeration; countably infinite sets; diagonalization proof. Chapter 1 NFA to DFA conversion
Week 4 Pumping Lemma plus Closure theorems for Regular Languages; Intro to CFGs Chapter 1.4 Reference Slides 4; Azedeh Farzan slides; A 33 min video; Reference Slides5
Week 5 Context Free Languages Ch 2
Week 6 CFGs continiued; Contains Regular Languages; Chomsky Normal Form Ch 2 (cont'd) Reference Slides6 Reference Slides7: Pumping Lemma CFLs
Week 6 Set Cardinality Pp 202-205
Week 7 Turing Machines; Turing Machines Ch 3 2016 Test 1 solutions Sample Test 2 (which we covered in class, almost to the end) Sample Test 1 with a Pumping Lemma quiz appended. Jeff Edmonds' slides on uncountability Alan Turing Scrapbook, Jeff Edmonds' slides on Models of Computation
Week 8 (approx.) Study Days Office hours are by appointment
Week 9 Formal Defn TM; Variations on the standard TM; Nondeterminism, multitape, etc. Ch 3 cont'd
Week 10 Church-Turing Thesis. Universal TM (not covered in Text). Decidable Languages and Turing Recognizable Languages Ch 4;
Week 11 Undecidability and the Halting Problem. Reducibility. Ch 4-5.
Week 12 Time complexity; NP-complete Ch 5. Ch 7.
Week 13 NP-completeness Ch 7 cont'd Shiyan Hu's NP-completeness slides; Power Point slides from GSU on reductions. A practice final will be provided closer to the end of term.
Week 14 NP-completeness, Summary, Review Ch 7

Grading Scheme: