This course examines what can be computed, what cannot, and what can be computed efficiently. Students study finite automata, context-free grammars, pushdown automata, and Turing machines as progressively more powerful models of computation, and then confront the limits of computation itself through decidability and complexity. The course is taught constructively: rather than treating these models as abstractions on a page, students implement them as working simulators and use them to answer concrete questions about real languages and real programs.
Dial in: +1 585-969-5075 · PIN 894 153 012# · more numbers
Posted before the session they're used in and kept available all term. Each set is a self-contained page — read it, work the examples, and bring questions.
The schedule is aligned to the LIU Brooklyn academic calendar; any session affected by a University holiday or closure is adjusted and announced in class and on Brightspace. The current week is highlighted.
| Week | Sessions | Topic | Materials | To do |
|---|---|---|---|---|
| WK 1 | S1 · Sep 3 | Course overview. Sets, proofs, strings, alphabets, and formal languages | Notes 01 |
|
| WK 2 | S2–S3 · Sep 8, Sep 10 | Deterministic finite automata: definition, computation, and construction | Notes 02 |
|
| WK 3 | S4–S5 · Sep 15, Sep 17 | Nondeterministic finite automata and the subset construction | Notes 03 |
|
| WK 4 | S6–S7 · Sep 22, Sep 24 | Regular expressions, equivalence with automata, and closure properties | Notes 04 · soon |
|
| WK 5 | S8–S9 · Sep 29, Oct 1 | The pumping lemma for regular languages. Myhill–Nerode and minimization Project 1 due |
Notes 05 · soon |
|
| WK 6 | S10–S11 · Oct 6, Oct 8 | Context-free grammars, derivations, parse trees, and ambiguity | Notes 06 · soon |
|
| WK 7 | S12–S13 · Oct 13, Oct 15 | Pushdown automata and the equivalence of PDAs and CFGs | Notes 07 · soon |
|
| WK 8 | S14–S15 · Oct 20, Oct 22 | The pumping lemma for context-free languages. Parsing in practice Project 2 due |
Notes 08 · soon |
|
| WK 9 | S16–S17 · Oct 27, Oct 29 | Turing machines: the model, configurations, and variants | Notes 09 · soon |
|
| WK 10 | S18–S19 · Nov 3, Nov 5 | The Church–Turing thesis. Decidable and recognizable languages | Notes 10 · soon |
|
| WK 11 | S20–S21 · Nov 10, Nov 12 | Undecidability, diagonalization, and the halting problem | Notes 11 · soon |
|
| WK 12 | S22–S23 · Nov 17, Nov 19 | Mapping reductions and Rice's theorem Project 3 due |
Notes 12 · soon |
|
| WK 13 | S24 · Nov 24 | Time complexity, the class P, nondeterminism, and the class NP◦ Nov 26 — no class (Thanksgiving) Capstone proposal due |
Notes 13 · soon |
|
| WK 14 | S25–S26 · Dec 1, Dec 3 | NP-completeness, the Cook–Levin theorem, and polynomial-time reductions | Notes 14 · soon |
|
| WK 15 | S27–S28 · Dec 8, Dec 10 | Space complexity and PSPACE. Capstone presentations | Notes 15 · soon |
|
| FINALS | Dec 14 – 21 | Final capstone deliverables due. No final examination. | ||
This course is graded entirely on four hands-on projects — there are no exams. Specifications and rubrics are released at least two weeks before each due date. Every project is submitted as a Git repository plus a written report; late work is reduced by 10% per calendar day.
Build a simulator that accepts DFA and NFA definitions, decides string membership, converts NFA to DFA by subset construction, and compiles regular expressions into automata. Includes a test suite and a written argument for the correctness of the conversion.
Design a context-free grammar for a small domain-specific language and implement a parser and a pushdown-automaton simulator for it. The written component addresses ambiguity and demonstrates, with a pumping-lemma argument, a language the grammar cannot capture.
Implement a Turing machine simulator supporting multiple tape variants, encode several decidable and recognizable languages on it, and produce a written demonstration of why the halting problem cannot be solved by any such machine.
Build a reduction toolkit that transforms instances of one NP-complete problem into another (for example, 3-SAT to Clique to Vertex Cover), verify the transformations empirically with a solver, and present the complexity argument in a technical report and a live presentation.
Every project is graded on the same four criteria. Each project rubric is released with its specification.
| Criterion | Weight | What is assessed |
|---|---|---|
| Correctness and completeness | 35% | The artifact does what the specification requires, and the required cases are handled. |
| Implementation quality | 20% | Structure, readability, and evidence of testing. Commit history shows sustained individual work. |
| Analysis and written report | 25% | The report explains the design, justifies the decisions, and reports results honestly, including what did not work. |
| Demonstration and defense | 20% | The student can run the artifact live and answer questions about any part of it. |
| Letter | Range % | GPA |
|---|---|---|
| A | 93–100 | 4.00 |
| A- | 90–92 | 3.67 |
| B+ | 87–89 | 3.33 |
| B | 83–86 | 3.00 |
| B- | 80–82 | 2.67 |
| C+ | 77–79 | 2.33 |
| C | 73–76 | 2.00 |
| C- | 68–72 | 1.67 |
| D | 60–67 | 1.00 |
| F | < 60 | 0.00 |
| Synchronous class sessions | 51 h |
| Review of posted notes | 30 h |
| Project 1 — Automata Simulator | 17 h |
| Project 2 — Grammars and Parsing | 20 h |
| Project 3 — Turing Machine Workbench | 20 h |
| Project 4 — Capstone and presentation | 22 h |
| Total | 160 h |
College-level discrete mathematics and programming proficiency in a language of your choice, or permission of the instructor.
All class sessions are held live on Google Meet at the scheduled times. Students are expected to attend, to have their development environment running, and to be able to share their screen when demonstrating work. Every student presents current work and takes part in critique at each meeting.
Modes of communication are Brightspace (lms.liu.edu) and email; expect a reply within 24 hours. Virtual office hours are held by appointment — email the instructor to schedule.
All course notes, examples, and project specifications are distributed through the course repository and this site. Students are responsible for reviewing the current version before each session.
Every project is submitted through Brightspace as a link to the student's Git repository, together with the written report. Commit history is part of the evidence of individual work. Late work is reduced by 10% per calendar day. Extensions are granted only for a documented medical or family emergency, requested before the deadline by email.
Projects are individual work unless a specification explicitly designates a team deliverable. Discussing approaches is fine, but submitted code, models, and writing must be your own. Generative AI tools may be used as a learning aid and are treated like any other reference: any AI-assisted portion of a submission must be disclosed in the project report, and you must be able to explain and defend every line of what you submit.
Recording of class sessions by students is not permitted without the instructor's prior written consent.
Students with a documented disability/impairment who require reasonable accommodations should provide an Accommodation Letter from Student Support Services (Sloan Building, 1st Floor · 718-488-1044 · studentsupportservices@brooklyn.liu.edu · Mon–Fri 9am–5pm).
For issues with Brightspace, LIU email, Google Meet, or campus network access, contact IT: It@liu.edu · 718-488-3300 (Mon–Fri 9am–5pm).