CS381 - Fall 2004

Lecture: Monday, Wednesday, and Friday  9:05a-9:55a  HO B14

[Announcements] [Course Staff] [Office Hours] [CS381 -or- CS481] [Regrades]
[Textbooks] [Homework] [Exams] [Lecture Topics] [Newsgroup]


Announcements:

 
bullet Old exams are now available online. solution will follow shortly.
bullet Please write your netID on the front of each homework problem you submit.
bullet In addition to the newsgroup, there is an email list that has been setup to correspond with the course staff. Please send all course related questions to cs381-l@lists.cs.cornell* rather than directly to Professor Hopcroft or to one of the TAs. You are likely to get a faster response by using this address rather than emailing one of us directly.

Course Staff:
  Office Email Address
Professor John Hopcroft Upson 5144 jeh@cs.cornell*
Ron Hose Upson 328 rh228
Dan Sheldon Upson 328 dsheldon@cs.cornell*
Frans Adjie Effendi Upson 328 fae2
Radhika Lakshmanan Upson 328 rl223
     
Course Staff Mailing List   cs381-l@lists.cs.cornell*
*: Dont forget to put .edu after these addresses when you are sending email.

Office Hours:
Monday 11am - 12pm Hopcroft (Upson 5144)

4 PM - 5:30 PM Radhika (Upson 328)
Tuesday 3pm - 4pm Hopcroft (Upson 5144)
Wednesday 11am - 12pm Hopcroft (Upson 5144) 
Thursday

3pm - 4pm Hopcroft (Upson 5144)
Friday 11am - 12pm Hopcroft (Upson 5144)

CS381 -or- CS481:

 CS381 and CS481 follow roughly the same syllabus, but CS481 is somewhat faster paced and goes into more depth. It is meant for more theoretically inclined students, grad students, and undergrads bound for grad school. Corrective shifting is encouraged in the first few weeks of the semester.

Regrades:

 To apply for a regrade, please attach a note to the assignment explaining the reason you feel it should be regraded and hand it in with the next week's homework assignment. Assignments will not be eligible for a regrade unless the request is received with the homework following the week in which it was handed back; after that, grades are final.

Textbook:

 Introduction to Automata Theory, Languages, and Computation / John E. Hopcroft, Rajeev Motwani, Jeffery D. Ullman -- 2nd Edition

Homework:
bullet  Homework assigned every Friday and is due the following Friday in class; No late homework excepted.
bullet You are encouraged to work in groups to solve the homework problems, however, solutions must be written in your own words and you must fully understand everything that you submit. Students suspected of violating this will be asked to explain their homework solutions in person.
bullet Homework is VERY important; at least half of your final grade will be based on your homework scores. Therefore it is very important that homework is done carefully and legibly. Unreadable homework will be returned and will receive no credit.

 

(All problems from Hopcroft, Motwani, and Ullman unless otherwise specified)

Each problem in an assignment is graded by a different TA, if you have questions about the grading, please contact to the corresponding TA.

Assignment #1: 

2.2.4 [Solution] ,2.2.5 b and d [Solution] ,2.2.6 [Solution] ,2.2.10 [Solution]

Assignment #2: 

2.3.3,2.3.4,2.5.2 [solution] ,2.5.3 [solution]

Assignment #3:

See Handout. Please submit your solutions on 4 sheets of paper:

  1. problems 1,2,3
  2. problems 4,5
  3. problems 6,7
  4. problems 8,9

Assignment #4:

See Handout

Exams:

 (Both prelims will be in-class examinations)

Prelim #1: Friday, October 1
Prelim #2: Friday, November 5
Final Exam: December 15,  9-11:30am

Here are some old exams and their solutions. We strongly suggest attempting the questions before looking at the solutions.

Prelim #1 (2003) Solution
Prelim #2 (2003) Solution
Final (2003) Solution

Prelim #1 (2002) Solution
Prelim #2 (2002) Solution
Final (2002) Solution

Lecture Topics:

