Instructor info
Instructor |
Claude Anderson |
Office Phone |
812-877-8331 |
Office Hours |
My schedule will vary from week to week. Most days
I will have two or three hours of specifically
scheduled office hours in the early afternoon, plus some occasional hours when I am likely
to be there.
I try hard to keep my calendar up-to-date.
My calendar is also linked from the top of the schedule page.
Whenever I am in my office and not helping another student, I am usually
available to talk with you. Exception:
Even if I am in my office, I will not be available 8:00-9:00 AM
MTRF; I will be doing last minute preparation for that day's class
meeting. |
E-mail |
anderson@rose-hulman.edu
or
csse474staff@rose-hulman.edu (the latter goes to me and the eight
graders) |
Schedule
page
|
http://www.rose-hulman.edu/class/csse/csse474/201830/Schedule/Schedule.htm
This is where I will post readings, assignments, resources, exam dates,
etc.
(you should bookmark it in your browser) |
Moodle pages |
Some things
that are interactive or that I do not want to post publicly (such as
solutions to HW or quizzes) will be posted on the Moodle course page.
|
Piazza page |
https://piazza.com/rose-hulman/spring2020/macsse474/ Discussion
forums and course announcements. A great place to ask/answer questions about lectures, readings, homework, etc. |
Required Text
Automata, Computability, and Complexity: Theory and Applications
by Elaine Rich (Prentice Hall, 2008)
It is available online (and free) here, by permission of the author..
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 several entire chapters in this 10-week course.
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 (Cengage.com,
2012)
Overview of course topics
I may adjust the timing 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
|
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 this course already comfortable with about 75% of that appendix, you should be fine.
If not, you have some extra work to do.
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 happens to be the area of application.
We will focus much more on the theory than on the applications.
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 Functions of a Real Variable course from
the math department, and some results from this course are
even less intuitive than that course.
You will have to internalize and embrace many mathematical notations,
abstractions, and formalisms 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
and be alert in the morning.
I will have a sign-in sheet each day. If you miss three class meetings without
notifying me in advance, I will begin to question your commitment to the course.
If you miss five classes with no advance notification, I will ask you to drop the course or receive an F
grade .
Two things that I frown on:
- Oversleeping your section's meeting time and asking if it is okay
to come to a later section. As of March 3, 2020, there are no extra seats in the later sections.
- Missing class, then coming to my office
and asking me to summarize what you missed.
You first should look over the slides and notes
pages from that day, 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.
But 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;
you will be asked to write up and turn in about 60% of those problems. These will
typically be short
thought problems, mathematical analyses, formal proofs, algorithm or machine
constructions. I expect you to think through them carefully and write your answers
legibly and clearly (if you prefer, type 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 the difficult problems 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
them
later.
Technology, presenting your solutions, composition, and submission:
Computer-created or hand-written? Your solutions will need
to include many mathematical symbols, especially logical
symbols such as ∄, ¬, ∧, ∈, ∩, ⊆, and →. You can do this in
either of two ways (more details under How to Submit, below):
-
Learn how
to produce such symbols in software such as
Microsoft Word, Maple, or LaTeX
-
Legibly write your solutions by hand and,
and scan or photograph them, collecting them into a Word PDF document that you
will submit. /li>
When will Homework assignments be due? Most weeks two assignments will be due, nbsp;
Mondays and Thursdays at 11:55 PM. There
may be some exceptions due to exams, the break in the middle
of the term, 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, please submit a
single file.
Acceptable file formats are MSWord, Maple, PDF (not JPEG ,GIF, PNG). If
you take pictures with your phone, I want you to edit them to make sure they are
readable, and collect them (in correct order) 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. Do not write on both
sides of a page that you intend to scan or photograph. Material from
the other side tends to "bleed through."
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 an Early Day if you submit an assignment 24 hours early and earn at least 75%
of the credit for it. Each Early Day will be worth 5 extra-credit homework points at the end of the term.
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 we will grade that submission, even if you resubmit before the deadline.
Policy on Late Assignments:
In general, only on-time submissions will be accepted for credit. With so many students in the class,
accepting late assignmets will make it difficult or impossible for us to get assignments graded in time for our feedback to help students with subsequent assignments.
Leave yourself enough time to scan or photograph your work and submit it before the 11:55 deadline.
I will consider, on an individual basis, requests for a one-day extension due to emergency or unforeseen circumstances.
You should ask at least 10 hours before the assignment's due time.
If possible, you should ask me in person so I can ask questions about the circumstance.
If the nature of your emergency prevents a face-to-face conversation, an email request may be acceptable.
In general, "I started the assignment too late" or "I have three assignments due today" will not be considered unforeseen circumstances.
Notification of an earned early day: You
do not have to do anything. I will keep
track of Early 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 Early Day program because
you do not want your balance to be made public, let me know. But
then you will not be able to earn extra-credit points for early submissions.
Grade Components
|
25% |
Assignments (including written homework,
quizzes, and any special assignments) |
75% |
Examinations (two in-class exams, 20%,
25%, and one evening exam, 30%)
Exams will be closed book and notes. You
can bring yourself and a writing implement.
I will provide a sheet that has some definitions and notations,
and you will know the contents of that sheet in advance. |
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?
(taken from https://www.rose-hulman.edu/campus-life/student-services/registrar/rules-and-procedures/grades.html)
- "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.
For example, if a problem is worth 12 points, the possible scores are 0, 4, 8, and 12.
Bounty for discovering new errors in the textbook and
course materials.
If you are the first to find and report 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.
In your email subject line, please include 474 and bug
report
Email, Piazza, Classmates
I will communicate many announcements and assignment
clarifications using the class Announcements Page and
(between class meetings) 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, 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 your question or comment is not personal and does not contain homework "spoilers"
please post it 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, so
asking them questions will help them. I suggest that you find one or two other students and meet regularly with them to discuss this coure.
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, you may miss the
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 contains 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 (see page 14 of this student handbook)):
“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 CSSE Department 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 reading the 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)
that is equal in magnitude to the positive maximum score for the entire assignment or exam. Egregious or repeated cases will result in a grade of “F” for the course.
Rose-Hulman rules require me to report cases of academic misconduct to the Dean of Students.
More important, such dishonesty steals your own self-esteem. So don’t cheat.
| |