SYLLABUS

Instructor:

Prerequisites: Math 250 Discrete Mathematics or Math 330 Modern Algebra I and one computer science course.

Textbook (required): Sipser, M. Introduction to the Theory of Computation, 3rd Edition, Thomson Course Technology, 2013.

Automation Tool (Recommended): JFLAP 7.1 (available by downloading from https://www.jflap.org and installing on your own machine)
You should have Java 8.0 to run this program.

Assignments, class notes, and other material will be made available on the course homepage: http://www.cs.kzoo.edu/cs300/. Students are responsible for checking this resource frequently. Grades will be kept on Kit.

---

Course Overview

In this course we address the following foundational question of computer science: what can be (efficiently) automated? To even understand this question, we must be clear about what we mean by automation. So we begin the course by looking at several different mathematical models of computation: finite state machines, pushdown automata, and Turing machines.

A comparison of the various models of computation will suggest that Turing machines accurately represent our intuitive notion of computation, i.e. the problems that can be solved by a Turing machine are exactly those problems that can be solved automatically. As a result we rephrase our question: what problems can be solved by a Turing machine? We will look at some examples of problems that can be solved by Turing machines and examples of problems that cannot. Along the way we will also see ways to show that a problem cannot be solved automatically.

Finally we will consider the question of efficiency. Different ways of solving the same problem may take different amounts of time or space. We will talk about ways to analyze and compare the efficiency of algorithms, and then use this to classify problems according to how efficiently they can be solved. We will see examples of problems that can be solved efficiently, examples of problems that cannot be solved efficiently, and examples of problems for which the existence of efficient solutions is an enigma.

---

Intended Course Schedule

---

Attendance and Participation

Regular attendance and participation is expected of all students and will affect your grade. Active participation in this class means coming to class on time, completing assigned reading and exercises, presenting exercises, listening to others, contributing ideas of your own, and asking questions as they come up.

---

Assignments, Collaboration, and the Honor System:

This course operates in accordance with the principles of the Kalamazoo College Honor System: responsibility for personal behavior, independent thought, respect for others, and environmental responsibility. In particular, academic integrity is a fundamental principle of scholarship. Representing someone else's work as your own, in any form, constitutes academic dishonesty. Unauthorized collaboration and receiving help from others outside the bounds permitted by the instructor are also violations of the College honor code. You are responsible for working within the permitted bounds, and acknowledging any help from others or contributions from other sources.

Assignments, class notes, and other material will be made available on the course web site (http://www.cs.kzoo.edu/cs300/). Students are responsible for checking this resource frequently.

Reading assignments and related exercises will be assigned for each class. You are expected to come to class having done the reading and attempted the assignment and being prepared to discuss both the ideas from the reading and your solutions to the exercises. You are encouraged to work on these exercises in groups; just be sure that each group member understands each answer well enough to present it to the class. We will be working on many of these exercises in small groups during class time. When presenting an answer, you should acknowledge any help that you received.

Reflective Responses will be assigned several times during the quarter. These will be opportunities for you to reflect on what you are learning in the course and to give feedback on what would help you be more successful in the course.

Homework assignments will be assigned throughout the quarter. Homework assignments are due by the end of the day on the designated due date.

If you get stuck on a homework problem or just want to see if you are heading in the right direction, I am quite willing to help you. You may also discuss the requirements, concepts, and overall strategies related to homework problems with your classmates, as long as you walk away from the discussion without notes. It is important that you write up your homework solutions individually, acknowledging any ideas from others that you have used. Organizing and writing up the solutions on your own ensures that you really understand the solution. Copying someone else's solution does not help you learn the material. Submitting a copied solution as your own work is plagiarism. You are encouraged to type up your solutions. Any handwritten assignment that cannot be clearly read is subject to a loss of points.

Penalties for violating the Honor Code in this course may include receiving no credit for an assignment, a lowered course grade, or failure of the course. Depending on the severity of the incident, a report may be sent to the Dean's Office, which may result in additional consequences, including suspension from the College. Any subsequent violation will result in the immediate failure of this course.

---

Grades

Grades will be based on:

---

Title IX Support and Responsibilities:

Kalamazoo College strives to provide an environment free of bias, discrimination, and harassment. If you have been the victim of sexual or gender-based harassment, discrimination, misconduct, or violence, I encourage you to report this so the College can provide you options for support or resolution though the Title IX process. If you share information of an incident with me, I am required to notify the Title IX Coordinator about the facts of the incident. For more information about your options and confidential resources, please visit the Title IX website.