MCS-265: Theory of Computation (Spring 2004)

Overview

In this course we will learn the theoretical underpinnings of computer science. We will learn about the fundamental capabilities and limitations of different computing devices. Much of our studies will be foundational in nature, but we will also discuss applications to hardware design, pattern matching, compilers, and other areas of computer science. Surprisingly, this theory began years before the advent of the modern computer!

The prerequisite to the course is MCS-236. In short, this course will build on your skills to manipulate mathematical notation and write formal proofs. If you have been uncomfortable with these skills in the past, you may have troubles in this course. Although I will quickly review the material in Chapter 0, I expect you to already be comfortable with the vast majority of the material there.

Reaching me

All office, phone and schedule information will be maintained on my web page. I'll try to keep it updated with any temporary changes to my schedule as well. In short, if my office door is open you are welcome; if I'm busy, we'll set up an appointment. Email and phone calls work, too.

All course handouts will be available through my World Wide Web page, and some supplementary materials such as code to use as a starting point in assignments may be available there as well. The URL for this course is http://www.gustavus.edu/~wolfe/265/.

World Wide Web

All course handouts will be available through my World Wide Web page, and some supplementary materials such as code to use as a starting point in assignments may be available there as well. The URL for this course is http://www.gac.edu/~wolfe/55/.

Text and references

Our text for the course is Sipser, Introduction to the Theory of Computation, 1996. The text is modern, up to date, and is as lucid and conversational as possible while remaining theoretically formal. We'll be covering Chapters 1, 3, 4, 5 and 7, and a few other miscellaneous topics. You should be aware that material from Chapter 2 which is usually covered in a course like this will be omitted. (If you plan on taking the GRE exam or going to graduate school, be sure to read and understand this chapter as well!)

Garey & Johnson, Computers and Intractability: A guide to the Theory of NP-Completeness, 1979, is the definitive (though old) book cataloging NP-complete problems.

Hopcroft & Ullman, Introduction to Automata Theory, Languages, and Computation, 1979, would be a superb alternative textbook for the course.

Exams

Exams will be closed-book and closed-notes. You may, however, use a single 8 1/2 by 11 sheet of paper with hand-written notes for reference.

Late policy

One assignment will be accepted up to 72 hours late without penalty, and one assignment can be up to 24 hours late; any more late will be heavily penalized. When submitting an assignment late, be sure to write the date and time of submission on your assignment. This very liberal late policy is intended to accommodate illness or conflict. Please do not ask for additional exceptions unless your situation is unusual. In any case, all assignments must be submitted by the last day of classes.

Homeworks

Homeworks and lab reports are due at the start of class on the due date. Please staple (not fold nor paper clip) your homework together.

Feel free to work on some problems in groups of at most 3 people, but write up your solutions separately (without help from others). Please be selective in choosing the most challenging problems to work together in groups.

For the most part, homework should be your own work. If you get help from a classmate or some other reference for a problem or two, be sure to cite the reference. The citation should appear at the top of your written problem solution.

The remarks I place on your homeworks are often quite brief. Feel free to ask me for clarification about any remarks or suggestions which are unclear or unhelpful.

Deliverables and grading

There will be about one homework per week (40%), three written quizzes (40%), and a portfolio (20%). Most semesters, I have held an oral quiz (10%); your final grade will be divided by 1.1 to account for 110% worth of points. If you earn 80% or more of the points, you will receive an A, 75% for an A-, 70% for a B+ and down by 5 percentage points each to the lowest passing grade of 35 for a D. There is no curve, although I reserve the right to adjust your grade at the end of the course.

A portfolio is due the last day of classes, consisting of typeset solutions written by you. These should represent those solutions, clearly written up, which you are especially proud of. You may submit your portfolio as often as you wish and I will provide feedback to help you hone your writeups. You are free to rewrite your solutions, reflecting these comments, to increase your grade. At the end of the course your portfolio should contain:

Your final grade portfolio grade will naturally take into account clarity and correctness of your solutions. More difficult problem choices or more original approaches to solutions are also valued.

Grade changes

Any grade disputes should be made before the final exam. I will fix obvious grading errors promptly (and will thank you for pointing them out). For students especially fond of debate, I reserve the right to regrade a whole homework or exam.

Extra credit problems

At times I will hand out extra credit problems. You should work on these problems alone, without the aid of other students. I will not specify the amount of extra credit you will receive for a problem. Extra credit problems are due the last day of classes or the day I hand out a solution, whichever comes first. You should work alone on all extra credit problems . Submit solutions separately from your homework.

Missed class

You are responsible for xeroxing a classmate's notes and handouts if you miss a class. Usually handouts will also appear in my homepage and/or outside my office door. After trying to catch up with the help of a classmate, feel free to ask me questions as well.

Honor

Students are encouraged to discuss the course, including issues raised by the assignments. However, the solutions to homework assignments should be individual original work unless otherwise specified. If an assignment makes you realize you don't understand the material, ask a fellow student a question designed to improve your understanding, not one designed to get the assignment done. To do otherwise is to cheat yourself out of understanding, as well as to be intolerably dishonorable. Any cheating may lead to failure in the course and notification of the dean. This includes copying anyone else's work, deliberately facilitating copying and failing to give credit for solutions not discovered on your own. Failure to cite a source (written or verbal) on any component of the course is considered cheating.