COMP 310 Automata, Languages, and Computation

Syllabus - Spring 2009

Professor: John Noga (jnoga@csun.edu) (x6480)
Lectures: JD 3508 TR 11:00-12:15 or SG108 R 19:00-21:45
Office Hours: JD 4429 - TR 12:30-13:15 & 18-18:45, W 12:00-13:00
Text: An Introduction to Formal Languages and Automata - Linz
LMS: moodle.csun.edu

Course Objectives: Improved problem solving ability and understanding of the fundamental capabilities and limitations of computation. These objectives will be achieved primarily through the formal investigation of relationships between machines and languages. Topics will include automata (eg DFA, PDA, TM), grammars (eg right linear, context free), and languages classes (eg regular, context free, recursive).

Tentative Weekly Schedule:
Jan 20 - Jan22: Intro / Review / Preliminaries
Jan 27 - Jan 29: DFAs and NFAs
Feb 3 - Feb 5: Minimization of DFAs and Regular Expressions
Feb 10 - Feb 12: Equivalences (DFA/NFA/RegExp/RegularGrammars)
Feb 17 - Feb 19: Pumping Lemma (regular) and Closure Properties
Feb 24 - Feb 26:  Catch Up, Review, Exam
Mar 3 - Mar 5: Context Free Grammars and Chomsky Normal Form
Mar 10 - Mar 12: Grieback Normal Form and Parsing
Mar 17 - Mar 19: DPDAs / NPDAs and Equivalences (NPDA/CFG)
Mar 24 - Mar 26: Pumping Lemma (context free) and Closure Properties
Mar 31 - Apr 2: Chavez Holiday & Catch Up and Review
Apr 7 - Apr 9: Spring Break
Apr 14 - Apr 16: Exam and Turing Machines
Apr 21 - Apr 23: Turing Machine Variants and Hierarchy Questions
Apr 28 - Apr 30: Introduction to Decidability
May 5 - May 7: Introduction to P and NP
May 12 - May 14: Final Exam (Tue 10:15-12:15 or Thur 20:00-22:00)

Homework: Homework will be assigned through the semester. For each you will electronically submit a pdf file via moodle.csun.edu. Each assignment will have a selection of problems graded. In addition, a small number of points will be determined based upon its appearance/form. The purpose of these appearance points it to encourage professional looking work. Late homework will not be accepted.

Grading: Your grade will be based upon your scores on 2 midterms (20% each), 1 final (40%), and homework assignments (20%). Your combined percentage can be converted to a grade using the values from the table (which may be slightly reduced at the professor's discretion).
 

 A  92%
 A-  90%
B+  88%
 B  82%
 B-  80%
C+  78%
 C  72%
 C-  70%
D+  68%
 D 62%
 D- 60%

F  0%

Academic Dishonesty: The typical penalty for any form of academic dishonesty is an F for the course and being reported to the Vice President for Student Affairs. Note that facilitating the academic dishonesty of others is a form of academic dishonesty. In this course all homework assignments and exams are assigned to individuals. Students may discuss homework problems. Students may explain what needs to done and suggest methods to accomplish the tasks. However, submitting work which is identical or nearly identical is cheating. Submitting work done by others or a solution you do not understand is cheating. What you submit should reflect your understanding of the material. Further details on academic dishonesty can be found in the CSUN catalog. If there is any doubt as to what constitutes academic dishonesty ask the professor.