Please note that this is the schedule from Fall '02. This year we will follow these topics in approximately the same order.
August 30th Introduction to Notation, Alphabets, Strings, Empty String, Sets, Empty Set, Countably Infinite Sets, Intro to Diagonalization, Definition of Finite Automata
September 2nd Deterministic Finite Automata: Formal definition, Extending delta function to (Q x SIG*), Examples; Non-deterministic Finite Automata: Informal definition, Examples
September 4th Introduction to NFA-DFA conversion, Formal definition of NFAs, Extension of Delta function to (Q X SIG*) for NFAs, Introduction to NFAs with epsilon transitions, Reversing of finite automata's
September 6th (Hartmanis) Subset Construction; How to convert a NFA to an DFA: Examples, Theorem, Brief intuitive discussion of the proof
September 9th Applications of NFAs and conversion to DFAs; Relationship between DFAs, NFAs, Epsilon-NFAs; Epsilon-closures
September 11th Regular Expressions: Definition, Operators, Examples
September 13th Notation review, Examples of Regular Expressions, Conversion of DFAs to Regular Expressions
September 16th Continuation of Examples, Converting Regular Expressions to Automata
(notes on DFA to Regular Expression conversion are here)
September 18th Converting Regular Expressions to Automata, Regular Expression Operators, Showing sets are not Regular via the Pumping Lemma
September 20th Pumping Lemma Examples, Closue Properties: Union, Intersection, Complement, -, Reverse, Homomorphisms
September 23rd Homomorphisms, Closure under Homomorphisms - Proof with Regular Expressions & Machines, Inverse of Homomorphisms
September 25th Review of homomorphisms, Closure under inverse homomorphisms, Using closed operations to show languages regular
September 27th Examples of using closed operations to show languages regular
September 30th Prove ValidComp(M) is valid using homomorphism, O(n) notation, Decision Procedures, Prove Emptiness Problem, Membership Problem and Equivalence Problem in Regular Language are all decidable.
October 2nd Testing equivalence of states, DFA minimization
October 4th Definition and Example of Context Free Grammars, Derivations of CFGs, Definition of Context Free Languages
October 7th < Prelim #1 >
October 9th Review of prelim, CFL example
October 11th Conversion of Automata to CFGs, Theorem: Regular Languages are proper subsets of CFLs, Theorem: CFLs are not closed under intersection and complement
October 16th Definition of PDAs, Equivalence of PDA accepting by final state and PDA accepting by empty stack
October 18th Construction of a CFG G for a PDA M such that L(G) = N(M), and proof of the equivalence
October 21st Chomsky Normal Form
October 23rd Converting CFG into CNF; The Pumping Lemma for CFL
October 25th Application of the Pumping Lemma for CFL's; The Substitution Theorem for CFL; Applying the Substitution Theorem to show the closure properties of CFL under union, concatenation, *, +, Homomorphisms, and Reversal; CFL is not closed under Intersection and Complement
October 27th More on Closure Properties
October 29th Decision Procedures for CFL's; Testing Membership in a CFL; Testing Emptiness of CFL's
November 1st Computer Programs are Countably Infinite; Diagonalization Lemma; Definition of Recursive Language Sets; Definition of Recursively Enumerable Language Sets
November 4th Proper contain Relation between Regular Set, CFL, Recursive Set and Recursively Enumerable Set; Definition and Notation of the Turing Machine; Instantaneous Descriptions for Turing Machines
November 6th Multiple Tracks, Multitape TMs, Equivalence of One-Tape and Multitape TMs, Nondeterministic Turing Machines, Simulating a TM by Computer, Simulating a Computer by TM
November 8th Turing Machines with Semi-infinite tapes, Multitask Machines, Counter Machine and its power, The Diagonalization Language, Proof that the Diagonalization Language is not RE
November 11th Review of Prelim 2, Decidability problems and TMs, The Halting Problem
November 13th The Halting Problem is Undecidable, Rice's Theorem, Undecidable problems for CFLs
November 15th The Diagonalization Language is not RE; {(M,x) | TM M halts on string x} is RE but not recursive (Halting Problem) and the complement is not RE; Proof that the Halting Problem is not recursive (decidable) by reduction
November 18th Halting Problem is RE but not recursive, Rice's Theorem and properties of the RE languages, Proof of Rice's Theorem by reduction
November 20th ValidComp of TMs with Intersection of CFLs, the emptiness of the intersection of two CFLs is undecidable, L(G) = Sigma* for CFLs is undecidable, the equivalence of 2 CFLs is undecidable
November 22nd The class P and examples: Membership in CFL, Prime, etc.; The class NP and examples: Hamiltonian-Circuit Problem, Factorization, Conjunctive Normal Form, Clique, etc.; Polynomial-Time reduction from CNF to Clique Problem
November 25th NP-Completeness of #-CNF problem, Proof of Cook's Theorem

Newsgroup:

 There is a newsgroup cornell.class.cs381 established for this course. It is intended for discussing CS381 related topics, interesting problems (NOT homework solutions), complaints, suggestions, etc. You can learn more about newsgroups here.



Ron Hose, Mehmet Fidanboylu
Last modified: 09/27/2004 10:29