| CS 467/ 667 Theory of Computation | Fall 2002 | ||||
|
11:00 AM - 12:15 PM. Tuesday &
Thursday, PE 208
|
|||||
| Instructor: |
Yaakov L. Varol
|
||||
| Office: |
SEM 242. Office Hours: Tuesday &
Thursday 09:30 - 10:50 AM, or by appointment.
|
||||
| Catalog Entry: |
Fundamental concepts of computation.
Relationship between grammars, languages and machines, emphasizing regular and context free languages, finite state acceptors and Turing machines. Complexity, and computability. Prerequisite, CS 365(306) and MATH 182.
|
||||
| Textbook: |
Introduction to Formal Languages and
Automata (3rd edition) By Peter Linz, Jones and Bartlett Publishers, 2001
|
||||
| Course Outline: |
The coverage in this course will focus on
mathematical properties of computer hardware and software, languages, and certain applications. We will study what can or cannot be computed, how quickly, and on which type of a machine. The course will have three parts: automata and languages, computability, and complexity. Roughly two thirds of the course will be devoted to the study of finite accepters, regular languages, push down automata, and context free languages (chapters 1-8). The rest of the course will cover Turing machines, computability, and complexity (chapters 9-14).
|
||||
| Course Objective: |
This course is intended to be an upper level
undergraduate or introductory graduate course in computer science theory.
The objective is to build upon the foundations laid down in CS 365. Theorems and proofs are important and will be covered. However, the emphasis will be on intuition, on practical considerations, and on the relevance of the theory to computer scientists and engineers.
|
||||
| Course Work: |
There will be specific assignments from the
exercises and problems at the end of each chapter. Questions on tests will bear close resemblance to the assignments.
|
||||
| Course Grade: |
Tentative (i.e. subject to change) make up
for the course grade is as follows: Midterm Tests ( 3 or 4 in number ) 60% Comprehensive Final (Thursday, December 12, 07:30 AM) 40%
|
||||
| P.S.: |
The work load and evaluations for CS 667
students will be slightly different and a bit more demanding. Make-ups for
quizzes or exams and the grade of incomplete will not be granted except for
medical reasons. The academic dishonesty policies of the University of
Nevada, Reno will be enforced on all cases of plagiarism or cheating. Please
read the policy at
www.unr.edu/stsv/acdispol.html.
|
||||
| HAVE A WONDERFUL FALL SEMESTER. | |||||