CPT S 317: AUTOMATA AND FORMAL LANGUAGES

Spring 2010, 3cr.

 

(JAN 11 - May 7)

SCHOOL OF EECS

WASHINGTON STATE UNIVERSITY

 

 

MWF 9:10 - 10:00

SLOAN 7

 

ANNOUNCEMENTS (recent)

Please fill up the course evaluations

 

COURSE DETAILS

 

The primary objectives of this course is as follows:

  • 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

 

INSTRUCTOR

 

ANANTH KALYANARAMAN

EME 237, 335-6760

Weekly office hours:  Wednesdays, 4-5pm

 

COURSE WEBSITE AND ANGEL MANAGEMENT SYSTEMS

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

  • 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 sections below.
  • The ANGEL web portal will be used for email exchanges, email announcements, and listing of useful web links/resources.
     All email correspondences with the instructor and the TAs should be sent through the Angel . Please do not use personal email ids to send from or send to the instructor/TAs, as they will be discarded.

        Angel home:    http://angel.wsu.edu/

        Angel login page:    https://lms.wsu.edu/

        Angel "Getting Started" link:    http://angel.wsu.edu/GetStarted.asp

  • Mail Alert:    Students are advised to check their ANGEL mailbox at least once a day.

 

TEACHING ASSISTANTS

 

            Barnan Das, EME 206

            Weekly office hours: Monday, 11:30-12:30

 

            Ruma Paul, Sloan 311

            Weekly office hours: Thursday, 2-3

       

 

PREREQUISITES

 

  • CPTS 122
  • MATH 216 or equivalent

 

TEXTBOOKS (REQUIRED)

  • Introduction to automata theory, languages and computation

# Authors: JE Hopcroft, R Motwani and JD Ullman

# Publisher:Addison Wesley/Pearson; 3rd Edition

 

 

GRADING

  • 8 homeworks (60%)

  •  2 midterms (20%)

  • 1 final exam (20%)

 

 

LECTURE NOTES

 

 

COURSE SCHEDULE

 

 

HOMEWORKS

 

  • (1/20) Homework 1 PDF

  • (1/27) Homework 2 PDF

  • (2/10) Homework 3 PDF

  • (3/1) Homework 4 PDF

  • (3/10) Homework 5 PDF

  • (3/26) Homework 6 PDF

  • (4/12) Homework 7 PDF

  • (4/12) Homework 8 PDF

 

 

COURSE POLICIES

Homework policy:

  • Homeworks must be submitted in class on the due date mentioned in the assignment. 

  • 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 assignment. *No late submissions* will be allowed.  However, earlier submissions are allowed
              (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 at least 1 week prior to the submission date.

Exam policy:    

  • Closed-book, closed-notes, comprehensive
  • Midterm Exam dates will be announced in class once they are finalized. Tentative dates for these exams will be posted on the course website. Make-up exams can be offered but will be 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).

 

USEFUL LINKS AND WEB RESOURCES

 

            Angel login page:    https://lms.wsu.edu/

Keep checking your ANGEL mailbox at least once a day.

 

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

  • (4/19) HW8 posted
  • (4/12) HW7 posted
  • (4/5) Midterm II review slides posted on the Lecture Notes site
  • (3/26) Homework 6 posted
  • (3/10) Homework 5 posted
  • (3/1) Homework 4 posted
  • (2/10) Homework 3 posted
  • (1/27) Homework 2 posted
  • (1/20) Homework 1 posted
  • Welcome! Please get familiar with the contents of this course website