COSE215: Theory of Computation, 2025 Spring

COSE215: Theory of Computation, 2025 Spring

Course Information

Course Materials

Installation of Scala and sbt

Scala is a general-purpose programming language combining object-oriented and functional programming in one concise, high-level language. Scala’s static types help avoid bugs in complex applications, and its JVM and JavaScript runtimes let you build high-performance systems with easy access to huge ecosystems of libraries.

The interactive build tool sbt is built for Scala and Java projects.

Please download and install them using the following links:

Online Automata Simulator

Schedule

# Date Title PDFUpdateCodeHomework
Part 0: Basic Concepts
0 03/05 Course Overview

08/29
(17:36)

1 03/10 Mathematical Preliminaries

08/29
(17:36)

2 03/12 Basic Introduction of Scala

08/29
(17:36)

code
hw01
(by 03/26)
Part 1: Finite Automata
3 03/17 Deterministic Finite Automata (DFA)

08/29
(17:36)

code
4 03/19 Nondeterministic Finite Automata (NFA)

08/29
(17:36)

code
5 03/24 ε-Nondeterministic Finite Automata (ε-NFA)

08/29
(17:36)

code
hw02
(by 04/07)
6 03/26 Regular Expressions and Languages

08/29
(17:36)

code
7 03/31 Equivalence of Regular Expressions and Finite Automata

08/29
(17:36)

8 04/02 Closure Properties of Regular Languages

08/29
(17:36)

ex01
9 04/07 The Pumping Lemma for Regular Languages

08/29
(17:36)

hw03
(by 04/21)
10 04/09 Equivalence and Minimization of Finite Automata

08/29
(17:36)

ex02
Part 2: Pushdown Automata
11 04/14 Context-Free Grammars (CFGs) and Languages (CFLs)

08/29
(17:36)

code
12 04/16 Examples of Context-Free Grammars

08/29
(17:36)

13 04/21 Parse Trees and Ambiguity

08/29
(17:36)

04/23 Midterm Exam Lectures 1 - 13
14 04/30 Pushdown Automata (PDA)

08/29
(17:36)

code
15 05/05 Examples of Pushdown Automata

08/29
(17:36)

hw04
(by 05/19)
16 05/07 Equivalence of Pushdown Automata and Context-Free Grammars

08/29
(17:36)

17 05/12 Deterministic Pushdown Automata (DPDA)

08/29
(17:36)

18 05/14 Normal Forms of Context-Free Grammars

08/29
(17:36)

19 05/19 Closure Properties of Context-Free Languages

08/29
(17:36)

hw05
(by 06/02)
20 05/21 The Pumping Lemma for Context-Free Languages

08/29
(17:36)

Part 3: Turing Machines / Computability
21 05/26 Turing Machines (TMs)

08/29
(17:36)

code
22 05/28 Examples of Turing Machines

08/29
(17:36)

23 06/02 Extensions of Turing Machines

08/29
(17:36)

hw06
(by 06/16)
24 06/04 The Origin of Computer Science

08/29
(17:36)

25 06/09 Undecidability

08/29
(17:36)

26 06/11 P, NP, and NP-Complete Problems

08/29
(17:36)

27 06/16 Course Review

08/29
(17:36)

06/23 Final Exam Lectures 14 - 26