Content

NFA to DFA conversion Reference Slides4Azedeh Farzan slidesA 33 min video : Reference Slides5

Week	Topic	Sipser chapter(s)
Week 1	Review of Sets, functions, etc.; Introduce Strings and Languages	Chapter 0 and Chapter 1.
Week 2	Regular language; closure under union; Non-Determinism; algorithm for converting NFA to DFA.	Ch 1
Week 3	Regular Expressions. Kleene's Theorem; Algorithms for converting among re, DFA, NFA. Pumping Lemma. Enumeration; countably infinite sets; diagonalization proof.	Chapter 1
Week 4	Pumping Lemma plus Closure theorems for Regular Languages; Intro to CFGs	Chapter 1.4	NFA to r.e. conversion; Pumping Lemma to prove {ww': w ∈ {0,1}* and w' is bit-flip of w} is not regular
Week 5	Context Free Languages	Ch 2
Week 6	CFGs continiued; Contains Regular Languages; Chomsky Normal Form	Ch 2 (cont'd) Reference Slides6 Reference Slides7: Pumping Lemma CFLs
Week 6	Set Cardinality	Pp 202-205
Week 7	Turing Machines; Turing Machines	Ch 3 2016 Test 1 solutions Sample Test 2 (which we covered in class, almost to the end) Sample Test 1 with a Pumping Lemma quiz appended. Jeff Edmonds' slides on uncountability Alan Turing Scrapbook, Jeff Edmonds' slides on Models of Computation
Week 8	Study Days	Office hours are by appointment	Study Days
Week 9	Formal Defn TM; Variations on the standard TM; Nondeterminism, multitape, etc.	Ch 3 cont'd
Week 10	Church-Turing Thesis. Universal TM (not covered in Text). Decidable Languages and Turing Recognizable Languages	Ch 4;
Week 11	Undecidability and the Halting Problem. Reducibility.	Ch 4-5.
Week 12	Time complexity; NP-complete	Ch 5. Ch 7.
Week 13	NP-completeness	Ch 7 cont'd Shiyan Hu's NP-completeness slides; Power Point slides from GSU on reductions.	Practice Final (PDF)
Week 14	NP-completeness, Summary, Review	Ch 7

Grading Scheme:

• Assignments

There will be approximately 7 assignments; their total worth is 30 percent of your final grade.

Paper assignments will be accepted in person. Electronic assignments can be emailed to gara dot pruesse at viu dot ca. Scans of handwritten assignments will not be graded, but will be permitted as proof of completion by the deadline as long as the physical original is handed in on or before the first workday after the assignment is due.

Each assignment will have a specified due date, and any assignments handed in after the due date, within 24 hours, will have 10% penalty; after 24 hours it will not be accepted.

• Midterms and Quizzes
There will be two midterms and two quizzes; see the week-by-week schedule for the dates.
Midterm 1: 15 Midterm 2: 15 Quiz 1: 2.5 Quiz 2: 2.5 Total: 35

 
• Final Exam
In addition, there will be a final exam worth 35 per percent. A student must pass the final exam to pass the course.

 


Grades will be distributed as follows:

A+ >= 90.0	A >= 85.0	A- >= 80.0
B+ >= 76.0	B >= 72.0	B- >= 68.0
C+ >= 64.0	C >= 60.0	C->= 55.0
D   >= 50.0		F otherwise