MA/CSSE 474 Theory of Computation - Winter 2015-16 (201620)
Syllabus and Policies

• 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:

1. Demonstrate the ability to construct proofs using various techniques such as induction, contradiction, contrapositive.
2. Explain the concepts of finite automata and regular languages.
3. Design deterministic and nondeterministic automata to recognize specified regular languages.
4. Design regular expressions to generate specified regular languages.
5. Explain the concepts of context-free and context-sensitive grammars.
6. Design context-free grammars to generate specified context-free languages.
7. Design push-down automata to recognize specified context-free languages.
8. Design Turing Machines to recognize languages and compute functions.
9. Explain the Church-Turing thesis and its significance.
10. Determine a language's location in the Chomsky hierarchy (regular sets, context-free, context-sensitive, recursively enumerable languages).
11. Prove that a language is in a specified class and that it is not in the next lower class.
12. Convert among equivalently powerful notations for a language, including among DFAs, NFAs, and regular expressions, and between PDAs and CFGs.
13. Explain why some problems have no algorithmic solution.
14. Provide examples that illustrate the concept of undecidability.
15. Prove that a problem is undecidable by reducing a classic known undecidable problem to it.
16. 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:

1. 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. 
2. 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.

1. 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.
2. 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 ...
3. 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.
4. 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.
5. Unused late days are not redeemable at the end of the term.
6. 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.