CS 451 Spring 2007  >  Syllabus

CS 451 Spring 2007

COURSE:   CS 451 Automata and Formal Languages. 3 credits.
  Time & place:   1–2 p.m. MWF, 309 Gruening.
  Prerequisites:   CS 201 and MATH 307. Prerequisites will be enforced.
INSTRUCTOR:   Glenn G. Chappell, Computer Science.
  Office:   201B Chapman.
  Office hours:   2:15 M–F or by appointment (but feel free to stop by any time!).
  Office phone:   [474-]5736. This is also voice mail.
  E-mail:   ffggc@uaf.edu
TEXT:   Hopcroft, Motwani, and Ullman, Automata Theory, Languages, and Computation, 3rd ed., Addison-Wesley, 2007.
WEB PAGE:   http://www.cs.uaf.edu/2007/spring/cs451

Course Topics & Goals

CS 451 is about the theory behind computation. It deals with the question, “What is it possible for a computer to do?” We will be studying various models of computation and determining what each is capable of. Topics include introduction to proof, automata, finite automata, regular expressions, and regular languages, push-down automata, context-free grammars, and context-free languages, Turing machines and decidability, and intractable problems.

Important Dates

Fri, Mar 9   In-class midterm exam
Fri, Mar 23   Last day to withdraw
Fri, Apr 27   No class (UAF SpringFest)
Mon, May 7   Last regular class meeting
Fri, May 11   Final exam 1–3 p.m. in the classroom


Class meetings will be conducted using a lecture-discussion format.

Readings & Homework — Readings from the text will be assigned frequently. Homework will be assigned roughly weekly, and will include both written work and some programming.

Quizzes — Short in-class quizzes will be given, unannounced. However, possible quiz topics will be announced in advanced.

Exams — Two exams will be given: midterm and final. The final will be comprehensive, emphasizing material covered after the midterm. See “Important Dates”.


Course grades will be based on points earned, using a 90-80-70-60 scale. The lowest two quiz scores and the lowest homework score will be dropped. Point totals will be as follows.

Assignments and Quizzes (total)   200 pts
Midterm Exam    100 pts
Final Exam   100 pts
TOTAL   400 pts


No make-up quizzes will be given.

Students are expected to be at every class meeting on time, and are responsible for all class content, whether present or not. If absence from class is necessary, in-class work (other than quizzes) and homework may be made up only if the instructor is notified as soon as possible; in particular, absences due to scheduled events must be arranged ahead of time.

Academic dishonesty will not be tolerated, and will be dealt with according to UAF procedures.

Students in this class must pay the CS lab fee. Payment allows access to the Chapman 103 lab.

UAF academic policies: http://www.uaf.edu/catalog/current/academics
CS Department policies: http://www.cs.uaf.edu/cs/Policies.html

CS 451 Spring 2007: Syllabus / Updated: 17 Jan 2007 / Glenn G. Chappell / ffggc@uaf.edu Valid HTML 4.01!