CS 252: Introduction to Computational Theory

Course Description

What does it mean to compute? Is computation a mathematical abstraction or a physical process? Are there limits to what can be computed? Can we build machines that can compute anything computable? This course will introduce the theoretical basis for the study of computation. We will study several models of computation including regular, context free and unrestricted languages and their respective equivalent recognizing (theoretical) machines: finite automata, pushdown automata and Turing machines. We will consider the question of what is computable and what is not. Finally, we will refine the question to what is practically computable.

Text & Reading

The text for the class is Introduction to the Theory of Computation, 3rd Ed. by Michael Sipser. (ISBN: 113318779X). We will cover much of the text following the provided schedule. You are responsible for reading the material for a given day prior to that day's lecture. Because class time is limited, we may not cover everything in the text. However, except where specifically noted otherwise, you are responsible for the entire text.

Attendance & Participation

Class attendance and participation are expected. This is not because I feel the need to have students in class; instead, it is because your attendance and participation guarantee you a better learning experience.

Make sure you have done the reading and tried to understand on your own before you ask questions. If you do not, it is usually readily apparent. This can lead to crankiness, and crankiness never was happiness. When you don't understand something, ask; there are no dumb questions—unless you haven't done your reading.

Homework Assignments

A few problems will be assigned (from the text) each class period and will be due at the beginning of class the following period. It is very important to stay current in this class and this homework schedule is designed to help you do so. This is where the pain and suffering occur.

Communicating clearly and concisely what you have to say is an important skill you will use throughout your career. All written assignments are to be neat and professional. If you cannot clearly communicate something, there is a good chance that you do not yet understand it well. Good writing, grammar, punctuation, etc. are important and can affect your grade.

Late Policy

All assignments are due at the beginning of class on the date indicated.

Exams

There will be two mid-terms (administered in the testing center) and one final (administered in class). These tests will be timed, you will be allowed one page of notes, and they will consist of written problems similar to those encountered on the homework. If you put in the time to understand the homework assignments, the tests should not be too difficult. Explicitly, the final will only deal with material not covered on the midterms; however, it will be implicitly comprehensive in that it will assume you understand the material covered throughout the course.

Grading

Grading will be on a weighted curve. An approximate breakdown is as follows:

25%	or	0%	Homework
50%	or	66%	Midterms
25%	or	34%	Final Exam

You may choose which grade breakdown you would like applied to you; however, that choice must be made at the beginning of the semester and will be binding for the entire semester. Although your final class grade will not be available until the end of the term, a cumulative point total will be available online and will be updated approximately weekly. You should check this periodically to ensure that my records are in accordance with the work you have done. Please bring any discrepancies to my attention immediately, as these things are usually easily resolved early and are often much more difficult as time passes.

Appealing grades on assignments and on tests begins with you. Make an effort to understand why you received the score that you did and make sure that you have a good reason to appeal. If after making these efforts, you still feel like you have a concern, the next step is to calmly and intelligently discuss it with TA. If after taking both of these steps you still are not satisfied, come see me.

Working Together

You may work together with other members of the class; in fact, you are strongly encouraged to do so; however, do NOT turn in other people's work. This is a fine line that may require some judgment on your part. Examples of acceptable collaboration: discussing homework problems and solutions with others in the class; posting questions and/or answers to questions on the class newsgroup; comparing learning results and conclusions from programming assignments with other class members. Unacceptable collaboration would be simply copying homework, code or test answers from a friend or allowing someone else to copy homework, code or test answers. Academic dishonesty will be grounds for failure of the course; however, I do not anticipate that we will have any questions or problems in this area.

Preventing Sexual Harassment

Title IX of the Education Amendments of 1972 prohibits sex discrimination against any participant in an educational program or activity that receives federal funds. The act is intended to eliminate sex discrimination in education and pertains to admissions, academic and athletic programs, and university-sponsored activities. Title IX also prohibits sexual harassment of students by university employees, other students, and visitors to campus. If you encounter sexual harassment or gender-based discrimination, please talk to your professor; contact the Equal Employment Office at 801-422-5895 or 1-888-238-1062 (24-hours), or http://www.ethicspoint.com; or contact the Honor Code Office at 801-422-2847.

Students With Disabilities

BYU is committed to providing reasonable accommodation to qualified persons with disabilities. If you have any disability that may adversely affect your success in this course, please contact the University Accessibility Center at 422-2767. Services deemed appropriate will be coordinated with the student and instructor by that office.