Foundations of Computation

Fall 2017

TR 11:40am to 12:55pm, 300 Main Street, B201.

Stephen A. Fenner

Telephone: 803-777-2596 (only if I'm there; email is preferred)

Email: I use gmail (gmail.com) and my user name is fenner.sa

Web: http://www.cse.sc.edu/~fenner

Office: Storey Center, 550 Assembly St., Room 2249; also via email

Office Hours: MW 2:00pm - 4:00pm or by appointment

Name: Daniel Padé

Office: Storey Center, 550 Assembly St., Room 1205

Phone: 901-300-6878

E-mail: pade AT email DOT sc DOT edu

Office hours: MTW 11:00 - 12:00 or by appointment

CSCE 211, 212, 350. MATH 374 is highly recommended.

**Required:**
J. E. Hopcroft, R. Motwani, J. D. Ullman, *Automata Theory, Languages,
and Computation (3rd Edition)*. Addison-Wesley-Pearson 2007.

The (somewhat outdated) official departmental syllabus for this course can be found HERE.

This course is a mathematical introduction to the basic concepts underlying all computation. The goal is to discover the fundamental abilities and limitations of computers and to use mathematical rigor to prove facts about computation. We will study abstract models of computation, such as finite automata, grammars, and Turing machines. We will also set up a formal framework for defining computational problems as formal languages with the goal of studying the ultimate limits of computation. The core topics learned in this course pop up repeatedly in many areas of computer science and have close connections with logic and the foundations of mathematics.

There will be three midterm exams, each worth 15% of your grade. Another 15% of your grade will consist of a programming assignment. The remaining 40% of your grade is a final exam.

Each midterm exam will start at the beginning of class and last approximately 40
minutes, followed by a discussion of the answers. All midterm exams
are **closed book, closed notes, and no electronic devices allowed**,
except for legitimate use by students with documented special needs.
Each midterm will be number of questions or problems sampled from
the preceding homework assignments, possibly modified somewhat.

Here is the schedule of exams.

Exam |
Date |

1st midterm | Thursday 9/14 |

2nd midterm | Tuesday 10/10 |

3rd midterm | Tuesday 11/7 |

final | Thursday 12/14 (12:30 - 3:00) |

The final exam is 2.5 hours on Thursday December 14, from 12:30pm to
3:00pm. It is **open book, open notes, but no electronic devices of
any kind except for legitimate use by students with documented
special needs.** Final exam questions will also be derived from the
homework exercises, but more loosely.

**PLEASE NOTE:**

- This course will go by quickly. The subject matter is cummulative and requires time and effort to digest, and so it is vital that you keep up with the homework and reading.
- The course is mathematical in nature. The third most important indicator of success in this course (second to hard work and internal motivation) is a certain level of "mathematical maturity," that is, being able to: (a) understand mathematical definitions and theorems, (b) verify proofs, (c) solve mathematical problems, and (d) in simple cases, generate one's own definitions, theorems, and proofs.

The homework problems are intended as a pool for exam questions and as timely feedback for you. They will not be graded.

Letter grades correspond to score percentages as follows:

A | 90 or above |

B+ | at least 86 and less than 90 |

B | at least 80 and less than 86 |

C+ | at least 76 and less than 80 |

C | at least 70 and less than 76 |

D+ | at least 66 and less than 70 |

D | at least 60 and less than 66 |

F | less than 60 |

You (the student) are expected to read all assigned material before the lecture begins. If for some reason you cannot attend class, you are responsible for any material covered during your absence.

The textbook coordinates with a set of on-line resources (Gradiance). I will neither require nor assume you to have access to these resources. I encourage it if you'd like some extra insight, but it's purely optional. (My rationale for not requiring it is this: it appears that to access Gradiance you need to purchase a new, unused copy of the text.)

**No make-up exams will be given except under extreme
circumstances with a valid excuse, in which case you must give me
notice well before the exam if at all possible.** Valid excuses include
grave illness or death in the immediate family, or other similarly
dire emergency. They do not include car problems or non-emergency
events (weddings, trips, sports meets, etc.). **Before proceeding with
the course make sure that you can attend all the exams.**

You are expected to know the Academic Code of Responsibility as it
appears in the *Carolina Community: Student Policy Manual*.

You may not represent other people's work as your own. More specifically,
you cannot submit specific
answers from other sources without proper attribution. If you copy or
otherwise derive materials/answers from other people, books, the web,
etc., you must cite your source(s) in a way that adheres to the usual
standards for an academic paper. Deriving or copying without proper
attribution is plagiarism, which I regard as a serious offense.
(**Exceptions:** You do not need to explicitly cite any material you
lift from the course's textbook or from my own lectures or lecture
notes. You are also not required to explicitly cite any general
background material you use for an answer but which does not
specifically relate to the actual question being answered.)

Obtaining answers during an exam other than by the approved means (your own printed material, knowledge, and cleverness) is forbidden. Passing along questions or answers to an exam to anyone else before the exam is given is also forbidden.

Any violation of the rules above constitutes cheating, for which there is no excuse.

**THE USUAL PENALTY FOR CHEATING IS FAILURE OF THE COURSE.** The offense
will also be reported to the USC OFfice of Academic Integrity. The
bare minimum penalty you may receive for an instance of cheating is
double the points of the assignment off. That means that if an
assignment/test is worth 10 points, your ultimate grade would be -20
for the assignment/test. Finally, as noted in the *Student Policy
Manual*, the maximum penalty for cheating on an assignment is
expulsion from the University. These penalties apply both to copier
and copiee.

Go HERE for more information about the Honor Code and class policies.

Course topics by chapter are given below. Any topics in brackets "[ ]" do not correspond to current sections in the book. This schedule is flexible and is subject to some revision as the class proceeds. There may not be time to cover all the topics listed. You will be tested only on those topics that could be covered in class, which means that the content of the exams may be adjusted.

Topic(s) |
Chapter |
Week(s) |

Introduction: mathematical preliminaries, definitions, theorems, proofs, automata concepts: alphabets, strings, and languages | 1 | 1 - 2 |

Deterministic finite automata | 2.1 - 2.2 | 3 |

Nondeterministic finite automata, regular expressions | 2.3, 2.5 | 4 |

Regular expressions (cont.), regular languages, equivalence to automata | 3.1 - 3.3 | 5 |

Proving languages nonregular: pumping lemma | 4.1 - 4.2 | 6 |

Minimization of automata | 4.4 | 7 |

Context-free grammars and languages, parse trees | 5.1 - 5.4 | 8 - 9 |

Pushdown automata, equivalence to grammars | 6.1 - 6.3 | 10 |

Normal forms of CFGs, pumping lemma for CFLs | 7.1 - 7.2 | 11 |

Turing machines, notion of "algorithm" | 8 | 12 - 13 |

Undecidability and intractability | 9 - 10 | 14 |

Final Exam (cummulative, but emphasizing material not tested on the midterms) | all | 12:30pm on 12/14 |

This page last updated Friday October 27, 2017 at 14:41:33 EDT.