Term: W
Catalogue Number 165601
| Day | Time | Location
3009 VARI HALL ------------------------ 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. |
|||
| Monday | 6:00-9:00 pm
[See also Lecture Schedule] |
||||
| Course director: | Professor G.
Tourlakis,
Office: 354 Chemistry & Computer Science Building, Telephone: 736-2100-66674, e-mail: gt@cs.yorku.ca |
|
| Start date: | 01/03/2000 | |
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 processors, specifically, the following themes:
Regular and Context free languages and their automata; Introduction to
"type-0" languages, Turing Machines and Computability. Unsolvability. If
time permits introduction to NP-completeness.
PREREQUISITES:
AK/COSC2411 3.0, AK/COSC2412 3.0 and AK/MATH2442 3.0
Alternatively, Department of Computer Science General
Prerequisites.
NOTE: Not open to students who have completed AK/COSC3430 6.0
REQUIRED TEXT/S
Introduction to the
Theory of Computation, by Michael Sipser, PWS Publishing Company. ISBN
0-534-94728-X
SUGGESTED TEXT
J. E. Hopcroft and J. D. Ullman, Introduction to Automata Theory,
Languages and Computation, Addison-Wesley. ISBN 0201 029 88-X
H. R. Lewis and C. H. Papadimitriou, Elements of the Theory of Computation,
Prentice Hall (latest edition). ISBN 013 2734176
WEIGHTING OF COURSE
| Term work (Assignments 50% and Test (in-class) 20%) | 70% | |
| Final Exam (in-class) | 30% |
Term Test Date/Time: February 21, 2000; 6:00-7:30pm (in class).
Last revised: Mon Jan 3 15:39:12 2000