MA/CSSE 474 Theory of Computation - Spring 2020 (202030)
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 (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:

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

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

1. Learn how to produce such symbols in software such as Microsoft Word, Maple, or LaTeX
2. 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.