|
|
Title:
|
|
Theory of Computing
|
|
|
|
|
|
Instructor:
|
|
Cezar Câmpeanu
|
|
|
|
|
|
Email:
|
|
ccampeanu < at > upei < dot > ca
|
|
|
|
|
|
Office:
|
|
CASS 408
|
|
|
|
|
|
Tel:
|
|
(902)566-0485
|
|
|
|
|
|
Textbook:
|
|
Introduction to Automata Theory, Languages, and Computation 3rd Edition,
by John E. Hopcroft, Rajeev Motwani, and Jeffrey D. Ullman
Addison Wesley, 2007,
ISBN 13: 978-0321-46225-1
ISBN 10: 0-321-46225-4
|
|
|
|
|
|
|
|
|
|
|
|
|
|
Textbook Stanford web site:
|
|
http://www-db.stanford.edu/~ullman/ialc.html
|
|
|
|
|
|
Course web site:
|
|
Go To: http://www.smcs.upei.ca/~ccampeanu,
or
http://www.upei.ca/smcs,
Then follow the links: Faculty, Cezar Câmpeanu, Personal Webpage. Then follow Teaching, and MCS332 under Winter 2018
|
|
|
|
|
|
Recommended reading:
|
|
Handbook of Formal Languages Vols. 1 - 3 Rozenberg, Grzegorz; Salomaa, Arto (Eds.) 1997, LXVIII, 2051 p. 272 illus., Hardcover ISBN: 3-540-61486-9
|
|
|
|
|
|
General description:
|
|
This course introduces automata theory, formal languages and computability. Topics include: finite automata, regular expressions, context-free and context-sensitive languages, Turing machines, recursive functions, recursive and recursively-enumerable sets, and unsolvable and intractable problems.
|
|
|
|
|
|
PREREQUISITE:
|
|
CS 261 and Math 242
|
|
|
|
|
|
Essential to review:
|
|
Set theory, Mathematical Logic, including boolean algebras, Induction, Arithmetic/Number Theory (mainly Modular Arithmetic).
|
|
|
|
|
|
Time and Location:
|
|
Monday/Wednesday/Friday 9:30 - 10:20, CSH 104
|
|
|
|
|
|
Office Hours:
|
|
Monday 12:30-2:20, anytime by appointment (please send email-)
|
|
|
|
|
|
Midterm:
|
|
Wednesday, February 28, 2018, during class
|
|
|
|
|
|
Final Exam:
|
|
Saturday, April 14, at 9:00 am Health Science Building 105
|
|
|
|
|
To make sure you are viewing the most recent version of this page,press the shift key while clicking on the Reload button.
It is your responsibility to check this page for updates.
