Courses / COSE215 Schedule ↓
COSE215: Theory of Computation, 2024 Spring
Note that this page is outdated. Please refer to the recent course page.
Course Information
- Instructor: Jihyeok Park (박지혁)
- Office: 609A, Science Library Bldg (과학도서관)
- Email: jihyeok_park@korea.ac.kr
- Lecture: 13:30–14:45 Mondays and Wednesdays @ 604, Woojung Hall of Informatics (우정정보관)
- Teaching Assistant: Jungyeom Kim (김준겸)
- 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
Part 0: Basic Concepts
- 003/04 Course Overview
- 103/06 Mathematical Preliminaries ex01sol ex01sol
- 203/11 Basic Introduction of Scala hw01by 03/25 hw01by 03/25 code
Part 1: Finite Automata
- 303/13 Deterministic Finite Automata (DFA) code
- 403/18 Nondeterministic Finite Automata (NFA) code
- 503/20 ε-Nondeterministic Finite Automata (ε-NFA) hw02by 04/03 hw02by 04/03 code
- 603/25 Regular Expressions and Languages code
- 703/27 Equivalence of Regular Expressions and Finite Automata
- 804/01 Closure Properties of Regular Languages ex02 ex02
- 904/03 The Pumping Lemma for Regular Languages hw03by 04/17 hw03by 04/17
- 1004/08 Equivalence and Minimization of Finite Automata ex03 ex03
Part 2: Pushdown Automata
- 1104/10 Context-Free Grammars (CFGs) and Languages (CFLs) code
- 1204/15 Examples of Context-Free Grammars
- 1304/17 Parse Trees and Ambiguity
- 04/24 Midterm Exam Lectures 1 - 13
- 1404/29 Pushdown Automata (PDA) code
- 1505/01 Examples of Pushdown Automata hw04by 05/20 hw04by 05/20
- 1605/06 Equivalence of Pushdown Automata and Context-Free Grammars
- 1705/08 Deterministic Pushdown Automata (DPDA)
- 1805/13 Normal Forms of Context-Free Grammars
- 1905/15 Closure Properties of Context-Free Languages hw05by 05/29 hw05by 05/29
- 2005/20 The Pumping Lemma for Context-Free Languages
Part 3: Turing Machines / Computability
- 2105/22 Turing Machines (TMs) code
- 2205/27 Examples of Turing Machines
- 2305/29 Extensions of Turing Machines hw06by 06/12 hw06by 06/12
- 2406/03 The Origin of Computer Science
- 2506/05 Undecidability
- 2606/10 P, NP, and NP-Complete Problems
- 2706/12 Course Review
- 06/19 Final Exam Lectures 14 - 26