Download as pdf, TeX

1 Instructor

2 Overview

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.

2.1 Prerequisites

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

2.2 Text(s)

• J.E. Hopcroft, R. Motwani, J.D. Ullman. Automata Theory, Languages, and Computation. Addison-Wesley-Pearson 2007.

3 Coursework and Grading

There will be weekly quizzes (11 in all), which will comprise 50% of your grade. Your lowest quiz grade will be dropped, and so each quiz is worth 5% of your grade. 16% of your grade will consist of a programming assignment. The remaining 34% of the grade is split equally between the midterm and final exam.

Each quiz will be given at the start of class and last approximately 10 minutes. All quizzes are closed book, closed notes, and no electronic devices allowed, except for legitimate use by students with documented special needs. Each quiz will be a question or problem sampled from that week’s homework assignment, possibly modified somewhat.

The final exam is 2.5 hours on Wednesday, Apr 26, from 4:00pm to 6:30pm. It is open book, open notes. Electronic devices may be used, but only as timepieces and for passive viewing of locally stored content. Absolutely no electronic communication or computation is permitted. Exam questions will also be derived from the homework exercises, but more loosely.

PLEASE NOTE:

• This course will go by quickly. The subject matter 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 is intended as a pool for quiz and exam questions and as timely feedback for you.

4 Course Policies

4.1 Reading and Lectures

• 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 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.)

4.2 Quizzes and Exams

• Exams are open book, open notes.
• Quizzes are closed note
• No make-up quizzes or exams will be given except under extreme circumstances with a valid excuse, in which case you must give me notice well before the exam or quiz if at all possible. Valid excuses include grave illness or death in the immediate family, or other dire emergency. They do not include car problems or non-emergency events (weddings, trips, sports meets, etc.).

4.3 Grades

• Grades in the C range represent performance that meets expectations; Grades in the B range represent performance that is substantially better than the expectations; Grades in the A range represent work that is excellent.

Letter grades correspond to score percentages as follows:

Grade	Range
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

4.4 Attendance

From the attendance policy:

• Students are obligated to complete all assigned work promptly, to attend class regularly, and to participate in whatever class discussion may occur.
• Absence from more than 10 percent of the scheduled class sessions, whether excused or unexcused, is excessive and I may choose to exact a grade penalty for such absences.
• It must be emphasized that the “10 percent rule” stated above applies to both excused and unexcused absences.

5 Code of Student Academic Responsibility

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/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 text or from my own lectures. 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 appropriate University entities. 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.

6 Tentative Course Outline

Course topics by chapter and the final exam date are given below. 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 quizzes and exam may be adjusted.

Topic(s)	Chapter (ALC)	Chapter (ITC)	Week(s)
Introduction: mathematical preliminaries, definitions, theorems, proofs, automata concepts: alphabets, strings, and languages	1	0	1–2 Jan. 16 — no class Jan. 17 — W drop day
Deterministic finite automata	2.1–2.2	1.1	3
Nondeterministic finite automata, regular expressions	2.3, 2.5	1.2-1.3	4
Regular expressions (cont.), regular languages, equivalence to automata	3.1–3.3	1.3	5
Proving languages nonregular: pumping lemma	4.1–4.2	1.4	6
MIDTERM EXAM	1–4	0-1	Wed. Feb 22
Minimization of automata	4.4	Prob 7.42	8 Mar 2. — WF drop day
Spring Break — Mar. 5–12
Context-free grammars and languages, parse trees	5.1–5.4	2.1	9–10
Pushdown automata, equivalence to grammars	6.1–6.3	2.2	11
Normal forms of CFGs, pumping lemma for CFLs	7.1–7.2	2.3	12
Turing machines, notion of “algorithm”	8	3.1, 3.3	13
Undecidability and intractability	9–10	4.1-4.2	14
FINAL EXAM (cumulative)	all	all	Apr. 26, 4:00pm

7 Quiz Schedule

Number	Date
Quiz 1	Wed 01/25
Quiz 2	Wed 02/01
Quiz 3	Wed 02/08
Quiz 4	Wed 02/15
Quiz 5	Wed 03/01
Quiz 6	Wed 03/15
Quiz 7	Wed 03/22
Quiz 8	Wed 03/29
Quiz 9	Wed 04/05
Quiz 10	Wed 04/12
Quiz 11	Wed 04/19

8 Data for Research Disclosure

Any and all results of in-class and out-of-class assignments and examinations are data sources for research and may be used in published research. All such use will always be anonymous.