COSE215: Theory of Computation, 2024 Spring

COSE215: Theory of Computation, 2024 Spring

Note that this page is outdated. Please refer to the recent course page.

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:

Schedule

# Date TitlePDFCodeHomework
Part 0: Basic Concepts
0 03/04 Course Overview
1 03/06 Mathematical Preliminariesex01
(sol)
2 03/11 Basic Introduction of Scalacode
hw01
(by 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
(by 04/03)
6 03/25 Regular Expressions and Languagescode
7 03/27 Equivalence of Regular Expressions and Finite Automata
8 04/01 Closure Properties of Regular Languagesex02
9 04/03 The Pumping Lemma for Regular Languageshw03
(by 04/17)
10 04/08 Equivalence and Minimization of Finite Automataex03
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 Automatahw04
(by 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 Languageshw05
(by 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 Machineshw06
(by 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