COSE215: Theory of Computation, 2025 Spring
Course Information
- Instructor: Jihyeok Park (박지혁)
- Office: 609A, Science Library Bldg (과학도서관)
- Email: jihyeok_park@korea.ac.kr
- Lecture: 13:30–14:45 Mondays and Wednesdays @ 301, Aegineung (애기능생활관)
- Teaching Assistant:
- Office hours: 14:00–16:00 Tuesdays (by appointment)
Course Materials
- Self-contained lecture notes are provided.
- Reference: Introduction to Automata Theory, Languages, and Computation (3rd Edition)
- Previous Exams
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:
- JDK >= 8 - https://www.oracle.com/java/technologies/downloads/
- sbt - https://www.scala-sbt.org/download.html
- Scala - https://www.scala-lang.org/download/
Schedule
| # | Date | Title | Code | Homework | ||
|---|---|---|---|---|---|---|
| Part 0: Basic Concepts | ||||||
| 0 | 03/05 | Course Overview | ||||
| 1 | 03/10 | Mathematical Preliminaries | ||||
| 2 | 03/12 | Basic Introduction of Scala | code | hw01 (by 03/26) | ||
| Part 1: Finite Automata | ||||||
| 3 | 03/17 | Deterministic Finite Automata (DFA) | code | |||
| 4 | 03/19 | Nondeterministic Finite Automata (NFA) | code | |||
| 5 | 03/24 | ε-Nondeterministic Finite Automata (ε-NFA) | hw02 (by 04/07) | |||
| 6 | 03/26 | Regular Expressions and Languages | ||||
| 7 | 03/31 | Equivalence of Regular Expressions and Finite Automata | ||||
| 8 | 04/02 | Closure Properties of Regular Languages | ex01 | |||
| 9 | 04/07 | The Pumping Lemma for Regular Languages | hw03 (by 04/21) | |||
| 10 | 04/09 | Equivalence and Minimization of Finite Automata | ex02 | |||
| Part 2: Pushdown Automata | ||||||
| 11 | 04/14 | Context-Free Grammars (CFGs) and Languages (CFLs) | ||||
| 12 | 04/16 | Examples of Context-Free Grammars | ||||
| 13 | 04/21 | Parse Trees and Ambiguity | ||||
| 04/23 | Midterm Exam | Lectures 1 - 13 | ||||
| 14 | 04/30 | Pushdown Automata (PDA) | ||||
| 15 | 05/05 | Examples of Pushdown Automata | hw04 (by 05/19) | |||
| 16 | 05/07 | Equivalence of Pushdown Automata and Context-Free Grammars | ||||
| 17 | 05/12 | Deterministic Pushdown Automata (DPDA) | ||||
| 18 | 05/14 | Normal Forms of Context-Free Grammars | ||||
| 19 | 05/19 | Closure Properties of Context-Free Languages | hw05 (by 06/02) | |||
| 20 | 05/21 | The Pumping Lemma for Context-Free Languages | ||||
| Part 3: Turing Machines / Computability | ||||||
| 21 | 05/26 | Turing Machines (TMs) | ||||
| 22 | 05/28 | Examples of Turing Machines | ||||
| 23 | 06/02 | Extensions of Turing Machines | hw06 (by 06/16) | |||
| 24 | 06/04 | The Origin of Computer Science | ||||
| 25 | 06/09 | Undecidability | ||||
| 26 | 06/11 | P, NP, and NP-Complete Problems | ||||
| 27 | 06/16 | Course Review | ||||
| 06/23 | Final Exam | Lectures 14 - 26 | ||||