Theory of Computation (CSCI 342)

Fall 2007

 

Instructor:                 Dr. Teresa Zollo

Email:                         teresa.zollo@yahoo.com

Phone:                        (585) 797-8647

URL:                            http://www.cs.geneseo.edu/~zollo

 

Office Hours:            Mondays 10:30-11:20 in South 341

                                      and by appointment                

                       

Lecture classes:  Mondays, Wednesdays and Frisdays 11:30-12:20,   Welles 24

 

Text:      Introduction to Automata Theory, Languages, and Computation (Second Edition), by John E. Hopcroft, Rajeev Motwani, and Jeffrey D. Ullman.  ISBN 0-201-44124-1    

Other assigned readings will be available through electronic reserve, the web, or the instructor’s outbox.

 

Course Description from the Student Bulletin:   This course covers basic theoretical principles

embodied in the theory of automata, the theory of formal languages, and the theory of Turing machines. Topics include finite automata, push-down automata, non-determinism, regular expressions, and context-free grammars; Turing machines and universal Turing machines; the halting problem, unsolvability, and computational complexity.

Prerequisites: CSCI 242.

Course Objectives:   Students who meet the intended goals of  this course will be able to:

 

 

 

 

 

 

 

 

 

 

 

 

Grading Policies

 

 

Numeric Course Score Computation

Course Component

Possible Points*

Weight

24  homework assignments

72

20%

12 quizzes

36

20%

midterm

100

30%

final exam

100

30%

*Homework assignments and quizzes will be given scores between 0 and 3.  The midterm and final exams will be scored based on 100 points.  

 

 

Grading Criteria for Homework and Quizzes

 

Grade

Description of student work

3

the solution was submitted at the beginning of the class period on the due date,  the solution is legible, well-organized and coherent,  the solution is correct, the solution demonstrates a good understanding of the course material being applied

2

the solution was submitted within 24 hours of the time it was due, the solution is fairly legible, well-organized and coherent,  the solution contains only minor errors, the solution demonstrates a basic level of understanding of the course material being applied

1

the solution was submitted within 24 hours of the time it was due, the solution is partially illegible, the solution is not presented in a organized and coherent manner,  the solution contains significant errors, the solution demonstrates a lack of understanding of the foundational course material being applied

0

the solution was not submitted within 24 hours of the time it was due, the solution is illegible or otherwise incoherent, the solution does addressed the question asked/problem assigned, the solution violates the academic honesty policy of the College**

 

**You are free to consult with your classmates on the homework.  However, each of you must submit your own solutions, written in your words and reflecting your own understanding of the material.  You may be asked to present your solutions in class.  If you are unable to adequately explain your solutions, then your grade will be 0.

 

Criteria for Distribution of Final Letter Grades

 

Numeric Course Score

Letter Grade

Numeric Course Score

Letter Grade

³ 93

A

³ 77   &  < 80

C+

³ 90  &  < 93

A-

³ 73  &  < 77

C

³ 87  &  < 90

B+

³ 70  &  < 73

C-

³ 83  &  < 87

B

³ 65  &  < 70

D

³ 80  &  < 83

B-

> 65

E

 

 

Tentative Course Schedule

 

 

Exams and Quizzes

Wed 09/05                 Quiz 1                          Wed 10/24                 Quiz 7

Wed 09/12                 Quiz 2                         Wed 10/31                  Quiz 8

Wed 09/19                 Quiz 3                         Wed 11/07                  Quiz 9

Wed 09/26                 Quiz 4                         Wed 11/14                   Quiz 10

Wed 10/03                 Quiz 5                         Wed 11/28                  Quiz 11

Wed 10/10                  Quiz 6                         Wed 12/05                  Quiz 12

Wed 10/17                  Midterm Exam          Fri    12/14  12-3 PM   Final Exam

 

 

Lecture Topics

 

Mon 08/27                                        Course Overview and Objectives    

Wed 08/29                                         Introduction to Formal Languages  (Sec 1.5)   

Wed 09/05  --  Fri    09/14               Finite Automata  (Chapter 2)

Mon 09/17   --  Fri    09/21               Regular Expressions  (Chapter 3)

Mon 09/24  &            Wed 09/26                Proving Languages to be Not Regular  (Sec 4.1)               

Fri    09/28  &  Mon 10/01                Properties of Regular Languages (rest of Chapter 4)

Wed 10/03   –  Mon 10/22                Context-Free Grammars  (Chapter 5)

Wed 10/24  &              Fri    10/26                 Pushdown Automata (Chapter 6)

Mon 10/29   --  Fri    11/02                Properties of Context-Free Languages (Chapter 7)

Mon 11/05   &  Wed  11/07                Proving Languages to be Not Context-Free (Sec 7.2)

Fri    11/09   --  Mon  11/19                Turing Machines (Chapter 8)                      

Mon 11/26   --  Fri     11/30                Undecidability            (Chapter 9)

Mon 12/03  --  Mon  12/10                Intractability (Chapter 10)