EECS 343 / MATH 343: Theoretical Computer Science

Spring 2004, Prof. Michael Branicky

Case Western Reserve University (CWRU)

General Information

Information Sheet

Lecture Hours: MWF 1:30-2:20pm, WCK 322

Course Instructor: Michael Branicky, mb@cwru.edu, Glennan 517B, x6430

Instructor's Office Hours: M 2:30-3:20pm, T 1-3pm

Course T.A.: Mustafa Kirac, mxk149@cwru.edu, Olin 504

T.A.'s Office Hours: MT 12-1pm

Required Texts

• Dexter C. Kozen. Automata and Computability. Springer-Verlag, NY, 1997. ISBN: 0387949070
  Buy it for $52.95 from www.bn.com: Automata and Computability

• Randal L. Schwartz and Tom Phoenix. Learning Perl, Third Edition. O'Reilly & Associates, 2001. ISBN: 0596001320
  Buy it for $24.46 from www.bn.com: Learning Perl, Third Edition

Class Roster

Log of Missing Assignments

Mirror sites

http://dora.cwru.edu/msb/343
http://vorlon.cwru.edu/~msb11/343

Announcements

• 07 MAY (Final Announcement): Course grades were delivered to the registrar on 05 May (11am); you can view them on-line with the rest of your grades. Course grade distribution was as follows:

  Spring 2004 Grade Assignments / Cut-offs (N=36): A¹³B¹⁵C⁷D¹F⁰W⁰  /  [89, 80, 70, 58]

  The cover sheet of your graded finals may be picked up during regular business hours from Cheryl Lange (Glennan 516); the post-mortem appears below.

  All Solutions links below have been intentionally disabled.

• Old Announcements

Problem Sets and Solutions

Problem Set #0 (Due 1/21)   HMU: Chap 1   Perl Problems   Kozen: Lects 1-2   FAQ   Solutions   Post-Mortem

Problem Set #1 (Due 1/28)   Solutions   Post-Mortem

Problem Set #2 (Due 2/04)   FAQ   Solutions   Post-Mortem

Problem Set #3 (Due 2/11)   FAQ   Solutions   Post-Mortem

Problem Set #4 (Due 2/18)   Examples   Solutions   Post-Mortem

Problem Set #5 (Due 2/25)   FAQ   Examples   Solutions   Post-Mortem

Problem Set #6 (Due 3/17)   Solutions   Post-Mortem

Problem Set #7 (Due 3/24)   Examples   Solutions   Post-Mortem

Problem Set #8 (Due 3/31)   FAQ   Solutions   Post-Mortem

Problem Set #9 (Due 4/14)   Examples   Solutions   Post-Mortem

Problem Set #A (Due 4/21)   Hints   Solutions   Post-Mortem

Problem Set #B (Due 4/26)   Hints   Solutions   Post-Mortem

Code Repository

Lecture Notes / Handouts

Lecture 02 (1/14): Encodings/Language Equality Proof

Lecture 05 (1/23): Protocol for Electronic Money

Lecture 06 (1/26): Subset Construction

Lecture 08 (1/30): e-NFA Conversion to DFA

Lecture 08 (1/30): Patterns

Lecture 09 (2/02): Regexes in Perl

Lecture 11 (2/06): From Regexes to FA

Lecture 23 (3/05): Chomsky Normal Form

Lecture 24 (3/15): CFL Pumping Lemma Example

Lecture 28 (3/24): PDA Simulation

Lecture 30 (3/29): More on Parsing

Simple bison file (logic.y)

If you want to see a more complicated example, you can check out the 1985 draft ANSI C standard grammar

Lecture 32 (4/02): Turing Machine Simulator

Lecture 33 (4/05): Solution to Last Review Problem

Lecture 38 (4/16): Decidable, Semi-Decidable, or Neither

Quizzes / Final

Quiz #1: Information Sheet   Solutions   Post-Mortem

From Spring 2003: Quiz #1   Solutions   Post-Mortem

From Spring 2002: Quiz #1   Solutions   Post-Mortem

From Spring 2001: Quiz #1 & Solutions   Post-Mortem

Quiz #2: Information Sheet   Solutions   Post-Mortem

From Spring 2003: Quiz #2   Solutions   Post-Mortem

From Spring 2002: Quiz #2   Solutions   Corrections   Post-Mortem

From Spring 2001: Quiz #2   Solutions   Post-Mortem

Final Exam: Information Sheet   Post-Mortem

From Spring 2003: Final Exam   Solutions   Post-Mortem

From Spring 2002: Final Exam   [No solutions]   Post-Mortem

From Spring 2001: Final Exam   [No solutions or post-mortem]

Chapter Summaries from Hopcroft, Motwani, and Ullman

Useful Links

Dexter Kozen's Home Page

Learning Perl On-Line [Suggested by: Joseph Morel]:

Safari Books On-line, then search or follow Programming --> Perl --> Learning Perl, 3rd Edition

Learning Perl, 3rd Edition Page, then navigate or press "Start Reading"

Learning Perl, Third Edition Page

CPAN (Comprehensive Perl Archive Network)

Perl Source Code (CPAN / Source)

Perl Binaries (CPAN / "Ports")

O'Reilly's Perl Products Page

Perl On-Ramp

Michael Sipser's Book's Home Page

Hopcroft, Motwani, and Ullman's Book Web Page

Dictionary of Algorithms and Data Structures

Pumping Lemma Poem [Suggested by: Ben Karas]

DDD: Perl Debugger [Suggested by: Dave Johnson]

Perltidy: A Perl Pretty Printer [Suggested by: Dave Johnson]

The Alan Turing Internet Scrapbook

A TM implemented in Conway's Game of Life [Suggested by: Dave Monk]

Automata Library for Haskell [Courtesy of: Leon Smith]

Eric Klavins' Self-Assembly Research

The Mortality Problem for Matrices of Low Dimensions