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 Lin's slides introducing DFAs: Wolf, Goat, Cabbage

    -->
  3. 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)
  4. 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

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