|
Activities Before Classes
|
|
Week #1: January 10–14, 2005
|
|
Monday, January 10
|
Lecture #1
|
Introduction to the Course
|
|
Wednesday, January 12
|
Lecture #2
|
Introduction to Deterministic Finite Automata
|
|
Thursday, January 13
|
Common Tutorial
|
Mathematics Review
|
|
Friday, January 14
|
Lecture #3
|
Design and Verification of DFAs
|
|
Week #2: January 17–21, 2005
|
|
Monday, January 17
|
Lecture #4
|
Design and Verification of DFAs
|
|
Wednesday, January 19
|
Lecture #5
|
Nondeterministic Finite Automata
|
|
January 17–19
|
Individual Tutorials
|
Languages, Decision Problems,
and Interpretation of DFAs
|
|
Thursday, January 20
|
Common Tutorial
|
Design and Verification of DFAs
|
|
Friday, January 21
|
Lecture #6
|
Equivalence of DFAs and NFAs
|
|
Week #3: January 24–28, 2005
|
|
Monday, January 24
|
Lecture #7
|
Epsilon-NFAs
|
|
Wednesday, January 26
|
Lecture #8
|
Equivalence of DFAs and Epsilon-NFAs
Introduction to Regular Expressions
|
|
January 24–26
|
Individual Tutorials
|
Design and Verification of DFAs
|
|
Thursday, January 27
|
Common Tutorial
|
Questions and Answers for
Assignment #1
|
|
Friday, January 28
|
Lecture #9
|
Regular Expressions
|
|
|
|
Assignment #1
is Due at 4:00pm
|
|
Week #4: January 31–February 4, 2005
|
|
Monday, January 31
|
Lecture #10
|
Proving Properties of Regular Expressions
|
|
Wednesday, February 2
|
Lecture #11
|
Equivalence of Regular Expressions and Finite Automata
|
|
January 31 – February 2
|
Individual Tutorials
|
Interpretation and Design of NFAs and epsilon-NFAs
|
|
Thursday, February 3
|
Common Tutorial
|
Regular Expressions
|
|
Friday, February 4
|
Lecture #12
|
Pumping Lemma for Regular Languages
|
|
Week #5: February 7–11, 2005
|
|
Monday, February 7
|
Lecture #13
|
Pumping Lemma for Regular Languages
|
|
Wednesday, February 9
|
Lecture #14
|
Closure Properties for Regular Languages
|
|
February 7–9
|
Individual Tutorials
|
Equivalence of Finite Automata and Regular Expressions
|
|
Thursday, February 10
|
Quiz #1
|
Finite Automata and Regular Expressions
|
|
Friday, February 11
|
Lecture #15
|
Closure Properties for Regular Languages
|
|
Week #6: February 14–18, 2005
|
|
Monday, February 14
|
Lecture #16
|
Introduction to Context-Free Grammars
|
|
Wednesday, February 16
|
Lecture #17
|
Context-Free Grammars: Strings and Derivations
|
|
February 14–16
|
Individual Tutorials
|
Proving Languages are (or are not) Regular
|
|
Thursday, February 17
|
Quiz #2
|
Proving Languages are (or are not) Regular
|
|
Friday, February 18
|
Lecture #18
|
Languages of Context-Free Grammars
|
|
Reading Days &mdash No Lectures or Tutorials:
February 21–25, 2005
|
|
Week #7: February 28–March 4, 2005
|
|
Monday, February 28
|
Lecture #19
|
Ambiguous Grammars and Languages
|
|
Wednesday, March 2
|
Lecture #20
|
Grammars in Chomsky Normal Form
|
|
February 28–March 2
|
Individual Tutorials
|
Interpretation, Design, and Verification of CFGs
|
|
Thursday, March 3
|
Common Tutorial
|
Questions and Answers for
Assignment #2
|
|
Friday, March 4
|
Lecture #21
|
Grammars in Chomsky Normal Form
|
|
|
|
Assignment #2
is Due at 11:00am
|
|
Week #8: March 7–11, 2005
|
|
Monday, March 7
|
Lecture #22
|
Chomsky Normal Form
|
|
Wednesday, March 9
|
Lecture #23
|
Chomsky Normal Form and Parsing
|
|
March 7–9
|
Individual Tutorials
|
Ambiguity and Inherent Ambiguity
|
|
Thursday, March 10
|
Midterm Test
|
Regular Languages and Basic Properties of CFGs
|
|
Friday, March 11
|
Lecture #24
|
Pumping Lemma for Context-Free Languages
|
|
Week #9: March 14–18, 2005
|
|
Monday, March 14
|
Lecture #25
|
Pumping Lemma for Context-Free Languages
|
|
Wednesday, March 16
|
Lecture #26
|
Closure Properties for Context-Free Languages
|
|
March 14–16
|
Individual Tutorials
|
Chomsky Normal Form
|
|
Thursday, March 17
|
Common Tutorial
|
Proving Languages are (or are not) Context-Free
|
|
Friday, March 18
|
Lecture #27
|
Introduction to Turing Machines
|
|
Week #10: March 21–25, 2005
|
|
Monday, March 21
|
Lecture #28
|
Turing Machines and Halting
|
|
Wednesday, March 23
|
Lecture #29
|
Programming Techniques for Turing Machines
|
|
March 21–23
|
Individual Tutorials
|
Proving Languages are (or are not) Context-Free
|
|
Thursday, March 24
|
Quiz #3
|
Advanced Concepts for CFGs
|
|
Friday, March 25
|
Good Friday
|
No Lectures or Tutorials
|
|
Week #11: March 28–April 1, 2005
|
|
Monday, March 28
|
Lecture #30
|
Turing Machine Variants
|
|
Wednesday, March 30
|
Lecture #31
|
Turing Machine Variants
|
|
March 28–30
|
Individual Tutorials
|
Interpretation and Design of Turing Machines
|
|
Thursday, March 31
|
Quiz #4
|
Interpretation and Design of Turing Machines
|
|
Friday, April 1
|
Lecture #32
|
Turing Machine Encodings and Simulations
|
|
Week #12: April 4–April 8, 2005
|
|
Monday, April 4
|
Lecture #33
|
Turing Machines and Real Computers
|
|
Wednesday, April 6
|
Lecture #34
|
Recursive and Recusively Enumerable Languages
Decidable Problems
|
|
April 4–6
|
Individual Tutorials
|
Turing Machine Variants and Simulations
|
|
Thursday, April 7
|
Quiz #5
|
Turing Machine Variants and Simulations
|
|
Friday, April 8
|
Lecture #35
|
Undecidability: Reductions
|
|
Week #13: April 11–April 15, 2005
|
|
Monday, April 11
|
Lecture #36
|
Reductions and Closure Properties
Proofs of Undecidability
|
|
Wednesday, April 13
|
Lecture #37
|
Reductions and Undecidability
|
|
April 11–13
|
Individual Tutorials
|
Reductions and Undecidability
|
|
Thursday, April 14
|
Common Tutorial
|
Questions and Answers for
Assignment #3
|
|
Friday, April 15
|
Lecture #38
|
Proof That the Halting Problem is Undecidable
|
|
|
|
Assignment #3
is Due at 11:00am
|
|
Activities After Classes: April 18–30, 2005
|
|
Thursday, April 21
|
CSUS Exam Review for CPSC 313
|
3–5 pm in ES 162
|
|
Friday, April 22
|
Final Examination
|
8–11am in ICT 121
|
This page was most recently changed on Tuesday, April 19, 2005 by
Wayne Eberly.
