CSE 457 Spring 2010
Theory of Formal Languages Syllabus
This document is available at http://www.public.asu.edu/~ccolbou/src/457syllabuss10.html
CSE 457 is a second course in
the theory of formal languages.
Topics to be Covered:
 Shallit Chapter 1  done
 Shallit Chapter 3, Sections 3.13.9 and beginning of 3.10  done
 Shallit Chapter 4, Sections 4.14.4
 Shallit Chapter 7, Sections 7.17.2
The primary learning objectives of CSE 457 are to address two objectives of the CS major in more detail than is treated in CSE 355, namely (1) apply knowledge of computing and of mathematics appropriate to Computer Science, and (2)
apply mathematical foundations, algorithmic principles, and computer science theory in the modeling and design of software and demonstrate the comprehension of the tradeoffs involved in design choices.
The grading for undergraduates in the class is as follows:

Homework Assignments  five at 6% each  30%
Always due at the start of class.
Written documentation detailing medical treatment or a family emergency is required in order to make alternate arrangements for homework submission.
Homework 1 (Out 28 January, Due 11 February, Returned 18 February).
Homework 2 (Out 11 February, Due 25 February, Returned 04 March).
Homework 3 (Out 25 February, Due 23 March, Returned 30 March).
Homework 4 (Out 23 March, Due 13 April, Returned 22 April.
Homework 5 (Out 15 April, Due 29 April, Returned 04 May).
 Midterm Exam 1  15%  23 February in class
 Midterm Exam 2  15%  30 March in class
 Final Exam (Open Book and Notes)  40%  12:102:00 Thursday 06 May
The grading for graduate students in the class is as follows:

Homework Assignments  five at 5% each  25%
(as above)
 Midterm Exam 1  15%  23 February in class
 Midterm Exam 2  15%  30 March in class
 Project  45%  Due 06 May at 2:00 p.m., with in class presentation to be scheduled earlier.
The individual project topic is to be selected prior to spring break, and should concern an area in which the theory of formal languages is applied (e.g., network protocols, natural language understanding, coding theory, software correctness).
The project is an individual effort enabling the student to explore applications that the course cannot treat.
An 810 page wellresearched document is expected.
Shallit's book suggests possible projects at the end of each chapter,
and potential topics will also be discussed in class.
Undergraduates preferring the graduate course workload should speak to the instructor to see if the requirements can be varied to accommodate their interests.
Approval for undergraduates to pursue projects must be obtained by 16 February at the latest, or the student will be assumed to be following the undergraduate requirements.
General Course Information:
Students may discuss homework
assignments with their classmates; however all work turned in is expected
to be that of the individual. If you have any questions regarding appropriate
collaboration please see the instructor.
We will follow the text closely, but the emphasis on the tests will be the same as that in the lectures. Hence, although class attendance is not required, it is highly recommended.