| |
Topics |
Assignments
|
|
Week 1
01/07 - 01/11 |
Introduction to the course.
Sets, Relations and functions
(1.1, 1.2, 1.3)
Finite and infinite sets. Countability (1.4)
|
|
|
Week 2
01/14 - 01/18 |
Proof techniques (1.5)
Closures and algorithms (1.6)
|
HW-01 due 01/19
HW-01: Solution
|
|
Week 3
01/21 - 01/25 |
Alphabets and languages (1.7)
Finite representation of languages
Regular expressions and regular languages (1.8)
|
HW-02 due 01/26
HW-02: Solution
|
|
Week 4
01/28 - 02/01 |
Deterministic Finite State Automata (2.1)
Non-Deterministic Finite State Automata (2.2)
|
HW-03 due 02/02
HW-03: Solution
|
|
Week 5
02/04 - 02/08 |
TEST on Chapter 1
Finite automata and regular expressions. (2.3)
Non-regular languages. The Pumping Theorem (2.4)
|
|
|
Week 6
02/11 - 02/15 |
State minimization (2.5)
Algorithms for FSA. FSA as algorithms (2.6)
|
|
|
Week 7
01/18 - 02/22 |
Context-free languages, context-free grammars (CFGs) (3.1)
Parse trees (3.2)
|
HW-04 due 02/23
HW-04: Solution
|
|
Week 8
02/25 - 02/29 |
TEST on Chapter 2
Push-down automata (3.3, 3.4)
|
|
|
Week 9
03/03 - 03/07
|
Non-CF Languages. Algorithms for CFGs. (3.5, 3.6)
Context-Free Grammars - Parsing (3.7)
|
HW-05 due 03/08
HW-05: Solution
|
|
|
Spring break (03/08-03/16)
|
|
|
Week 10
03/17 - 03/21 |
TEST on Chapter 3
|
|
| |
Easter recess Monday 04/24
|
|
|
Week 11
03/26 - 03/28 |
Canceled
|
|
|
Week 12
03/31 - 04/04 |
The definition of a Turing machine (4.1)
Computing with Turing machines (4.2)
|
|
|
Week 13
04/07 - 04/11 |
Extensions of Turing machines.
Random-access Turing Machines. Non-deterministic machines
(4.3, 4.4, 4.5)
Grammars, Chomsky Hierarchy. Numerical functions (4.6, 4.7)
|
HW-06 due 04/13
|
|
Week 14
04/14 - 04/18 |
The Church-Turing thesis. Universal Turing machines.
The Halting problem.
Undecidable problems about Turing machines. (5.1, 5.2, 5.3, 5.4, 5.5)
Computational complexity (Chapter 6)
NP-completeness (Chapter 7)
Challenges for theoretical computer science and its contribution to other sciences.
http://www.research.att.com/~dsj/nsflist.html
|
|
| |
Final exam : Thursday 04/24, 10:15 - 12:15 pm
|
|