Computing Science 320

Foundations of Computer Science

Course Materials for Spring 2022


Instructor: Dr. Gara Pruesse
Office:  Bldg 315, Room 218
Contact:  (250) 753-3245 Local 2337
  Gara.Pruesse [at] viu [dot] ca


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





Below are of some resources used in previous years, as extra material.
  1. A Sample CFL test (Test 2) from 2015. And the Solutions.
  2. CFG Ambiguity slides
  3. Lin's slides introducing DFAs: Wolf, Goat, Cabbage

  4. The following open-access, free online text will be used supplementary material for the course:
    Theory of Computation by Anil Maheshwari Michiel Smid (U. of Ottawa)
  5. Various other texts may be usefull 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

  6. Another helpful resource is the following recorded lectures: Jeff Ullman's lectures
  7. Reference Slides1 (pdf)
  8. Reference Slides2 (pdf): DFAs
  9. Slides3 (pdf): DFAs
  10. Reference Slides4
  11. Azedeh Farzan slides
  12. A 33 min video : Reference Slides5
  13. Reference Slides6: PDAs
  14. Pumping Theorem for CFLs Reference Slides7
  15. Jeff Edmonds' slides on uncountability
  16. Solutions to Example Test1
  17. Solutions to Example Test1
  18. Alan Turing Scrapbook,
  19. Jeff Edmonds' slides on Models of Computation
  20. Portland State slides
  21. Shiyan Hu's NP-completeness slides;