This course deals with the study of formal models of computation. Topics include formal languages, automata theory, Turing machines, undecidability, and an introduction to computational complexity.

An Introduction to the Theory of Computer Science, Languages and Machines, 3rd edition by Thomas A. Sudkamp

CPSC 170 and MATH 131.

By the end of the course, successful students will have the following abilities:

1. Students will be able to use various proof techniques, e.g., proof by contradiction and mathematical induction, in proving properties of formal languages, e.g., regular and context-free.
2. Students will understand the formalisms of finite state automata and pushdown automata and their relationship with regular languages and context-free languages, respectively. Students will be able to construct, when possible, such automata to prove a given language to be of a certain type (regular, context-free).
3. Students will understand the formalism of a Turing machine and be able to construct such machines for Turing computable problems.
4. Students will understand the notion of undecidability and be able to prove problems to be undecidable.

The course will meet in class for 3 hours during the week. There will be three tests (on September 25, October 30, and December 4) during the semester. The final exam is scheduled for Tuesday, December 15, 2015 from 2:00 - 5:00pm.

In case of scheduling conflicts make-up tests will be available by pre-arrangement only. After the test, make-ups will be available only in case of documented medical emergencies.

Besides the exams, there will be quizzes in class, regular homework assignments, and a co-curricular requirement.

This course expects you to spend at least 12 hours of work each week inside and outside of class.

Quizzes: Quizzes will be in class and will be announced one class period before the quiz.

Homework: Homework will be assigned on a regular basis and posted at the course website. All homeworks are due at the beginning of class on the posted due date. All homework assignments must be handed in typed (either in LaTeX or your choice of typesetting software). The course website has a tutorial on LaTeX. Late home works will not be accepted.

Co-curricular Requirement: The Mathematics, Computer Science and Physics department offers a series of discussions that appeal to a broad range of interests related to these fields of study. These co-curricular sessions will engage the community to think about ongoing research, novel applications and other issues that face these disciplines. Each student is required to attend at least three of these sessions, and turn in a short paper describing the contents of the session, and his/her critical reflections about the topic and content. These papers are due in class within a week of the session. A paper submitted beyond a week from the event being discussed in the paper will not be accepted. The MCSP Conversation Series website has the schedule of talks in the series.

The final grade will be computed based on the grades in the quizzes, tests, the final exam, home works, and co-curricular activities according to the following weights.

The final course grade will be calculated as follows:

Regular attendance in class is highly recommended. Regardless of attendance, students are responsible for all material covered or assigned in class.

Cell phones should be kept in your backpacks or pockets (essentially, out of sight), and turned to the silent mode throughout the duration of the class. Please do not remove your cell phones until you are outside the classroom/lab. Similarly, during office consultations or consultations in the lab (even when it is not during regular class time), your cell phones should be out of sight and in the silent mode.

If you use an electronic device such as a tablet or a laptop for note-taking or to read the textbook, the content that is open on the screen should be strictly restricted to documents and pages of relevance to the class. For example, you should not have any social media websites open in your browser window, even if it is in a tab that is not currently in focus.

Students are expected to adhere to the Academic Integrity policies of Roanoke College. All work submitted for a grade is to be strictly the work of the student unless otherwise specified by the instructor. The policies as outlined in the Academic Integrity handbook will be enforced in the course.

Graded programs are subject to the Roanoke College Academic Integrity policies. Copying a program or a portion of a program (even a single line) or reading another person's program to obtain ideas for solving a problem is plagiarism. Other examples of integrity violation include writing code for someone else, using code written by someone else, telling someone else how to solve a problem or having someone tell you how to solve a problem (and using his/her method). These cases apply to any work that is handed in for a grade under the instructor's assumption that the work is your own. Unless specified otherwise by the instructor, discussion among students should be limited to general discussion of concepts and language details, not specific aspects of a solution to the assigned problem.