next up previous
Next: Required Reading

CSE396 Course Information, Spring 2017


Dr. Kenneth W. Regan, 326 Davis Hall, 645-4738,

TAs and UTAs:

Chaowen Guan:
Minwei Ye:

Ashish Tyagi:

Office Hours:

Note the Tue.+Wed. coverage before HWs are due on Thursdays. My Friday 1-2pm hours are primarily for my graduate seminar, hence Minwei Ye's at the same time take precedence for this course, but I'm available for private discussion and extended HWs can be given to me then. TA office hours are in/outside Davis 301, the shared TA space.

Assignments and Answer Keys

  1. Assignment 1 Answer key
  2. Assignment 2 Answer key
  3. Assignment 3 Answer key
  4. Assignment 4 Answer Key
  5. Assignment 5 Answer Key
  6. Assignment 6 Answer Key
  7. Assignment 7 Answer Key
  8. Assignment 8, plus notes on Two-Tape TMs and RAM simulation. Answer Key
  9. Assignment 9 Answer Key
  10. Assignment 10 Answer Key
Sample Prelim II (A modified merge of last year's main and makeup Prelim IIs; the extra problem marked X is not covered this year. Now with problem (5) fixed.) Its answer key.

Spring 2016 Final, plus alternate problem (5). Its answer key.

Answer Key of our Prelim I.

Answer Key of our Prelim II.

Printed Syllabus

Supplementary lecture notes on the Myhill-Nerode Theorem. Note too that this is covered in the Chapter 1 problems section, and both editions of Sipser give the proof (both directions) in the answers section.

Scans of handwritten handout on induction proofs and context-free grammars, featuring "Structural Induction": page 1, page 2. (May be changed)

Supplementary handout on Chomsky normal form conversion, with a worked-out example. (This spells things out more than the text does in its proof of Theorem 2.9---adding two optional steps removing "dead" and "unreachable" variables---but it's the same process.)

Piazza page

Lecture Notes for 2017---to be accumulated

Lectures and Recitations:

TuTh 11:00--12:20pm in Cooke 121
Mondays 8:00--8:50am, in Hochstetter 139
Mondays 4:00--4:50pm, in Hochstetter 139
Mondays 3:00--3:50pm, in Cooke 127A
Thursdays 3:30--4:20pm, in Norton 214
Tuesdays 3:00--3:50pm, in Cooke 508.
Recitations do not meet in Week 1.


Nature and Purposes of the Course

The first main objective of the course is to convey those major concepts and results in the theory of computation that guide our thinking about the power of computers and the problems we can solve with them. This includes the entire historical origin of the field in the work of Alan M. Turing, John von Neumann, and Stephen C. Kleene. Finite automata, regular expressions, context-free (and other) grammars, pushdown automata, and idealized programs (if not the Turing machine, think of the Java Virtual Machine) are tools of everyday computing practice. Computational complexity theory asks the fundamental question of how much time, memory, and other computational resources computers need to solve certain problems, and today is relied upon for Internet security.

A second main objective is not as "concrete" as the above-listed syllabus material, but is just as important. Computers are by-nature entirely formal entities---they do precisely what is prescribed in programming languages that are ultimately formal and mathematical. Not just to reason about them, but even to communicate effectively in the field and on the job, one must be able to state assertions precisely and design prototypes concisely. This requires fluency in the underlying mathematical language used to describe problems, computations, and objectives. This course gives valuable training in formal modes of reasoning, analysis, and presentation.

Extra Resources (some may be used officially)

Setup instructions for the "Turing Kit" DFA/TM simulator (optional).

Items From Previous Semesters

Spring 2016 Lecture Notes---Spring 2017 will generate new notes on the fly and have some change in time spent on certain topics, but will overall follow this sequence fairly closely:

Lecture Notes

Spring 2015 Lecture Notes---Spring 2016 will generate new notes on the fly but follow this sequence fairly closely.

Week 1 Scribe Notes

Week 2 Scribe Notes (part B).

Week 3 Scribe Notes

Week 4 Scribe Notes (part B)

Week 5 Scribe Notes (Both lectures in one fi le now)

Week 6 Scribe Notes (part B)

Week 7 Scribe Notes

Week 8 Scribe Notes (part B)

Week 9 Scribe Notes (part B)

Week 10 Scribe Notes (part B)

Week 11 Scribe Notes (part B)

Week 12 Scribe Notes

Week 13 Scribe Notes (part B)

Week 14 Scribe Notes (part B).

Week 2-or-3 recitation notes: page 1, page 2, page 3.

ASCII text pseudocode for the FA-to-regexp algorithm, expressed using a matrix of regular expressions.

Supplementary handout on Chomsky normal form conversion, with a worked-out example. (This is from the mid-1990s with Martin's text---the notation is different from lecture but the process is the same.)