CSCI 2400 - Models of Computation

Fall 2001

Syllabus

http://www.cs.rpi.edu/courses/fall01/modcomp

Class Meetings

Place : DCC 324
Time: Tuesday & Friday  2:00-3:50 pm

Instructor & TAs

 

Name

Office

Email

Phone

Office Hours

Instructor

Costas Busch

Lally 302

 

x2782

Monday & Tuesday & Friday 4-5 pm

Graduate TA

Seung-Mok Yoo

Lally 3b

 

x8565

Thursday 10-12 am

Graduate TA

Zhong Zhang

Lally 310

 

 

Fr iday 12-2 pm

Undergraduate TA

Mark Fermann

 

 

 

 

Undergraduate TA

Marshall Vandergrift

 

 

 

 

Undergraduate TA

Ki Yim

 

 

 

 

Text (Required)

Title: An Introduction to Formal Languages and Automata
Author:  Peter Linz
Edition: Third
ISBN: 0-7637-1422-4

Grading

Homeworks (40%)

There will be 7 homeworks. Each homework will consist from 5 problems. You will have 2 weeks for each homework.
No late homeworks are accepted.

Computer Projects (20%)

There will be 2 computer projects. The first project counts 5% and the second 15%, respectively, of your grade. You will have almost a month for each project. For the projects you will work with teams of 3 people. No late projects are accepted.

Exams (40 %)

There will be one midterm and one final exam. Each counts for 20% of your grade. The exams will be given in class and will be open book.

Academic Integrity

 Collaboration is not allowed. Any collaboration will be considered cheating. The only allowed collaboration is for the projects between the same team members. If anyone is cought cheating then appropriate measures will be taken.

Tentative Schedule

 

Day

Topic

Book Chapter

Assignments

Tuesday August 27

Mathematical Preliminaries

1.1

 

Friday August 31

Finite Automata

1.2 & 2.1

 

Tuesday September 4

Nondeterministic Finite Accepters

2.2 - 2.3

Homework 1 - out

Friday September 7

Regular Expressions

3.1 - 3.2

 

Tuesday September 11

Regular Grammars

3.3

 

Friday September 14

Properties of  Regular Languages

4.1 - 4.2

 

Tuesday September 18

Pumping Lemma

4.3

Homework 1 due
Homework 2 - out

Friday September 21

Lex

 

Project 1 - out

Tuesday September 25

Context-Free Languages

5.1

 

Friday September 28

Parsing and Ambiguity

5.2 - 5.3

 

Tuesday October 2

Normal Forms

6

Homework 2 due
Homework 3 -out

Friday October 5

Pushdown Automata & Context-Free Languages

7.1 - 7.3

 

Tuesday October 9

No class (follow Monday's class schedule)

 

 

Friday October 12

Deterministic Pushdown automata & Pumping Lemma

7.4 & 8.1

 

Tuesday October 16

Properties of Context-Free Languages

8.2

Homework 3 due
Homework 4 -out

Friday October 19

Yacc

 

 

Tuesday October 23

Review Class

 

Project 1 due
Project 2 - out

Friday October 26

Midterm

 

 

Tuesday October 30

Turing Machines

9.1

Homework 4 due
Homework 5 - out

Friday November 2

Turing's Thesis

9.2 - 9.3

 

Tuesday November 6

Variations of Turing Machines

10.1 - 10.2

 

Friday November 9

Universal Turing Machine

10.3 - 10.5

 

Tuesday November 13

Recursive Languages

11.1

Homework 5 due
Homework 6 - out

Friday November 16

The Chomsky Hierarchy

11.2 - 11.4

 

Tuesday November 20

Decidability

12.1 - 12.2

 

Friday November 23

No class (Thanksgiving)

 

 

Tuesday November 27

The Post-Correspondence Problem

12.3 - 12.4

Homework 6 due
Homework 7 - out (2 problems only)

Friday November 30

Other Models of Computation & Computational Complexity

13 & 14

Project 2 due

Tuesday December 4

Review Class

 

Homework 7 due

Friday December 7

Final Exam