**Instructor: **
Dr. Okie, 219 Davis Hall

**Phone:**
Office: 831-5992; Home: 951-7372
(Before 9:00 p.m., please)

**Email:**
nokie (Feel free to send email. I'll reply as quickly as possible.)

**Office Hours:**
MW: 10:00-10:55; TuTh: 11:00-11:55; F: 2:00-2:55
and by appointment.
You are welcome to come by at any time and if not busy I'd be glad to help you.
Except for classes and meetings, I'm usually in most of the day.
You may want to check my
complete schedule
to see when my meetings and classes are normally held.

**Prerequisite:** ITEC 122, Discrete Mathematics.

** Content: ** In this course we focus on
the **theory of computation** and, at the end, discuss the **theory of complexity**.
The theory of computation deals with the **theoretical limits**
of what can be computed and complexity theory deals with the **practical limits. **
The heart of the course is ** languages**, not natural languages (eg English),
but formal languages, which are defined to be sets of strings (This will be on the exam!).
We use a number of abstract tools for defining languages, including
**automata** (Latin for machines),
grammars, and regular expressions.
Each of these tools is an abstract model of computing.
We will also learn a hierarchy of languages and relate this hierarchy to a
hierarchy of tools!
The course involves little programming, but it does
cover how the theory applies to real world computing.
The material in this course can be challenging, but it is also
fascinating and stimulating, and I encourage you to give the
course your best.

**Topics:**

- Mathematics background (as needed during semester)
- Languages
- Finite automata and regular expressions
- Nondeterministic automata
- Regular and context free languages
- Context free grammars
- Pushdown automata
- Turing Machines
- Undecidability
- NP-Completeness

**
Course Outcomes:
**
Students who complete the course will be able to

- Demonstrate an ability to understand and apply mathematical concepts.
- Describe, analyze, and design language generators and recognizers including context free grammars and both deterministic and non-deterministic finite automata, pushdown automata, and Turing machines.
- Use a Pumping Lemma to prove that a language is not in a given class.
- Explain the Church-Turing Thesis and its significance.
- Describe example unsolvable problems and outline how a problem can be shown to be unsolvable.
- Define the classes P, NP, NP-Complete and explain their significance.

**Required Text:** *
Automata, Computability and Complexity: Theory and Applications*,
Elaine A. Rich,
Prentice Hall,
2007.
This is an outstanding text!
It covers the field broadly, and at the same it time gives very clear
descriptions of basic and advanced comcepts.
Make sure that you look at the
errata
for the book at the author's
book page
.

**
Semester Schedule:
**
We will cover most sections of chapters 1-21 and 27-30,
but skipping chapters 4, 7, 15, and 29,
and only briefly covering chapters 9 and 14.
Exams will be held around the time we finish chapters 10 and 16.

**
Communication:
**
I will post relevant course information on the course web page as well as
send announcements via email. It is your responsibility to
be aware of this information, as well as
all information presented in class, of course.

**Course web page:**
http://www.radford.edu/nokie/classes/420.
Currently this page shows topics and notes from earlier semesters,
when we used different text.
This semester we will primarily be using the excellent notes that
come with the text, but I will leave the old notes as additional
information.
I will update topics as the semester progresses.

** Evaluation: **
Course grades ("A" through "F", with pluses and minuses possible) will be based on your grades on
the following activities:

Per cent | Activity |

40 | Programs, Homework, and In-class Activities |

30 | Two in-class tests |

30 | Comprehensive final exam: 8:00 a.m. - 10:00 a.m., Wednesday, December 13, 2017 |

100 | Total |

** Homework problems: **
Every week or so you will have
a graded set of homework problems.
It is very important that you do
these assignments; figuring out the
answers to problems is the best way
to learn the material.
Also, the assignments are worth
40% of your grade.
If there are 10 assignments, then
each will be worth almost half of
a letter grade for the course!

Assignments will be graded on correctnesss and completeness, as well as neatness, clarity, and grammar. Unless otherwise specified, assignments will be due in class and on paper. Electronic submissions will not be accepted. Please use the course grades page to verify that I recorded your grades correctly, and keep all graded work until after you have received your course grade.

** Honor Code: **
This class will be conducted in strict observance of the Honor Code.
Please refer to your Student Handbook for details of expected behavior.

Of course, all work that you submit for grading must be your own, not somebody else's. You must not let anyone write your assignments for you and you must not use someone else's solutions as a basis for your own.

You may form a study group and work together on solving the
homework assignments. But each of you must *understand* for yourself how to
solve each problem, and you must *independently* write up your own solution,
in your own words, and submit it under your own name.

This means that you must not turn in work that is essentially identical with another person's.

Whenever possible you should show your work and explain your reasoning rather than simply giving a one-word answer to a question.

You should list the names of any students with whom you worked on an assignment, and you should also give a reference for any material that you find in a book or on the web.

Please be aware that if I suspect that you have violated the Honor Code, then I will not hesitate to file charges with the Dean of Students Office.

** Late policy: **
Unless otherwise specified, late
assignments will not be accepted.
You have two free late days that
can be redeemed on any assignment(s).

** Attendance: ** Attendance is not required;
however you will
find it much easier to learn the material and to make a good grade
if you come to
class. If you get behind in this course you are likely to find it
extremely difficult to catch up! Learning the concepts
takes time, and you must work on the course material regularly for it to
sink in. You will not be allowed to make up
any in-class activities that
you miss.
Good attendance and class participation can be to your benefit if you have
a borderline final grade!

** Exams: **
In exceptional circumstances I may
give permission to miss an exam
if you contact me in advance.
In such cases the weight of your
final will be increased. Otherwise
a missed exam will
be worth 0 points.

** Academic Accommodations: **
If you are seeking academic accommodations at RU under the ADA,
you must register with the
DRO.
To receive academic accommodations for this class,
submit your documentation to the DRO in Tyler Hall (lower level,
Suites 54-69), 540-831-6525 (fax), or
dro@radford.edu, and then set up an interview with the
DRO to discuss accommodations.
After you have been notified via email that your
accommodation package is ready,
you must pick it up and then meet with me to discuss it.
For more information and documentation guidelines, visit
www.radford.edu/dro
or call 540-831-6350.

** Distractions: **
Laptops are not to be used during class unless I give you permission or
tell you to use them.
Electronic devices are distracting to you and to others.
Research shows that multitasking limits concentration and reduces learning.
Experience shows that distraction from a laptop lowers a
student's course grade by a full letter grade.
Food is also distractiong - please do no bring it to class!

Dr. Okie's Home Page