CPT S 317: AUTOMATA AND FORMAL LANGUAGES

Spring 2012, 3cr.

 

(JAN 9 - May 4)

SCHOOL OF EECS

WASHINGTON STATE UNIVERSITY

 

 

MWF 10:10 - 11:00

COLL 220

 

Current announcements    Instructor & TAs contact    Course details    Grading and other course policies    Course online resources

 

Lecture notes    Homeworks    Course schedule  

 

 

ACTIVE ANNOUNCEMENTS

 

INSTRUCTOR & TAs

 

ANANTH KALYANARAMAN

Weekly office hours: Wednesdays 13:00-14:00  @ EME 237

 

Teaching assistants:

Dmitry Dementyev

Weekly office hours: Thursdays 09:20-10:20 @ EME B31

 

Cewei Cui

Weekly office hours: Tuesdays 11:00-12:00 (noon) @ EME B31

 

 

COURSE DETAILS

 

  • Course objectives:

    • Introduce concepts in automata theory and theory of computation

    • Identify different formal language classes and their relationships

    • Design grammars and recognizers for different formal languages

    • Prove or disprove theorems in automata theory using its properties

    • Determine the decidability and intractability of computational problems

  • Prerequisites:

    • CPTS 122
    • MATH 216 or equivalent

  • Required textbook:

    • "Introduction to automata theory, languages and computation"

    # Authors: JE Hopcroft, R Motwani and JD Ullman

    # Publisher:Addison Wesley/Pearson; 3rd Edition

 

GRADING & COURSE POLICIES

  • 8 homeworks (60%)  - best 7 out of 8 will be used toward final grade.

  •  2 midterms (20%)

  • 1 final exam (20%)

Homework policy:

  • Homeworks must be submitted in class as hardcopy on the due date mentioned in the homework.  Early submissions are allowed.

  • All homeworks must be done individually. Anyone cheating will receive a zero for that assignment and will be subject to the university's academic dishonesty/integrity policy. Cheating involves giving assistance to or receiving assistance from another individual. Academic Integrity Policy (please read)

  • Late submission policy:
  •     No late submissions will be allowed on any homework. However, earlier submissions are allowed at any time before due date (either in class or can be turned in at the instructor's office).
  •     Extensions may be allowed but only under extraordinary circumstances upon contacting the instructor well in advance (generally at least 1 week prior to the submission date).

Exam policy:    

  • Closed-book, closed-notes, comprehensive
  • Midterm Exam dates and syllabus will be announced in class as the exams approach. Tentative dates for these exams are posted on the course website schedule link. Please make sure you mark these on your calendar. Make-up exams can be offered but are extremely rare and only under excruciating/emergency circumstances. If you have a problem with the date, come and see the instructor well ahead of time (at least 2 weeks prior to the exam).

 

COURSE WEBSITE, OSBLE

The course will use three different web resources for different purposes:

  1. The "course website" (i.e., this page you are reading now) is where lecture notes and homeworks will be posted, and the course schedule will be maintained. See corresponding links.
  2. The OSBLE learning portal will be used for email exchanges, email announcements, and listing of useful web links/resources.
    Please see here for instructions on how to set up your OSBLE account and other personal settings. This is NOT an optional step. All students enrolled in this class should take care of this by the first week of the semester.

 

LECTURE NOTES

 

 

COURSE SCHEDULE

 

 

HOMEWORKS

 

 

 

 

SAFETY ON CAMPUS

 

http://alert.wsu.edu

 

WSU Campus Safety Plan:    http://safetyplan.wsu.edu/

 

Get familiar with the emergency procedures from the above links.

 

STUDENTS WITH DISABILITIES

 

DRC website:    http://www.drc.wsu.edu

 

Reasonable accommodations are available for students with a documented disability. If you have a disability and may need accommodations to fully participate in this class, please visit the Disability Resource Center (DRC). All accommodations MUST be approved through the DRC (Admin Annex Bldg, Room 205). Please stop by or call 509-335-3417 to make an appointment with a disability specialist.Visit the DRC website for more information.

 

ANNOUNCEMENTS ARCHIVE

  • Homework 7 has been posted (due Wednesday April 11).
  • Homework 6 has been posted below.
  • Homework 5 has been posted below.
  • Homework 4 and its rubrics have been posted below under the Homeworks section.  
  • Homework 3 and its rubrics have been posted below under the Homeworks section.  
  • Homework 2 and its rubrics have been posted below under the Homeworks section.  
  • Homework 1 and its rubrics have been posted below under the Homeworks section.  
  • I have set up OSBLE for our course. Please see here for instructions on how to set up your OSBLE account and other personal settings. This is NOT an optional step. All students enrolled in this class should do this by January 20th.
  • Welcome to Cpt S 317, Spring 2012!