Oscar H. Ibarra
ibarra at cs dot ucsb dot edu
Harold Frank Hall, Room 2117
Teaching Assistant:
Patricio Jara
pjara at cs dot ucsb dot edu
Announcements
Here is a sketch of the proof of the Pumping Lemma for Context Free Grammars.CYK Algorithm
*************** Midterm Rescheduled for November 3, 2009 ******************
Because of a mix-up the proctor didn't show up. The midterm is rescheduled for November 3, 9:30-10:45 AM. Apologies for the rescheduling.
The midterm and final dates are now posted below.
There will be class on Tuesday, October 20.
There is no class on Thursday, October 22. The professor made up for this lecture on Friday, October 9th.
Professor Ibarra will give a class lecture during discussion on Friday, October 9th 11:00-11:50 in Phelps 3515. Please be there!
Course Description
Topics to be covered include:Finite automata and regular expressions; properties of regular languages; pushdown automata and context-free grammars/languages; properties of context-free languages; introduction to computability/unsolvability and computational complexity.
Required Text: An Introduction to Formal Languages and Automata, Peter Linz, Jones and Bartlet Publishers.
Prerequisite:CS40
Syllabus
Schedule
Lectures: TR 9:30-10:45 (PHELPS 3505)Discussion: F 11:00-11:50 (PHELPS 3515)
Office Hours
Oscar H. Ibarra: TR 11:00-11:50 (HFH 2117)Patricio Jara: MW 1:00-1:50 (PHELPS 1413) **** NOTE THE CORRECTION ****
Conduct
Cheating will not be tolerated. Persons caught cheating will receive a grade of F in the course and a report will be filed at the Office of Student Services.Assignments
All assignments are to be turned in by the due date at the 138 Turnin Box in room 2112 Harold Frank Hall. No late assignments will be accepted.Assignment 1
Assignment 2
Assignment 3
Assignment 4
Assignment 5
Assignment 6
Exams
There will be one midterm exam and a final. The midterm and the final will be based on the material covered in the lectures and discussion sessions up to the day of the exam.Midterm: Tuesday, November 3th
Final:Wednesday, December 9th, 8:00-11:00
All exams are closed book. There will be no makeup exams.
Grading Policy
Assignments: 35%Midterm: 25%
Final: 40%