CS154 - Winter, 2000

CS154 - Introduction to Automata and Complexity Theory
Winter Quarter 2000

Index

Resources
Registration and Introductory Material
Assignments
Lecture Notes

Resources

The Miderm and The Solution.
The Final and The Solution.
The Table of Contents for the new book.
Here are some test files for your regular-expression processor (Project Part 1).
1. test1.txt: a RE whose DFA has about 1000 states.
2. test2.txt: a RE whose DFA has about 32,000 states.
3. test3.txt: a RE whose DFA has about 1,000,000 states.
4. test4.txt: a RE whose DFA has about 32,000,000 states.
5. test5.txt: a RE with a big NFA but a very small DFA.
6. test6.txt: an even more extreme version of test5.txt.

Test Cases for Project Part 2.

We have made a file with the contents of 20,000 pages from the www.stanford.edu server, and this file will be input to your FA simulator. There are also samples of this file available, and we hope you will try out your Project 3 on small samples before trying the whole thing.

Class Registration

Course Information (HTML).
Course Outline (HTML).

Assignments

Assignment #1 (HTML), due Tuesday 1/18/00 at Noon. The FAQ sheet. Solutions
Assignment #2 (HTML), due Monday 1/24/00 at 3:15PM. The FAQ sheet. The solutions: Postscript; PDF.
Project #1 (HTML), due Wednesday 2/2/00 at 3:15PM. The FAQ sheet.
Assignment #3 (HTML), due Monday 1/31/00 at 3:15PM. The FAQ sheet. Solutions
Assignment #4 (HTML), due Monday 2/14/00 at 3:15PM. Solutions
Project #2 (HTML), due Wednesday 2/23/00 at 3:15PM. The FAQ sheet.
Assignment #5 (HTML), due Monday 2/28/00 at 3:15PM. The FAQ sheet. Solutions
Assignment #6 (HTML), due Monday 3/6/00 at 3:15PM. The FAQ sheet. Solutions
Project #3 (HTML), due Wednesday 3/8/00 at 3:15PM. The FAQ sheet.
Mock Homework #7. Read, but do not hand in. Solutions.