CSE 457/598 Fall 2012
Theory of Formal Languages Syllabus
This document is available at http://www.public.asu.edu/~ccolbou/src/457syllabusf12.html
CSE 457 is a second course in
the theory of formal languages.
Topics to be Covered:
 Shallit: primarily Chapters 1, 3, 4, 7
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 8% each  40%
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: 03 September 2012 Due: 20 September 2012 Returned: 25 September 2012)
Grades out of 50 are: Undergraduate: 19 27 35 36 40 40. Graduate: 26 29 30 32 33 33 35 36 36 36 37 37 38 41 41 44 50 50 50 50.
Homework 2 (Out: 18 September 2012 Due: 04 October 2012 Returned: 09 October 2012)
Grades out of 50 are: Undergraduate: 16 17 21 24 47. Graduate:
11 15 15 20 21 26 30 32 35 36 36 36 37 38 40 41 42 44 50.
Homework 3 (Out: 06 October 2012 Due: 29 October 2012 Returned: 30 October 2012)
Grades out of 50 are: Undergraduate: 11 16 31 44. Graduate:
19 23 27 27 30 33 35 36 37 39 42 43 43 44 44 47 47.
Homework 4 (Out: 30 October 2012 Due: 15 November 2012 Returned: 27 November 2012)
Grades out of 50 are: Undergraduate: 9 19 20 41. Graduate:
12 14 20 21 23 25 26 27 28 32 34 34 34 36 38 38 49.
Homework 5 (Out: 15 November 2012 Due: 29 November 2012 Returned: 04 December 2012)
Grades out of 50 are: Undergraduate: 13 29 41 43. Graduate:
20 29 34 36 36 42 42 42 42 43 44 45 45 47 48 49 49 49.
 Midterm Exam  20%  takehome from 31 October until 02 November
The pdf file for the midterm appears
here and the tex source for it is
here.
Grades out of 50:
Undergraduate: 5 25 27 30 31 46.
Graduate: 28 32 33 35 37 38 39 40 41 41 41 42 45 46 46 47 49 50.
 Final Exam (Open Book and Notes)  40%  takehome 69 December.
The pdf file for the final appears
here and the tex source for it is
here.
The grading for graduate students in the class is as follows:

Homework Assignments  five at 3% each (perhaps, selected questions only graded)  15%
(due dates same as undergrads)
 Midterm Exam  15%  as above
 Final Exam (Open Book and Notes)  30%  as above
 Project  40%  Due 13 December at 12 noon.
The individual project topic is to be selected prior to 08 October, 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.
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 the end of September 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.
Penalties for plagiarism and other forms of academic dishonesty range from a negative 100% on the offending item to failure in the course with a transcript designation of academic dishonesty, and for repeat offenses can result in expulsion from the program.
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.