http://www.cs.rpi.edu/courses/fall01/modcomp
Place : DCC 324
Time:
Tuesday & Friday 2:00-3:50 pm
|
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 |
|
|
|
|
Title: An
Introduction to Formal Languages and Automata
Author: Peter Linz
Edition: Third
ISBN: 0-7637-1422-4
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.
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.
|
|||
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 |
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 |
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 |
Friday October 19 |
Yacc |
|
|
Tuesday October 23 |
Review Class |
|
Project 1 due |
Friday October 26 |
Midterm |
|
|
Tuesday October 30 |
Turing Machines |
9.1 |
Homework 4 due |
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 |
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 |
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 |
|
|