Math 220 - Theory of Computing

Course Details

Textbook

An Introduction to Formal Languages and Automata, Fourth Edition by Peter Linz, 2006 ISBN: 9780763737986 Find this book at Amazon

Overview

Two main questions arise with computational problem solving: can a problem be solved at all, and if so, how efficiently? Topics include computability and complexity theory as related to Turing machines, finite state automata, regular and context-free grammars, and the complexity classes of P and NP.

Prerequisites

CSC 207 or permission of instructor.

Quizzes and Participation

You are encouraged to attend class and participate in discussions. Active participation in class discussions and short quizzes will comprise 5% of your final grade.

Extra Credit

Extra credit for this course can be earned by participating in the Centenary Math Problem of the Week (POTW). Each reasonable submission will be worth an additional 0.5% toward your final grade, CC me with your submission for credit.

Disabilities

Centenary assures students with disabilities equal opportunity to reach the same level of achievement as other students. Strict confidentiality will be maintained on students with disabilities. Services for students with disabilities are available through the Counseling Center, located on the ground floor of Rotary Residence Hall, phone (318) 869-5424.

Honor Code

All students are bound by the Honor System. The Honor System is applicable to all academic work. See the Centenary College Handbook for the complete Honor Code.

Extensions

Each day an assignment is late, you will lose 10% of the credit for that assignment. No late work will be accepted after 5 days past the due date. This is an actual day, not a class day. You will have 2 free late days, to be used at your discretion throughout the semester. If you are turning in an assignment late, you need to email me with how many free late days you plan to use. Extensions beyond this for labs, projects, exams and quizzes are only given when circumstances beyond your control (e.g. being sick, choir or sports travel) prevent you from completing a project on time. You must notify me either by email or phone of your circumstances well in advance of the due date.

Syllabus

We will be covering most of the textbook following the format in the table of contents. We will also be using additional supplemental material such as relevant web-pages and background material. Additional readings will be assigned before material will be covered in class. You are expected to review the material and come to class prepared. As readings are assigned, they will be posted here. Course notes can be found on PicasaWeb

• August 24th: Chapter 1
• August 31st: Chapter 2
• September 16th: Chapter 3

Homework

You will have weekly Homeworks in this course, with problems assigned almost every day, for a total of 50% of your final grade. These homeworks will cover concepts we have discussed in class, and will be due approximately one week after they are assigned.

• HW1: Due Aug 31st
  Pg 14, Section 1.1 Ex 1, 5, 7, 20, 25, 31, 35
  Sample LaTeX File
• HW2: Due Sep 4th
  Pg 28, Section 1.2 Ex 1, 4, 7
• HW3: Due Sep 11th
  Pg 47, Section 2.1 Ex 6, 9, 10, 11, 15, 18, 20
• HW4: Due Sep 16th
  Pg 55, Section 2.2 Ex 6, 11, 12, 18, 19
• HW5: Due Sep 25th
  Pg 62, Section 2.3 Ex 3, 5
  Pg 69, Section 2.4 Ex 2b, 2d, 4, 7
• HW6: Due Sep 30th
  Pg 75, Section 3.1 Ex 1, 5, 8, 14, 15, 20, 24
  Pg 87, Section 3.2 Ex 5, 8, 10, 15
• HW7: Due Oct 5th
  Pg 28, Section 1.2 14a,c,e,f, 16, 21, 23 Pg 96, Section 3.3 5, 7, 13

  Exam 1 covers HW up to now

• HW8: Due Nov 4th
  Pg 183, Section 7.1, 4d,h,k, 6, 10, 11, 14 Pg 195, Section 7.2 4, 5, 6
• HW9: Due Nov 20th
  Pg 236, Section 9.1, 3, 4, 5, 7c, 7g, 8, 10

All homeworks must be written using LaTeX and turned in as a PDF on the cs server. There are many resources available for LaTeX on the web, including the LaTeX Math Symbols. Here are a few files that will assist with creating your homework PDFs.

• hwsample.pdf

  This PDF is an example of what your homework should look like when properly formatted and compiled with LaTeX.

• hwsample.tex

  This file includes the code for the LaTeX file.

• homework.sty, newalg.sty

  Two style files with a few definitions for the homework layout.

• jflap.pdf

  A figure to include in the homework pdf.

• jflap2dot.py

  A utility file to convert the XML output of JFLAP into dot format, which can be transformed into a pdf and then included in the LaTeX file.

Exams

There will be three exams, each worth 15% of your final grade. They will be take-home exams and will cover material from the homeworks.

• Exam 1: Due October 9th
• Exam 2: Due November 13th
• Final: Exam Week Time

Grading

Your final grade for this course will be based on the Homework, Project, Exams and Participation described above.

Grading Scale 90-100 A 80-89 B 70-79 C 60-69 D 0-59 F

Weights Homework 50% Participation 5% Exam 1 15% Exam 2 15% Final 15%

---

© Mark Goadrich, Centenary College of Louisiana