BCS 402 · Dr. Arash Kermani · CUD

Student tools — all 63 problems

One self-explanatory HTML tool per assigned problem. Each: theory + animated demo + Q&A notes.

Round 1 = 30 pts · Round 2 = 30 pts · Round 3 = 40 pts

Round 1 · Lectures 5–8 · Undecidability & reductions (30 pts each)

Lecture 5 — Diagonalization & halting

Cantor's diagonal

A_TM-undecidable table

Decidable/Recognizable Venn

Closure properties

P61 · CLO-1 · R1.9

Bridge theorem (constructive proof)

Lecture 6 — Reductions for undecidability

HALT_TM via A_TM

E_TM undecidable

EQ_TM mapping reduction

Lecture 7 — Computation-history method

Computation-history viewer

E_LBA undecidable

ALL_CFG undecidable

A_DFA, E_DFA, A_CFG

Post Correspondence

P62 · CLO-1 · R1.14

A_LBA decidable vs E_LBA undecidable

Lecture 8 — Recursion theorem & Rice

Rice's theorem checker

Recursion fixed point

Round 2 · Lectures 9–12 · NP & Cook–Levin (30 pts each)

Lecture 9 — Time complexity & P

Growth-rate race

Single-tape {0ⁿ1ⁿ}

Single-tape vs two-tape

Big-O classifier

TM running-time profiler

Lecture 10 — NP & verifiers

Verifier vs brute force

Interactive SAT

HAMPATH verifier

P-class showcase

COMPOSITES verifier

Lecture 11 — Cook–Levin

Cook-Levin tableau

3SAT → CLIQUE

Cook-Levin (specific)

P63 · CLO-3 · R2.12

NP ⊆ EXPTIME via NTM determinization

Lecture 12 — More NP-complete problems

3SAT → HAMPATH

3SAT → 3COLOR

SAT self-reducibility

Round 3 · Lectures 13–16 · Space & hierarchy (40 pts each)

Lecture 13 — Space, PSPACE, Savitch

Space vs time chart

PSPACE = NPSPACE

EXPTIME vs PSPACE

Lecture 14 — PSPACE-complete games

TQBF₃ normal form

Generalized Geography

TQBF → Geography

Generalized chess

Generalized Hex

Lecture 15 — L, NL, Immerman–Szelepcsényi

Log-space machine

PATH NL-complete

Inductive counting

Lecture 16 — Hierarchy theorems

Space hierarchy

REGEX-EQ EXPSPACE-complete

Every tool's structure

Theory — formal theorem in a gold box + intuition
Animated demo — auto-plays on load, loops, ⏸/▶ Pause/Play, Step, Reset, Speed (0.25× – 3×), narrated step-by-step
Q&A defence notes — 3-5 anticipated peer questions with model answers