CPT S 317: Automata and Formal Languages
Spring 2017School of EECSWashington State University, PullmanMWF 10:10-11:00SLOAN 169
Instructor:AnanthKalyanaraman(pronounced: “An-anth” “Kal-ya-na-ra-man”)EME [email protected] Hours:Wednesdays 2:30-3:30pm
Introduce concepts in automata theory and theory of computationIdentify different formal language classes and their relationshipsDesign grammars and recognizers for different formal languagesProve or disprove theorems in automata theory using its propertiesDetermine the decidability and intractability of computational problems
Very broadly, the course will contain three parts:Part I) Regular languagesPart II) Context-free languagesPart III) Turing machines & decidability
TA1TBDTA2:TBDCheck course website for any updates
CPT S 122/132: Data StructuresMath 216: Discrete Structures
Introduction to Automata Theory, Languages and ComputationBy J.E. Hopcroft, R. Motwani, J.D. Ullman3rdEditionAddison Wesley/PearsonCourse book homepage:http://infolab.stanford.edu/~ullman/ialc.htmlSolutions to starred exercises in the textbook & ErrataOSBLE+ (Online Studio-Based Learning Environment):http://plus.osble.orgThe Gradiance Resource (optional)
http://www.eecs.wsu.edu/~ananth/CptS317Why do I need to check the webpage?Lecture NotesHomeworks will be posted on the webpageA tentative schedule will also be posted and maintainedMisc. static information about the courseHow frequently do I need to keep checking the course webpage?Ideally once every day, and if not at least once before/after each class (for lecture notes)
The OSBLE+ Web Portal
We will use OSBLE+ for discussions, class announcements, and for email communication with instructor.Every student needs to register in OSBLE+ and should check the portal regularly. All important (dynamic) announcements will be made through this portal.Registration instructions are on the course website.
How to get in touch with the instructor and the TA(s)?
OSBLE+ (for email and dashboard public discussion forums)Office hoursWeekly oncepreferred way to meet one-on-oneNo need for prior appointment if meeting during the office hourIn addition, the instructor will be available outside of office hours to meet (appointments preferred for this mode).
8 homeworks (60%) - (best 7 policy)2 midterms (20%)1 final (20%)Grading Policy:Curved
Homework Submission Policy
Hardcopy to be submittedin classon the due dateEarly submissions allowedNo late submissionsExtensionsmaybe permitted under extraordinary circumstancesContact the instructorat least 1 week priorHomeworks will be posted on the course website
All homework must be doneindividuallyCheating:Helping others, getting help, looking up website for solutions, etc.Students caught cheating will be awarded anFgrade, and will be subjected to the WSU academic dishonesty policy.If something is not clear, on what constitutes and what does not, please consult the instructor in advance.
2 Midterms and 1 Final exam.Closed book, closed notes, comprehensiveMake-ups will be rare and only under extraordinary circumstancesSeek prior permission from instructor (at least 2 weeks in advance)
A tentative schedule has been posted and will be maintained on the course websiteSubject to change as course progressesBookmark & keep checkingRecommended frequency: once a weekLook for exam schedules as well here
Classes will involveboth Slides + Board(to roughly equal degrees)Lecture slides available onlineHowever, no scribes from class will be made availableSo, take your own notes in classFor latest/updated slides, download before eachuseUse of laptops and smart phonesnotallowed in classroom.