|
MA/CSSE 474 Theory of Computation - Summer 2013 (201340) |
|||||||||||||||||||||||||||||||||||||||||
Instructor info
Required TextAutomata, Computability, and Complexity: Theory and Applications by Elaine Rich (Prentice Hall, 2008)There is a companion web site: http://theoryandapplications.org/ Approximate reading schedule (I will adjust this as we go along)
Other Books
Course DescriptionRHIT Catalog DescriptionStudents 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, September 2009)Students who successfully complete this course should be able to:
PrerequisitesCSSE 230 Data Structures and Algorithms MA 375 Discrete and Combinatorial Algebra II
Appendix A of the textbook contains a review of most of the material you should know from those courses , some of it in slightly more depth than Ralph Grimaldi's book (for example, first-order logic). In addition, you should know the basics of Finite State Machines (Grimaldi Chapter 6 and Section 7.5), although the perspective on FSMs in this course will be a bit different. The main things that you should bring into this course
Course AssignmentsMany days there will be in-class quizzes, similar to other CSSE courses. In addition to questions that can be answered from the in-class material, there will sometimes be questions based on simple concepts from the reading assignments, as an encouragement for you to actually do the reading. [In the summer, these will not be assignments. I will post the quizzes and solutions on-line. I recommend that you read through the PowerPoint slides and try to do the quizzes, looking at the answers when necessary.]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. You may of course ask about any details that you do not understand. I strongly believe that reading the textbook will help you; sometimes there may be an ANGEL quiz that covers a reading assignment. I will assign some written problems, many of them from the textbook. They will usually be due on Mondays and Thursdays. When will problems be due? The usual pattern will be that problems assigned on Thursdays or Fridays will be due at noon on the following Tuesday, and problems assigned on Mondays or Tuesdays will be due on Friday. There may be some exceptions due to exams, break, or problems that are difficult enough to require more time. But you can always count on at least 60 hours between a problem's assignment and its due date. You will submit the homework to ANGEL drop boxes. You can either write them on your computer or write them by hand and scan them. The written problems will usually be short thought problems, mathematical analyses, formal proofs, or machine-design exercises. I expect you to think through them carefully and write your answers legibly and clearly (if you can't write it neatly, type it and print it). On some problems, not only the correctness but also the quality of your solution will determine your grade. 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 come back to difficult ones more often. Unless I specify otherwise for some 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. You should also acknowledge the collaboration in writing on the paper that you submit.There are no programming problems. This is essentially an abstract mathematics course whose area of application is computer science. 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. The textbook has many exercises at the ends of the chapters; 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. I recommend that you read them all, regardless of whether they are assigned. Get started early on all assignments! Sometimes you will need some "incubation time" before the problem is due. Policy on Late Assignments: Because of the number of students taking this class and because I am teaching an overload this term, I cannot accept late assignments. Please submit whatever parts you have done by noon on the due date. In calculating your assignment average, I will drop the score on which you get the lowest percentage score, so missing one assignment will not kill your grade.
Grade Components
MA/CSSE 474 Community
I encourage you to communicate with other
students. We can't duplicate the classroom
experience, but we get some sense of who is
in the class and how they are doing. I
encourage you to go into personal
preferences on ANGEL and make your picture
visible to other students. I encourage you
to write quite a bit about yourself on the
"Introduce yourself" forum. I
put the "introduce yourself" forum on ANGEL
instead of Piazza so it will only be visible
to students in the course.I also
encourage you to use the Piazza forums to
ask questions about course material or
homework, so they can be answered by other
students and/or so everyone can see the
questions and answers.
Email, Discussion Forums, ClassmatesI will usually communicate using Rose-Hulman email or via Piazza. You should check your email daily and make sure that your mailbox does not fill up.
Anonymous Suggestion BoxI 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 ANGEL site contains an anonymous suggestion box. I will get your comments, but I
cannot trace who sends them.
Academic IntegrityRecall the Institute policy on academic misconduct:
Exams and homework will be done on an individual basis except when explicitly noted. The simple rule of thumb for individual work is: Never give or use someone else’s code or written answers. Such exchanges are definitely cheating and not cooperation. The departmental statement on academic honesty has more detailed advice. We encourage you to work with other students. However, when it comes to writing up your solutions, it should be your own work (or the work of your group if it is a group or partner assignment). If you use someone else’s ideas in your solution (or any other work that you do anywhere), you have to:
If you are ever in doubt about whether some specific situation violates the 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 look at another student’s solution to get ideas of how to write your own code. Beginning the process of producing your own solution with an electronic copy of work done by other students is never appropriate. Plagiarism or cheating will 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. |