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:

	Final exams can be picked up in 5136 Upson during normal hours. Bring your Cornell ID with you.
	See "Office Hours" below for an updated schedule.
	Solutions for Prelim #2 are posted under "Exams".
	Exam 2 Concept list from last year available here
	See handout on converting to one-state PDA, with example.
	HW8 problem 3 deferred one week. Details below
	Exam 1 Concept list from last year available here
	Old exams are now available online.
	Please write your netID on the front of each homework problem you submit.
	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)
Tuesday	3pm - 4pm Hopcroft (Upson 5144) DEC. 14 W/B THE LAST DAY FOR OFFICE HOURS
Wednesday	11am - 12pm Hopcroft (Upson 5144)
Thursday	3pm - 4pm Hopcroft (Upson 5144)
Friday	11am - 12pm Hopcroft (Upson 5144) NO OFFICE HOURS ON DEC. 10.

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:

		Homework assigned every Friday and is due the following Friday in class; No late homework excepted.
		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.
		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[solution], 2.3.4 [Solutions: a b c] , 2.5.2 [solution] ,2.5.3 [solution]

Assignment #3: See Handout.

Please submit your solutions on 4 sheets of paper:

problems 1,2,3 [solutions]
problems 4,5
problems 6,7 [solutions]
problems 8,9 [Solution]

Assignment #4: See Handout

problem 1
problem 3.2.2
problem 3 [Solutions]
problems 4.2.1 [Solution]

Assignment #5: See Handout

problem 1(4.2.1) [Solution]
problem 2
4.2.6 by Machine Const. [Solution]
problem 4 (4.2.6 by homomorphism, etc) [Solution]
problem 5 [Solution]

Assignment #6: See Handout

Please submit your solutions on 4 sheets of paper:

problems 1,2, [Solutions]

problems 3,4 [Solutions]

problems 5,6 [Solution]

problems 7 [Solution]

Assignment #7: See Handout

Please submit your solutions on 4 sheets of paper:

problem 1 [Solution]

problem 2[Solution], problem 3

problem 4 (6.2.2b)[Solution]

problem 5 [Solution]

Assignment #8: See Handout

Please submit your solutions on 4 sheets of paper:

1. problems 1 [Solution], 2 [Solution]
   2. problem 3 [Solution]
   3. problem 4 [Solution]
   4. problem 5 [Solution]

Assignment #9: See Handout

Please submit your solutions on 5 sheets of paper:

   1. problem 1 [Solution]
    2. problem 2 [Solution]
    3. problem 3 [Solution]
    4. problem 4 [Solution]
    5. problem 5 [Solution]

Assignment #10: See Handout

Problem 1 [Solution]
Problem 2 [Solution]
Problem 3 [Solution]
Problem 4

Assignment #11: See Handout

Please submit your solutions on 4 sheets of paper:

   1. problem 1 [See Book P. 380]
    2. problem 2 [Solution]
    3. problem 3 [Solution]
    4. problem 4

Assignment #12: See Handout

Please submit your solutions on 4 sheets of paper:

    1. problem 1 [Solution]
    2. problem 2 [Solution]
    3. problem 3 [Solution]
    4. problem 4 [Solution]

Assignment #13: See Handout

Please submit your solutions on 4 sheets of paper:

   1. problem 1 [See Book P.455 and 456]
    2. problem 2 [Solution]
    3. problem 3 [Solution]
    4. problem 4 [Solution]

Assignment #14: See Handout [Solution]

Exams:

(Both prelims will be in-class examinations)

Prelim #1: Friday, October 1 Prelim #1 (2004) Solution
Prelim #2: Friday, November 5 Prelim #2 (2004) Solution
Final Exam: December 15, 9-11:30am - Upson B17

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/28/2005 16:00