Instructor info
Required Text
Automata, Computability, and Complexity: Theory and Applications
by Elaine Rich (Prentice Hall, 2008)
The author has a companion web site:
http://theoryandapplications.org/
Erata page: http://www.cs.utexas.edu/~ear/cs341/automatabook/errata.html
Yes, this is a big book! It has very detailed definitions,
explanations, proofs, and lots of examples and exercises. Also many applications of Theory of Computation to other areas.
We will skip some sections and even some chapters in this 10-week course.
Approximate schedule of readings and course topics (I may adjust this as we go along)
Week 1
|
Background, overview,
languages and the types of
Machines that recognize them
|
Week 2
|
Finite State
machines-
Deterministic
and
non-deterministic |
Week 3
|
Minimal
DFSMs,
Regular
expressions,
Kleene's
theorem |
Week 4
|
Regular Languages,
membership, closure,
decision problems |
Week 5
|
Context-free Grammars |
Week 6
|
Ambiguity, normal forms,
PDAs (deterministic and
non-deterministic) |
Week 7
|
Parsing, CFL membership,
decisions, closure
|
Week 8
|
Turing machines,
undecidability of the
Halting Problem |
Week 9
|
Enumerability; decidable,
semidecidable, and
non-semidecidable languages;
reduction |
Week 10
|
More complicated reductions;
computational complexity, P
and NP
|
Other Books
- A book that I recommend for every Computer Scientist's library:
Grimaldi, Ralph P. Discrete and Combinatorial Mathematics
(Addison-Wesley, 2003)
- Other good books on Automata and Computation:
- Introduction to Automata Theory, Languages, and Computation by Hopcroft, Motwani, and Ullman (Addison-Wesley, 2001)
- Introduction to the Theory of Computation by Michael Sipser (Thomson
Course Technology-Hill,
2006)
Course Description
RHIT Catalog Description
Students study
mathematical models by which to answer three questions: What
is a computer? What limits exist on what problems computers
can solve? What does it mean for a problem to be hard?
Topics include models of computation (including Turing
machines), undecidability (including the Halting Problem)
and computational complexity (including NP-completeness).
Course Learning Outcomes (adopted by CSSE department,
November 11, 2015)
Students who successfully complete this course should be
able to:
- Demonstrate the ability to construct proofs using various techniques such as induction, contradiction, contrapositive.
- Explain the concepts of finite automata and regular languages.
- Design deterministic and nondeterministic automata to recognize specified regular languages.
- Design regular expressions to generate specified regular languages.
- Explain the concepts of context-free and context-sensitive grammars.
- Design context-free grammars to generate specified context-free languages.
- Design push-down automata to recognize specified context-free languages.
- Design Turing Machines to recognize languages and compute functions.
- Explain the Church-Turing thesis and its significance.
- Determine a language's location in the Chomsky hierarchy (regular sets, context-free, context-sensitive, recursively enumerable languages).
- Prove that a language is in a specified class and that it is not in the next lower class.
- Convert among equivalently powerful notations for a language, including among DFAs, NFAs, and regular expressions, and between PDAs and CFGs.
- Explain why some problems have no algorithmic solution.
- Provide examples that illustrate the concept of undecidability.
- Prove that a problem is undecidable by reducing a classic known undecidable problem to it.
- Define the classes P and NP.
Prerequisites
CSSE 230 Data Structures and Algorithms MA 375 Discrete and Combinatorial Algebra II
| Note: The course
actually depends much more on MA
275 than on CSSE 230 or MA 375. If you are very
comfortable with the contents of chapters 2-7 of Grimaldi's book,
and if mathematical induction is "second nature" to you, you should
be fine. If not, you may have to work extra-hard in this
course for the first few weeks. The MA 375 exposure to
finite state machines will also be helpful, but we will take a
slightly different approach
in this course.
Students who are strong in the prerequisite mathematical background
(especially proofs) and who are willing to work hard usually do very well in this course.
Students who earned less than a B in MA 275 or 375 tend to have to work extraordinarily hard for the first few weeks of
this course, in order to make up for lost time. Students who
have this deficit who do not face it realistically at the
beginning of MA/CSSE 474 frequently end up dropping the course. Don't be that student!
I am available to help you with prerequisite material as well as the new 474 material.
But you need to make the time to do what it takes to catch up. |
Appendix A of the Rich textbook contains a review of most of the material you
need to know from those courses, some of it (for
example, first-order logic) in slightly more depth than in Ralph
Grimaldi's DISCO book.
The main things that you should bring into this course
- enthusiasm, curiosity, perseverance, and a "can do" attitude, especially
concerning proofs and mathematical terminology (if you don't pay attention to
terminology, you're dead in this course!)
- willingness to work cooperatively with other students in the classroom to enhance the learning environment for everyone
- determination to consistently devote enough time to the course
- commitment to read the textbook and get all you can from it, so that more
class time can be spent on problem solving
- commitment to avoid getting behind, and to ask questions when you don't understand something
- a reasonable comfort level with elementary discrete mathematics (especially
proofs). Appendix A of the Rich book is a good benchmark. If you
came to the course already comfortable with about 70% of that appendix, you should be fine.
What will the course be like?
It's a math course: This course is cross-listed in the Mathematics and CSSE
departments. I think it is best described as an "applied
theoretical math course." It has the look and feel of a
theoretical math course. Much of your time will be spent learning very
precise mathematical definitions, understanding and writing
proofs, and coming up with counter-examples. Computer
science is the area of application. In terms of the need
for mathematical detail, for understanding complex notation,
and for proving some things that are counter-intuitive, I
would compare this course to the Real Variables course in
the math department.
It will take a lot of time: If you are
well-prepared coming into the course (a solid B or better in
each of MA 275, MA 375, and CSSE 230), I estimate that you
will spend 2-3 hours per week reading the textbook, 4 hours
in class, and 6-8 hours working
on the homework problems. Yes, this is a lot of time,
but I think this is what will be necessary for the average
student if you are to fulfill the learning objectives of
this course. If you are weak in the prerequisite course
material, you might expect to spend an additional 1-5 hours
per week for the first half of the term. If you are
successful in catching up, you should not need to spend that
extra time in the second half of this course.
Its intellectual level is very high: I'd
say that it is on par with the Real Variables course form
the math department, and some parts are less intuitive.
You will have to absorb and embrace mathematical notation,
abstraction, and formalism if you are to do well here.
Attendance policy
I believe that attendance in this class is important, and that you should get to bed in time to make it to class.
On the other hand, this is a 400-level course. You are adults and experienced students.
You should know the value of coming to class without me forcing you to do it. So I won't.
However, I will have a sign-in sheet each day. If you are not doing well in the course,
I will look to see if you are missing class a lot. If so,
I will strongly suggest that you don't continue to miss class.
Two things that I frown on:
- Oversleeping your section's meeting time and asking if it is okay
to come to a later section. This is all right once or
twice during the term, but do not make a habit of it.
- Missing class, then coming to my office
and asking me to summarize what you missed.
You should look over the slides and notes
pages, read the textbook, talk to fellow
students about what you missed, and then
come to me with questions on specific things
that you still don't understand.
Assignments
Most days there will be in-class note
sheets,
similar to in-class quizzes in other CSSE courses.
You will usually not be required to
turn these in. When I give a reading assignment,
I seriously expect you to read it.
In-class discussions will assume that you have done the reading
and understood the "easy stuff" before class. Occasionally there may be
a
reading quiz based on the
definitions and simple concepts from a reading assignment.
You may of course ask about any details that you do
not understand. When there is a reading quiz, you must submit a
hard copy at the beginning of class. You can print it and write
on it, or complete it electronically and then print it.
I will assign many (on the order of 200) written problems, most of them from the textbook. These will
typically be short
thought problems, mathematical analyses, formal proofs, algorithm or machine
constructions, or machine-design
exercises. I expect you to think through them carefully and write your answers
legibly and clearly (if you prefer, type them and print them). On some problems,
your score will be determined
not only by the correctness but also the quality of your solution. Some of the problems will be straightforward practice with concepts
from the course; others will require creative solutions. Don't put them off
until the last minute! Get them into your mind soon after they are assigned, so
you have an opportunity to take a break (perhaps to ask questions) and come back to
the difficult problems
later.
When will Homework assignments be due? Most weeks, two assignments will be due.
Mondays and Thursdays at 11:55 PM. There
may be some exceptions due to exams, break, or problems that
are difficult enough to require more time.
How to submit? You will submit your homework solutions to
designated Moodle drop boxes. You can either compose your
solutions on
your computer or write them by hand and scan them to produce electronic copies. There are scanners in
F-217 and in the Logan Library. For each assignment, submit a
single file (can be a ZIP file); must be less than 10 MB; aim for 2 MB or less.
Acceptable file formats are MSWord, Maple, PDF (not JPEG ,GIF, PNG). If
you take pictures with your phone, I want you to edit to make sure they are
readable, and collect them into a Word or PDF document. If the graders and
I cannot read your scanned or photographed submissions, you will not get credit.
If you use pencil, choose a dark pencil. Things written on white paper
tend to scan better than engineering paper.
There are no traditional programming problems.
This is essentially an abstract mathematics course whose
area of application is computer science. The
"programs" you will write will be descriptions of finite
state machines, pushdown automata, and Turing machines to
accomplish certain tasks, as well as algorithms that
transform one abstract model to another.
Non-turnin assigned problems: Due to limited time (yours and mine), I will only
require you to formally write up a subset
of the assigned problems. You should make sure you
understand all of them. But sometimes the time required to
write them clearly is greater than the time required to
understand/solve them, so I will not ask you to submit all
of them. My assistants and I will do our best to grade
all required problems, but occasionally we may have to grade
a proper subset of them.
Additional practice problems: The textbook has many exercises at the ends of each chapter; Almost all
are likely to be helpful; obviously I cannot assign all of them. For many of those
problems, reading and thinking about them will be instructive, even if you
don't have time to fully solve them. In each chapter that we cover, I recommend that you read them all,
regardless of whether they are assigned.
Varying problem difficulty levels: Most assigned problems will
be routine, and I will expect that everyone should be able to get them.
Some of the problems will be more challenging; my expectation is that A and/or B
students will get them, but everyone will benefit from trying them.
Get started early on all assignments! Sometimes you
will need some "incubation time" before the problem is due. You can
earn a Late Day if you submit an assignment 24 hours early and earn at least 75%
of the credit for it.
You should only submit early if you mean it!
I will encourage my graders to begin grading
assignments as they come in. Once you submit an
assignment, it is possible that that is the submission that
will be graded, even if you resubmit before the deadline.
Policy on Late Assignments:
We all have occasional days when we are extra busy, or
times when a homework assignment takes longer to understand
and complete
than we expect it will. To allow for this, I give each
student a “late day bank account” that
starts with
three late days.
- Using (withdrawing) a late day allows
you to turn in a homework assignment
up to 24 hours after the time it is due. You
may not use late days for reading quizzes.
- You will earn (deposit) an additional
late day if your last submission for an
assignment is at least 24 hours before it is
due, provided that you earn at least 75% of
the possible points for that assignment.
There is no limit to the number of late days
you can save up. But ...
-
Only one late day may be used or
earned on any one assignment.
After that one late day has expired, you may
not submit that assignment for credit.
- Overdrafts are not allowed. If your late
day account is empty, you should take it as
a sign that you need to change your approach
to the course. If your account is empty and
you submit an assignment late, you will
receive no credit.
- Unused late days are not redeemable at
the end of the term.
- A few particular assignments may be
designated as ”no late days“ assignments.
This might happen because:
- there is an exam the
next day or the day after,
or
- what we will do in the
next class depends heavily
on this assignment, or
- some other reason that I
will explain at the time.
Notification of a late day deposit or withdrawal: You
do not have to do anything. I will keep
track of late days and post everyone's balance on the web.
The link is near the top left of the schedule page, just
above the actual schedule. I
cannot think of a better way to notify everyone that is
also simple for me to maintain. If
you do not want to participate in the late day bank because
you do not want your balance to be made public, let me know. But
then you will not be able to turn in any late assignments for
credit.
Grade Components
|
20% |
Assignments (including written homework,
quizzes, and any special assignments) |
80% |
Examinations (three in-class exams, 15%,
20%, 20%), and final exam, 25%
Exams will be closed book and notes. You
can bring yourself and a writing implement. |
The grading scale is a bit lower than in
other courses, to reflect the difficulty of some of the problems. If I
perceive that exams have been especially difficult, it
is even possible that these numbers will be lowered a little bit, but you should not
count on it.
What do A and B grades mean at Rose-Hulman?
(http://www.rose-hulman.edu/offices-and-services/registrar/rules-procedures/grades.aspx)
- "A" is an honor grade. It is awarded as a
mark of outstanding performance and for
achievement clearly of a higher order than
average. It indicates that the student has
demonstrated not only the ability to work
successfully, but also the ability to do some
creative thinking or problem solving in the
field. It will not be given for routine
performance of the assigned work in the course.
- "B" and "B+" indicate very good performance,
definitely above a satisfactory level, but not
as good in analytical thinking and originality
as that required for the grade of "A." Thorough
competence to do excellent work in the field is
required for the grades of "B" and "B+" which
will not be given for mere compliance with the
minimum essential standards of the course.
Grading scale for quizzes and homework problems. To
simplify the scoring process and let us focus on providing helpful feedback
instead of score nuances, the
possible point value for each quiz and each homework problem will be a multiple of 3, and will be
scored as that multiple times the following scale:|
3 Correct or a very minor error
2 Mostly correct
1 Some progress toward a solution
0 Nothing submitted, or nothing that demonstrates any understanding of the
problem.
Bounty for discovering new errors in the textbook and
course materials.
If you are the first to find and report (in the bug_reports folder on
Piazza) an error in the textbook or in any document that I produce for the
course (including this syllabus), I will give you some bonus Assignments points.
The number of points is proportional to the importance and subtlety of the
error. Even spelling, punctuation, or grammar errors will count for something!
Also broken or misdirected links.
Some already-known errors in the textbook:
http://www.cs.utexas.edu/~ear/cs341/automatabook/errata.html
Email, Discussion Forums, Classmates
I will communicate most announcements and assignment
clarifications using Piazza. For messages
directly to individuals and for urgent announcements, I will use
Rose-Hulman email. You should check your email and
Piazza every day or two, and make
sure that your mailbox does not fill up so you cannot
receive new messages.
Sign up for the Piazza course (see link near the beginning
of this syllabus). I suggest that you also set all
notifications to "real time".
When you send me course-related email, please
-
include 474 somewhere in
your subject line, and also
-
take a minute to think about
a reasonable subject line.
-
For example,
474: Question
about Exercise 2.1(b)
is reasonable;
474
by itself is not.
If you think that your question or comment
might be of general interest to people in
the class, please post it on one of the
course discussion forums on Piazza. First of
all, you may get an answer more quickly than
if you only send mail to me. Second, you may
get multiple people's perspectives. Third,
you will contribute to an active learning
community.
If you have a question that requires you to
reveal a possible homework problem solution before the
assignment is due, please send email to
csse474-staff@rose-hulman.edu instead of
posting on Piazza.
Other students in the course can often be
your best source of help. And they will also
learn more if they explain things to you.
Don't try to be the Lone Ranger in this
course, especially if you do not find the
course easy. If you have worked on
a problem for 30 minutes without making any
progress, it's probably time to seek help.
If you wait until the due date to start
working on a problem, there may not be an
opportunity for you to get such help.
Anonymous Suggestion Box
I want your feedback on how the course is going and how it could be improved. While "nonymous" suggestions are even more useful than anonymous ones,
I'd like to know what you are thinking, even if you do not feel comfortable with letting me know who made the suggestion.
Thus the 474 Moodle site will contain an anonymous suggestion box. I will get your comments, but I
cannot find out who sends them.
All I ask is that you only use this only for serious suggestions, not to
simply vent when you are momentarily frustrated.
You can also use this survey to tell me about things you like in the course and don't want to change. :) If you ask a question in your anonymous message, the only reasonable way I can
reply is with a post to Piazza. I will do
that if I think my response is likely to be relevant to several students in the class.
Academic Integrity
Recall the Institute policy on academic misconduct:
“Rose-Hulman expects its students to be responsible adults and to behave at all times with honor and integrity.”
Exams and homework will be done on an individual basis except when explicitly noted
for specific assignments. The simple rule of thumb for assignments that are
supposed to be individual work is:
Never use someone else’s code or written answers
(including answers that have been posted on the internet or answers written
by students from previous terms), or provide your answers to another
student.
Such exchanges are definitely cheating and not cooperation. The departmental statement on academic honesty has more detailed advice.
Unless I specify otherwise for some assignment or
problem, you may communicate with other students about the problems, and work out solutions together.
But when you write it up to turn it in, you must do it on your own without reference to things that you wrote together,
to make sure that you have internalized it.
You should also acknowledge the collaboration in writing on your submission.
If you are ever in doubt about whether some specific situation violates this policy, the best approach is to discuss it with your instructor beforehand. This is a very serious matter that we do not take lightly. Nor should you.
You should never simply look at another student’s solution to get ideas of how to write your own. Beginning the process of producing your own solution with a copy of work done by other students
or that you found on the internet or in some fraternity file, etc., is never appropriate.
Plagiarism or cheating will, as a minimum penalty, result in a negative score (i.e., less than zero) for the assignment or exam. Egregious cases will result in a grade of “F” for the course. More importantly, such dishonesty steals your own self-esteem. So don’t cheat.
| |