EECS 2001: Introduction to the Theory of Computation

EECS 2001 B: Introduction to the Theory of Computation

NOTE: the tutorial and lecture scheduled for November the 6th and 7th will be switched, i.e.,
- tutorial will take place on Nov. the 7th
- lecture will take place on Nov. the 6th

Course details

  • Lecture schedule: M,R, 17:30-19:00, CLH E
  • Tutorials schedule: W, 17:30-19:00, CLH E
  • Instructor's office hours: M 4:30-5:30pm, W 12-1pm, Lassonde Bld., 3052B
  • TAs:

Course description and Learning Outcomes

The Theory of Computation is one of the core disciplines defining modern computer science and applies to all aspects of computing from theoretical and philosophical considerations to practical applicability. The discipline offers the language to formalize, analyze, and implement computational problems as well as formal methods to support such an analysis and implementation. This course is the first introductory course in the theory of computing (it is continued as EECS4111). Its focus is on the basic concepts of formal grammars, languages, and models of computers as well as on these concepts' applications in several areas of computing from programming languages to Artificial Intelligence.

The course's learning objective is to master the language, concepts, and methods of the theory of computation necessary for, and required of every computer professional.

Course Evaluation

  • Assignment 1, 0.5%;
    deadline: 3 October
  • Assignment 2, 0.5%;
    deadline: October 31
  • Assignment 3, 0.5%;
    deadline: November 18th
  • Assignment 4, 0.5%;
    deadline: tba
  • Test 1, 29%; date: October 10
  • Test 2, 29%; date: November 11
  • NOTE: There will be no makeup tests; if you miss a test for valid medical, compassionate, etc. reasons (valid in accordance with York Un. regulations and documented without delay), the weight of missed tests will be transferred to final exam.
  • Final Exam, 40%;
    date/location: tba

  • Assignment location: all assignments and their solutions will be deposited in the course's directory /eecs/dept/course/2019-20/F/2001B

Course Schedule (covered subjects will be listed weekly)

  • week 1: course overview; alphabets and languages (textbook, section 0.2)
  • week 2: deterministic finite automata (DFAs) and the languages accepted by them: definitions and basic properties (textbook, section 1.1).
  • week 3: non-deterministic finite automata, regular languages and their properties (textbook, section 1.2); regular expressions (textbook, section 1.3)
  • week 4:
    - nonregular languages and the Pumping Lemma for regular languages (section 1.4)
    - regular languages and finite automata: applications;
    see lecture notes which can be found in the course's directory.
  • week 5: context-free grammars (CFGs): derivations, parse trees, ambiguity (textbook, section 2.1) the syntax of C
  • week 7: Chomsky Normal Form theorem (textbook, section 2.1)
  • week 8: context-free languages, applications: defining programming languages and parsing (textbook, section 2.4 and lecture notes)
  • week 9: Turing Machines (TMs): basic concepts, recursive and recursively enumerable languages, TMs as computers of integer functions, Church-Turing thesis (textbook, sections 3.1, 3.3, 5.3)
    See also these lecture notes:
    a brief portrait of Allan Turing.;
    informal notes on TMs and the limits of computing.
  • week 10: nondeterministic TMs; time and space complexity, complexity class P (textbook, sections 3.2 and 7.1, chapter 8)
  • week 11: problems as languages, decidable and undecidable problems, the denationalization and universal languages (textbook, sections 4.1, 4.2, 5.1 ).
  • week 12: complexity classes P and NP, the satisfiability problem SAT and its significance in computational complexity theory (textbook, sections 7.1-7.4)
    he big picture

Course Readings

The main textbook used in this course is: Introduction to the Theory of Computation by Michael Sipser. Other sources on the same subject (such as Introduction to Automata Theory, Languages, and Computation, by J.E. Hopcroft, R. Motwani, and J. Ullman) can also be used; however, it would be the student's responsibility to locate the relevant material when texts other than the recommended one are used.

York University Computer Museum is Looking for Volunteers!

York University Computer Museum (YUCoM) is looking for student volunteers to help with various projects from archiving documents to arranging exhibits. If you would like to volunteer 1 hour a week of your time, 2 hours, or more, please contact the instructor. Thanks!