CSC250
Theory of Computation
(Spring 2017)

Last Update:

Detailed Syllabus

Homework assignments due Tuesdays @midnight. You may deposit files in our Moodle course.

Notes & Assignments: These are web-access restricted links. Access those pages using name/pass determined by course #.

Week#
Dates
Notes
 Topics
(high-level)		 Topics
(detail)		 Critchlow
-Eck
Maheshwari
-Smid
 Assignments
Exams
Due Date
Assigns Feedback
0
J27
 Notes1 Overview Proofs §2.6 Counting ∞
§1.3 Proof Tech
A0
A0 Feedback
J31
1
J30,F1,3
 Notes2
Notes3
Notes4 		Proofs.
Countable & Uncountable.
Regular expressions. 		Power set.
Countable & uncountable.
Rationals: countable.
Cantor's diagonal argument.
Hierarchy of ∞'s.
Regular Languages 		§ 2.6 Counting ∞ (pp.114-125).
§ 3.1,3.2 RegEx (pp.139-146).
§5.2: Countable sets (pp.160-163).
A1
A1 Feedback
F7
2
F6,8,10
 Notes5
Notes6
Notes7		 Regular expressions
Python regex		 § 3.3: pp.146-149.
§ 2.7 RegEx (pp. 52-56).
A2
A2 Feedback
F14
3
F13,15,17
 Notes8
Notes9
Notes10 		DFA's / NFA's. Pumping lemma. DFA ↔ Language.
NFA ↔ Language. 		§ 3.4: pp.150-157.
§ 2.2: pp.23-30.
A3
A3 Feedback
F21
4
F20,22,24
 Notes11
Notes12
Notes13 		NFA ⇔ DFA
RegEx ⇔ NFA
Pumping Lemma 		§ 3.5: pp.160-163.
§ 3.6: pp.163ff.
§ 2.5: pp.41-47.
A4
A4 Feedback
F28
5
F27,M1,3
 Notes14
Notes15
Notes16 		§ 3.7: pp.171-4.
§ 2.9: pp.67-73.
A5
A5 Feedback
M7
Grammars
CFG's
6
M6,8,10
 Notes17
Notes18
Notes19 		Grammars
  § 4.1: pp.175-86
§ 3.1: pp.87-99.
↓
 
M13-17
    
Spring Break
  
7
M20,22,24
 Notes20
Notes21
Notes22 		Grammars, PDA's, LR(k) parsing. LR(1) parsing
PDA's
DPDA's
§ 4.4: pp.174-82.
§ 3.5-3.7: pp.108-20.
A6
A6 Feedback
M28
8
M27,29,31
 Notes23
Notes24
Notes25 		Turing machines. Turing Machines § 5.1: pp.197-203.
§ 4.1, 4.2: pp.133-42.
A7
A7 Feedback
A4
9
A3,5,7
 Notes26
Notes27
Notes28 		Multitape TMs
Decidability
Chomsky Normal Form		  
§ 4.3 pp.143-146
§ 4.4: p.146
§ 5.1: p.153
A8
A8 Feedback
A11
10
A10,12,14
 Notes29
Notes30
Notes31 		Halting problem "Mid-Term" Assessment.
Halting undecidable		  
§ 5.1-3
A9
Quiz9 Feedback
A9 Feedback
A18
11
A17,19,21
 Notes32
Notes33
Notes34		 Enumerable langs
Complexity theory
P=NP
RandGroups for week
  
Chap.5, § 5.4-5.6
Chap.6
ProjectIdeas
Project Teams/Dates
Updated 24Apr
Complexity theory
12
A24,26,28
   Project presentations    
Final Project Links
13
M1,3
   
M9-12
 
Exam Period
Final Project due
Fri 12 May
 
   
Return to CSC250 Class Homepage: