Term: W
| Day | Time | Location CLH K ------------------------ |
|||
| Tuesday and Thursday | 4:00-5:30 pm [See also Lecture Schedule ] |
||||
| Instructor: | Professor
G. Tourlakis , Office: 2051 CSEB, Telephone: 736-2100-66674, e-mail: gt@cse.yorku.ca |
|
| Start date: | Jan. 3, 2008 | |
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 deciders and verifiers, 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". More unsolvability results as time
permits. 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. Latest edition.
OTHER 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 |
|
Term Test Date/Time: Feb 19, 2008 (in class).
Note: Missed tests with good reason (normally medical, and well documented) will have their weight transferred to the final exam. There are no "make up" tests. Tests missed for no reason are deemed to have been written and are marked "0" (F).
The
homework must be each
individual's own work.
While consultations with
the instructor, tutor(s),
and among students,
are part of the learning process
and are encouraged, nevertheless, at the end
of
all this consultation each student will
have to produce an
individual (typed) report rather than a copy (full or partial) of
somebody
else's report.
Follow these links to
familiarise yourselves with Senate's expectations regarding Academic
Honesty, but also with many other Senate policies, in particular,
with those about Academic
Accommodation for Students with Disabilities, Religious
Accommodation and Repeating
Passed or Failed Courses for Academic Credit. See also this link.
The
concept of "late assignments" does not exist in this course (solutions
are posted on the due date).
Last revised: Jan 4, 2008