COSE215: Theory of Computation, 2024 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 @ 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
  • Midterm: 2023
  • Final: 2023

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	PDF (handout)	Code	Homework
Part 0: Basic Concepts
0	03/04	Course Overview
1	03/06	Mathematical Preliminaries			ex01 (sol)
2	03/11	Basic Introduction of Scala		code	hw01 (due: 03/25)
Part 1: Finite Automata
3	03/13	Deterministic Finite Automata (DFA)		code
4	03/18	Nondeterministic Finite Automata (NFA)		code
5	03/20	ε-Nondeterministic Finite Automata (ε-NFA)		code	hw02 (due: 04/03)
6	03/25	Regular Expressions and Languages		code
7	03/27	Equivalence of Regular Expressions and Finite Automata
8	04/01	Closure Properties of Regular Languages			ex02
9	04/03	The Pumping Lemma for Regular Languages			hw03 (due: 04/17)
10	04/08	Equivalence and Minimization of Finite Automata			ex03
Part 2: Pushdown Automata
11	04/10	Context-Free Grammars (CFGs) and Languages (CFLs)		code
12	04/15	Examples of Context-Free Grammars
13	04/17	Parse Trees and Ambiguity
04/24		Midterm Exam	Lectures 1 - 13
14	04/29	Pushdown Automata (PDA)		code
15	05/01	Examples of Pushdown Automata			hw04 (due: 05/20)
16	05/06	Equivalence of Pushdown Automata and Context-Free Grammars
17	05/08	Deterministic Pushdown Automata (DPDA)
18	05/13	Normal Forms of Context-Free Grammars
19	05/15	Closure Properties of Context-Free Languages			hw05 (due: 05/29)
20	05/20	The Pumping Lemma for Context-Free Languages
Part 3: Turing Machines / Computability
21	05/22	Turing Machines (TMs)		code
22	05/27	Examples of Turing Machines
23	05/29	Extensions of Turing Machines			hw06 (due: 06/12)
24	06/03	The Origin of Computer Science
25	06/05	Undecidability
26	06/10	P, NP, and NP-Complete Problems
27	06/12	Course Review
06/19		Final Exam	Lectures 14 - 26