From: Subject: CS 345/541 Date: Fri, 29 Aug 2008 10:10:32 -0400 MIME-Version: 1.0 Content-Type: text/html; charset="Windows-1252" Content-Transfer-Encoding: quoted-printable Content-Location: file://C:\Documents and Settings\csmith.AD\Local Settings\Temporary Internet Files\OLK55\syllabus-CS345-541 (3).html X-MimeOLE: Produced By Microsoft MimeOLE V6.00.2900.5579 CS 345/541
CS 345/541 Automata Theory and Formal = Languages=20
Fall 2008

Official Course Description. This course gives an introduction = to=20 formal languages and their relation to automata. Topics include = deterministic=20 and non-deterministic finite automata, regular expressions and = languages,=20 closure properties and decision procedures for context-free languages, = recursive=20 and recursively enumerable sets, Turing machines, and decidability. Some = aspects=20 of computational complexity may also be explored.=20

Prerequisites. CS142, and MA211 or MA346.=20

Location and Times. Snell 169, MWF 1:00-1:50.=20

Instructor. Alexis Maciel. Science Center 379, 268-2385,=20 alexis@clarkson.edu.=20

Office Hours. M 2:00-3:30, Tu 2:30-3:30, W 2:00-3:30, Th = 2:30-3:30.=20

Required Text. Michael Sipser, Introduction to the Theory = of=20 Computation, 2nd edition, Thomson Course Technology, 2006. ISBN=20 0-534-95097-3.=20

Course Objectives.=20

  1. To teach you concepts and results that constitute the foundations = of=20 computing, that is, the knowledge that allows us to understand what=20 computation is. These include the Turing machine, the existence of = undecidable=20 problems, and the P versus NP question.=20

  2. To teach you concepts and results of practical importance such as = those=20 related to regular expressions, context-free grammars, undecidability = and=20 NP-completeness.=20

  3. To increase your ability to think and communicate clearly.=20
Demonstrable outcomes. By the end of the semester,=20
  1. You will have a good understanding of concepts and results from = the theory=20 of computation, covering the range of topics listed below.=20

  2. You will be able to solve problems related to those topics. =

Topics to be covered. Deterministic and nondeterministic = finite=20 automata, regular expressions, regular languages, the Pumping Lemma,=20 context-free grammars, pushdown automata, context-free languages, = deterministic=20 and nondeterministic Turing machines, the Church-Turing thesis, and = undecidable=20 problems (essentially, most of Chapters 1 to 5). Time permitting, some = notions=20 of computational complexity, such as time and space complexity, the = classes P=20 and NP, and NP-completeness (Chapter 7).=20

Grading. Your evaluation will be based on several homework = assignments=20 (A), two tests (T) and a final exam (F). Your course grade will be = computed=20 using the following formula:=20

25% A + 25% T1 + 25% T2 + 25% F

The final exam will not be cumulative. At the final exam, you will = have the=20 option of writing make-up exams for Tests 1 and 2. Tentative dates for = the tests=20 are Thursday, October 16 and Thursday, November 13. These will be = evening exams.=20 All students are required to write the final exam (no exemptions).=20

Policy for missed work. There will be no make-up assignments. = Late=20 assignments may be accepted if a good excuse is provided and if = arrangements are=20 made at a reasonable time, in advance, if possible. Make-up tests can be = arranged under the same conditions. Other special arrangements can be = made for=20 students forced to miss more than a few days of class.=20

Laptops and other electronic devices. These are permitted in = class=20 only for the purpose of taking notes. Nothing else. Please turn off your = phone=20 ringers while in class.