next up previous
Next: Required Reading

CSE396 Course Information, Spring 2019


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

TAs and UTAs:

Yuhao Du,
Le Fang,
Chaowen Guan,
Junxuan Huang,
Corey Ropell (UTA),

Office Hours:

There will be ample coverage before HWs are due on Thursdays. TA office hours are in/outside Davis 301, the shared TA space.

Lectures and Recitations:

TuTh 11:00--12:20pm in Norton 112
Mondays 8:00--8:50am, in Cooke 127A
Mondays 4:00--4:50pm, in Norton 210
Mondays 3:00--3:50pm, in Cooke 127A
Thursdays 3:30--4:20pm, in Norton 213
Tuesdays 3:00--3:50pm, in Clemens 106
Thursdays 8:00--8:50am, in Norton 210
Thursdays 2:00--2:50pm, in Norton 213
Recitations do not meet in Week 1.

Printed Syllabus


Assignments and Answer Keys (will appear here, note 2018 assignments below)

  1. Assignment 1, due Fri. 2/15, 11:59pm
  2. Assignment 2, due Thu. 2/21, 11:59pm
  3. Assignment 3, due Thu. 2/28, 11:59pm
  4. Assignment 4, due Thu. 3/7, 11:59pm
  5. Assignment 5, due Thu. 3/28, 11:59pm (TopHat portion now 1 attempt only)
  6. Assignment 6, due Fri. 4/5, 11:59pm
  7. Assignment 7, due Thu. 4/11, 11:59pm
  8. Assignment 8, due Thu. 4/18, 11:59pm
  9. Assignment 9, due Thu. 5/2, 11:59pm
  10. Assignment 10, due Thu. 5/9, 11:59pm

Sample Final Exam (from 2018)

Review Session Notes, together with whiteboard photos from office hours: pic1, pic2.

Lecture Notes in 2019 (will appear here, see below for previous years)

2019 Piazza page

Extra Resources (some may be used officially)

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

Week 3 recitation notes (updating previous ones that were here): CSE396S19week3recs.pdf. Possible Week 4 extra: CSE396S19week4recs.pdf.

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

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.

New: Typeset and expanded handout on "Structural Induction" using context-free grammars.

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.)

New: Notes on Turing Machines and PDAs (some sideways):

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.

Items From Previous Semesters

Lecture Notes from 2018

Spring 2018 Assignments (left up on purpose, answer keys will be re-linked thru Piazza)

  1. Assignment 1
  2. Assignment 2
  3. Assignment 3
  4. Assignment 4
  5. Assignment 5
  6. Assignment 6
  7. Assignment 7
  8. Assignment 8,
  9. Assignment 9
  10. Assignment 10

Lecture Notes from 2017

Spring 2016 Lecture Notes