CS280
Introduction to Formal Languages and Theory of Computation
Autumn 1999

The final is on Wednesday 8 Dec early in the morning at 8:00 a.m. Place is RY 277 as usual.

• Time: MWF, 9:30-10:20 a.m.
• Room: RY277

CS280 addresses basic questions about computation and models of computation. Given a C program, is it possible to write a Scheme program that does exactly the same task? Is it possible to write a C program which takes in any C program as input and says if the input program uses only finite memory for any finite input?

Answering these and other questions requires a precise understanding of the power and limitations of computing. Finite automata, context free grammars and Turing machines are the three components of CS280.

Instructor: Divakar Viswanath

• Office: Ryerson 162C
• Email: divakar@cs.uchicago.edu
• Phone: 834-4545
• Office hours: Wednesdays 2:00-3:00 p.m., Fridays 1:00-2:00 p.m. and by appointment. Usually free on Monday afternoons.

Grader: Murali Krishnan

• Office: Ryerson 162A
• Email: gmkrishn@cs.uchicago.edu
• Phone: 702-3496

Course Information

• Handout #1
• Handout #2

Homeworks

• Homework #3
• Homework #4
• Homework #5
• Homework #6
• Homework #7
• Homework #8
• Homework #9

Homework Solutions

• Homework #1
(Mean = 13.4/25)
• Homework #2
(Mean = 16.1/20)
• Homework #3
(Mean = 29.3/40)
• Homework #4
(Mean = 26.1/40)
• Homework #5
• Homework #6
• Homework #7
• Homework #8
• Homework #9

Exams