back to cs386-syllabus

CS386 - Teaching Material - Fall 2008

Lectures

  1. 9/18/08: Course overview. Basic set theory. Set operations and their properties. Issues with the naive approach: the Russell's paradox.

  2. 9/23/08: Functions. Injections, Surjections and Bijections. Equinumerous sets. Countable and uncountable sets. Countability of N, Z, NxN and Q. Existence of uncountable sets: Cantor's theorem.

  3. 9/25/08: Elements of propositional logic. Propositional statements and their interpretations. Connectives and truth tables. Tautologies. Proof techniques: by contradiction, by contrapositive and by induction. More on cardinalities: equinumerosity of P(N) and R.

  4. 9/30/08: Alphabets, strings and languages. Language operations: concatenation and star closure. Language generation and language recognition. Finite State Automata. Transition function, extended transition function. Language accepted by a DFA. Transition Graphs. Examples. Java simulation of a DFA.

  5. 10/2/08: Nondeterministic Finite State Automata (NFA). Transforming NFAs into equivalent DFAs: the Subset Construction.

  6. 10/7/08: Proof of correctness of the Subset Construction.

  7. 10/9/08: State minimization of DFAs.

  8. 10/14/08: Preparation to MT1.

  9. 10/16/08: Regular expressions: syntax and semantics. From regular expressions to NFAs (MT1 canceled due to fire Drill).

  10. 10/21/08: MT1

  11. 10/23/08: Review of MT1. From NFAs to Regular Expression.

  12. 10/28/08: Grammars. The Chomsky hierarchy. Regular Grammars. Equivalence between DFAs and Regular Grammars. A bad case for the Subset Contruction. HW assignment given (see assignments). Date of MT2 announced (see announcements).

  13. 11/4/08: Existence of nonregular languages: Pumping Lemma.

  14. 11/11/08: Preparation to MT2. Closure Properties of Regular Languages.

  15. 11/13/08: MT2

  16. 11/18/08: Review of MT2. Note on Project: deadline extended to Tuesday 11/25/08.

  17. 11/20/08: Work on Homework Assignment.

  18. 11/25/08: Preparation to the Final examination. Parse Trees. Ambiguity.


Assignments

  1. 10/28/08: HW (revised 11/4/08). Due Tuesday, 11/18/08 before class. Deadline extended to Tuesday 11/25/08 at the beginning of class.


Announcements

  1. 10/7/08: MT1 will take place on Thursday 10/16/08. Topics: chapters 1 and 2 except grammars. Sample MT1.

  2. 10/9/08: Monday, 10/13/08, OHs are canceled.

  3. 10/25/08: Thursday, 11/20/08, there will be no lecture. Students can come to class and complete their HW assignment. Deadline extended until Thursday 11/20.

  4. 10/28/08: Thursday, 11/13/08. MT2. Comprehensive. 11/4/08: Update on MT2. Topics: up to chapter 4 inclusive. Closed book, closed notes. Sample MT2

  5. 11/14/08: Office Hours on Thu 11/20 are canceled.

  6. 11/25/08: Sample Final

Downloads

CSNS - Computer Science Network Services

Assignments and exams should be uploaded by the due date through the CSNS - Computer Science Network Services website. If you have never used this system before then follow the instructions for students.