Term: F
Catalogue No: 218301
| Day | Time | Location
038SSB ------------------------ Except for Correspondence and Internet courses, some final examinations could take place in a different room and on a different day from the regularly scheduled class. Check the published Examination Schedule for a complete list of days and times. |
|||
| Tuesday and Thursday | 2:30-4:00 pm [See also Lecture Schedule ] |
||||
| Instructor: | Professor
G. Tourlakis
, Office: 2051 CSB, Telephone: 736-2100-66674, e-mail: gt@cs.yorku.ca |
|
| Start date: | Sept. 6, 2001 | |
It is the responsibility of students to check the course web page weekly for course related information.
COURSE DESCRIPTION
This course covers fundamental theoretical computer science topics that find application in a wide variety of areas in the field (e.g., the design and analysis of computer algorithms, program semantics and correctness, programming language specification and translation).
Topics will include: Formal Languages and their acceptors
, specifically, the following themes: Regular and Context free
languages and finite and pushdown automata; Introduction
to Turing Machines and Computability. The Unsolvability
of the "Halting Problem". Overview of "things to come".
PREREQUISITES:
Department of Computer Science General
Prerequisites.
This course will call decisively
on your mathematical background.
REQUIRED TEXT
Hopcroft, Motwani, Ullman, Automata Theory, Languages and Computation
, Addison Wesley (2001). ISBN: 0-201-44124-1
SUGGESTED TEXTS
H. R. Lewis and C. H. Papadimitriou, Elements of the Theory of Computation,
Prentice Hall (latest edition). ISBN 013 2734176
Michael Sipser, Introduction
to the Theory of Computation, PWS Publishing Company. ISBN 0-534-94728-X
WEIGHTING OF COURSE
| Term work (Homework 30% ; Mid-Term Test 30%) |
|
|
| Final Exam (Exam Period starts on December 7. Time/place/date: TBA) |
|
Term Test Date/Time: October 23, 2001 (in class).
Last revised: Sep 3, 2001