MA308 Theory of Computation
Fall 2010
Instructor
Dr. James
Rauff, Professor of
Mathematics
Shilling Hall
203J Office Phone: 424-6249
Office
Hours: MW 1-3; TTH 9:45-10:45,1-2; F 11-12
Textbook
Elements of
the Theory of Computation (2e) by Lewis/Papadimitriou (Prentice-Hall,
2003) 0-13-262478-8
Catalogue Description
An introduction to the theory of computation emphasizing formal
languages, automata, and computability. Includes
computational complexity and NP-completeness. Prerequisite: MA 208.
Assessment
The class will run in
a quasi-seminar format. Your grade will
be based upon homework, class participation and exams. Homework will be collected and
assessed. Generally, I will examine
every exercise, but in cases where there are many similar exercises I will only
evaluate some of them. Class
participation includes answering questions, contributing to problem
solutions, presenting solutions to homework exercises, and later in the
semester, presenting material, ideas or theorems. Exams test your grasp of terminology
and theorems through typical exercises.
Your grade will be
computed as a percentage of total possible points earned. A: 93 -100%, A-: 90-92%, B+: 86-89%, B: 83-85%, B-:
80-82%, C+: 76-79%, C: 73-75%, C-: 70-72%, D+: 66-69%, D: 60-66%, F: below 60%.
Schedule
of Assignments: Last updated on December 6, 2010
|
Date |
Assignment
for today |
Topic |
|
Aug.
23 (M) |
none |
Regular
expressions & languages |
|
Aug,
25 (W) |
Read
section 1.8. Do exercises 1.8.1, 1.8.2,
1.8.3, 1.8.5, 1.8.6d on pp.51-52 |
DFA |
|
Aug.
27 (F) |
Read
section 2.1. Do exercises 2.1.2 &
2.1.3 on p.60 |
DFA |
|
Aug.
30 (M) |
Read
section 2.2 |
NDFA |
|
Sept.
1 (W) |
Do
exercises #2.2.1, 2.2.2 & 2.2.3 on pp.73-74 |
|
|
Sept.
3 (F) |
Do exercises
#2.2.6-2.2.9 on pp.74-75 |
|
|
Sept.
6 (M) |
LABOR
DAY- no class today |
|
|
Sept.
8 (W) |
Read
section 2.3. Do
exercises #2.3.4, 2.3.6abcg, 2.3.7 on
pp.83-84 |
Finite
Automata & regular expressions |
|
Sept.
10 (F) |
Read
section 2.4. Do exercises
#2.4.3de, 2.4.5 & 2.4.8abcdg |
Pumping
Lemma |
|
Sept.
13 (M) |
||
|
Sept.
15 (W) |
Hand in completed
exam on regular languages and finite automata |
|
|
Sept.
17 (F) |
Read
section 3.1 in Kinber/Smith handout. Do exercises 3.1-3.5 on p.110 of the
handout. |
|
|
Sept.
20 (M) |
Do
exercises #3.7,3.8,3.9ab,3.11 on p.111 of the K/S handout |
|
|
Sept.
22 (W) |
Read
section 3.2 in K/S handout. Do
exercises 3.13, 3.16, 3.17 on p.112 of the handout. |
|
|
Sept.
24 (F) |
Read
section 3.3 in K/S handout. Do exercises #3.18-3.22 on pp.112-114 |
|
|
Sept.
27 (M) |
Do
exercises #3.23-3.26 on p.114 of the K/S handout |
|
|
Sept.
29 (W) |
Section
3.4 of the K/S handout establishes that context-free grammars and pushdown automata
are equivalent representations of context-free languages. Use the
constructions of Theorem 3.4.1 (p.86) and Theorem 3.4.2 (p.90) to (a) Construct a PDA from the grammar
in exercise 3.15. (b) Construct a context-free grammar
from the PDA in exercise 3.20. |
|
|
Oct.
1 (F) |
Do
exercises #3.29, 3.31, 3.32 on pp.114-115 of the K/S handout. |
|
|
Oct.
4 (M) |
Read
section 3.5 in K/S handout. Do exercise #3.37 on p.116 of the K/S handout. |
|
|
Oct.
6 (W) |
Read section
3.6 in K/S handout. Do exercise #3.38 on p.116 of the K/S handout. |
|
|
Oct.
8 (F) |
Read
section 3.7 in K/S handout. Do exercise #3.41 on pp. 117 of the K/S handout. |
|
|
Oct.
11 (M) |
Hand in completed exam on
context-free languages. |
|
|
Oct.
13 (W) |
Back to your text. Read
section 4.1 Do
exercises #4.1.1 on p.191 |
|
|
Oct.
15 (F) |
|
Fall
Break –no class today |
|
Oct.
18 (M) |
Do
exercises # 4.1.2,4.1.4, 4.1.7, 4.1.8, 4.1.10 on pp.191-194 |
|
|
Oct.
20 (W) |
Read
pp.194-197. Do exercises 4.2.1 and
4.2.2 on p.200. |
|
|
Oct.
22 (F) |
Read
pp.198-199. Do exercises #4.2.3 and 4.2.4 on p.200. |
|
|
Oct.
25 (M) |
No class today |
|
|
Oct.
27 (W) |
Read section 4.6. Do exercises # 4.6.1a and 4.6.2 on p.232 |
|
|
Oct.
29 (F) |
Read
sections #5.1-5.2. Do exercise #5.2.1
on p.250 |
|
|
Nov.
1 (M) |
Read section 5.3 |
|
|
Nov.
3 (W) |
Do exercise #5.3.3e on p.254 |
|
|
Nov.
5 (F) |
Read section 5.4. (especially the proof of Theorem 5.4.2) Do exercise #5.4.2a on p.257 |
|
|
Nov.
8 (M) |
Do exercise 5.4.2d on p.257 |
|
|
Nov.
10 (W) |
Read Theorems 5.5.1 & 5.5.2 |
|
|
Nov.
12 (F) |
Hand in your completed exam on Turing Machines |
|
|
Nov.
15 (M) |
All assignments from here refer to the Computational
Complexity handout Read section 6.1 |
|
|
Nov.
17 (W) |
Do exercise 6.2 on p.195 |
|
|
Nov.
19 (F) |
Read
section 6.2. Do exercises 6.4ab on p.195 |
|
|
Nov.
22-26 |
Thanksgiving
break- no classes this week |
|
|
Nov.
29 (M) |
Do exercises 6.4c & 6.5a on p.195 |
|
|
Dec.
1 (W) |
Do exercises
6.5bcd on p.196 |
|
|
Dec.
3 (F) |
Do
exercises 6.5e on p.196 |
|
|
Dec.
6 (M) |
Read
section 6.3. Do exercise 6.6 on p.196 |
|
|
Dec.
8 (W) |
Do
exercise 6.9 on pp.196-197. Pick
up the final exam. |
|
|
Dec.
10 (F) |
No
class today |
|
|
Dec.
16 (Th) |
Hand in your
completed final exam by noon today. |
Learning
Goals -
This course
addresses the following goals for applied mathematics majors.
Applied
Mathematics Goal 2:
The applied mathematics major will be able to express and interpret
mathematical relationships from numerical, graphical and symbolic points of
view.
Applied
Mathematics Goal 3: The applied mathematics major will be able to
read and construct mathematical proofs in analysis and algebra.
Academic
Honesty Policy
All students are expected to uphold professional
standards for academic honesty and integrity in their research, writing, and
related performances. Academic honesty is the standard we expect from all
students. Read the Student Handbook for further details about offenses
involving academic integrity at: http://www.millikin.edu/handbook/. Staley Library also
hosts a web site on Preventing Plagiarism, which includes the complete
university policy. It is located at: http://www.millikin.edu/staley/services/instruction/Pages/plagiarism-faculty.aspx.
Visit and carefully read the Preventing Plagiarism web site.
The Faculty has the
right and the responsibility to hold students to high ethical standards in
conduct and in works performed, as befits a scholar at the university. Faculty
members have the responsibility to investigate all suspected breaches of
academic integrity that arise in their courses. They will make the
determination as to whether the student violated the Academic Integrity Policy.
Should the faculty member determine that the violation was intentional and
egregious, he or she will decide the consequences, taking into account the
severity and circumstances surrounding the violation, and will inform the
student in writing, forwarding a copy of the letter to the Registrar and to the
Dean of Student Development.
This letter will be
destroyed when the student graduates from the University unless a second breach
of integrity occurs, or unless the first instance is of sufficient magnitude to
result in failure of the course, with an attendant XF grade recorded in the
transcript. If an XF is assigned for the course, the faculty letter of
explanation becomes a permanent part of the student’s record. If a second
violation occurs subsequent to the first breach of integrity, the Dean of
Student Development will begin disciplinary and judicial processes of the
University, as outlined in the Student Handbook.
If a student receives
an XF for a course due to academic dishonesty, this remains as a permanent
grade and cannot be removed from the transcript. However, students may repeat the
course for credit toward graduation. Some programs and majors have more
explicit ethical standards, which supersede this Policy, and violation of which
may result in dismissal from some programs or majors within the University. If
you have difficulty with any assignment in this course, please see me rather
than consider academic dishonesty.
Disability
Accommodation Policy
Please address any
special needs or special accommodations with me at the beginning of the
semester or as soon as you become aware of your needs. If you are seeking
classroom accommodations under the Americans with Disabilities Act, you should
submit your documentation to the Office of Student Success at Millikin
University, currently located in Staley Library 014.