Theory of Computation

COSC 340

šŸ“‹ General

šŸ“– Python Tutorials

šŸŒ Wikipedia

šŸ“ŗ Videos

šŸ“ Study Guides

šŸ§© Projects

šŸ“… Course Schedule

Week Date Topics Due
1 Feb 3rd (Tuesday)

Course Introduction / Math Review

For next time: Read the syllabus, download and install Java, download JFLAP, get the textbook and read Chapter 0 (mostly focusing on 0.1 and 0.2), and brush up on Python.
Feb 5th (Thursday)

Deterministic Finite Automata (DFAs)

For next time: Read 1.1 regarding DFAs. Start working on Project 1.
  • Read 0.1 and 0.2
2 Feb 10th (Tuesday)

Nondeterministic Finite Automata (NFAs)

For next time: Finish reading 1.1. Continue working on Project 1 (I strongly suggest to get started early, just in case you run into some problems with your code). Start reading 1.2.
Feb 12th (Thursday)

DFA and NFA Practice

For next time: Continue working on Project 1 (I strongly suggest to get started early, just in case you run into some problems with your code). Continue reading 1.2.
  • Read 1.1
3 Feb 17th (Tuesday)

Regular Expressions (REGEXs)

For next time: Start reading 1.3. Finish Project 1 by Thursday night. Project 2 will be assigned next time.
Feb 19th (Thursday)

Regular Expressions (REGEXs)

For next time: Continue reading 1.3. Project 2 is now assigned. Project 1 is due tonight.
  • Project 1
  • Read 1.2
4 Feb 24th (Tuesday)

Regular Expressions (REGEX)

For next time: Keep working on Project 2. Finish reading 1.3.
Feb 26th (Thursday)

Nonregular Languages (The Pumping Lemma)

For next time: Continue working on Project 2. Iā€™m going to go ahead and post Project 3 for anyone that wants to get a head start on it. Start reading 1.4.
  • Read 1.3
5 Mar 3rd (Tuesday)

Review for Exam 1

For next time: Continue working on Project 2. Finish reading 1.4. The study guide is posted for Exam 1.
Mar 5th (Thursday)

Context-Free Grammars (CFG)

For next time: Iā€™m moving Project 2 a bit to give you more time to work on it. Start reading 2.1.
  • Read 1.4
6 Mar 10th (Tuesday)

Exam 1

For next time: Finish Project 2 by tonight.
  • Project 2
Mar 12th (Thursday)

Context-Free Grammars (CFG)

For next time: Keep working on Project 3. Finish reading 2.1.
  • Read 2.1
7 Mar 17th (Tuesday)

Pushdown Automata (PDA)

For next time: Keep working on Project 3. Read 2.2
Mar 19th (Thursday)

Pushdown Automata (PDA)

For next time: Project 3 is being pushed until after break. Finish reading 2.2. We will review for Exam 2 next time.
  • Read 2.2
8 Mar 24th (Tuesday) SPRING HOLIDAY - NO CLASS
Mar 26th (Thursday) SPRING HOLIDAY - NO CLASS
9 Mar 31st (Tuesday)

Turing Machines (TMs)

For next time: Project 4 is now assigned. Finish reading 2.2. Start reading 3.1
Apr 2nd (Thursday)

Review for Exam 2

For next time: Finish Project 3 by tonight.
  • Project 3
10 Apr 7th (Tuesday)

Turing Machines (TMs)

For next time: Exam 2 is next time. Be working on Project 4.
Apr 9th (Thursday) Exam 2
11 Apr 14th (Tuesday)

Turing Machines (TMs)

For next time: Project 4 is due next time. Finish reading 3.1. Start reading 3.2 and 3.3
  • Read 3.1
Apr 16th (Thursday)

Decidability

For next time: Project 4 is due tonight. Finish reading 3.2 and 3.3. I went ahead and assigned Projects 5 and 6.
  • Project 4
  • Read 3.2
12 Apr 21st (Tuesday)

Time Complexity

For next time: Keep working on your final two projects. Read 4.2.
  • Read 3.3
Apr 23rd (Thursday)

Complexity Classes

For next time: Keep working on your final two projects. Read 7.1 and 7.2.
  • Read 4.1
13 Apr 28th (Tuesday)

Reduction

For next time: Keep working on your final two projects. Read 7.3 and 7.4.
  • Project 5
  • Read 4.2
Apr 30th (Thursday)
  • Read 7.1 and 7.2
14 May 5th (Tuesday)
  • Read 7.3 and 7.4
May 7th (Thursday)
  • Project 6
15 May 14th (Thursday) Final Exam (11:30AM - 2:00PM)