# CS 3530: Computational Theory

## Fall 2018 Syllabus

An introduction to the theory of computation. Introduces theoretical computation models, along with a formal treatment of their capabilities and limitations. Topics include regular languages and finite automata, context-free languages and pushdown automata, Turing machines and the Church- Turing Thesis, decidability, and complexity, including NP-completeness. Students will complete written exercises.

### Prerequisites

CS 2420, CS 2810, and CS 3310, each with a C- or better.

### Course fees

**Course fee:** $20, used to assist in maintaining department infrastructure.

### Sections

One section:

TR 1:00 pm in Smith 116

CRN: 41302

Final exam on Thursday, December 13 at 1:00-2:50 pm

### Instructor

**Instructor:** Curtis Larsen

**Email:** larsen@dixie.edu

**Phone:** 435-652-7972

**Office:** North Burns 233

**Office Hours:** MTWR: 2:00-3:00 pm; or by appointment. (See Zoom link in Canvas.) (Spring 2021)

## Objectives

At the end of the course, students will:

Understand and be able to reason about the capabilities of various computational models.

Be able to use formal notations and apply rigor in their analysis of formal systems.

Recognize and understand different classes of computational complexity.

Understand the limits of computational models and the real-world systems that rely on them.

## Resources

### Texts

There is one required text for this course. It is available from the campus bookstore:

*Introduction to the Theory of Computation, 3rd edition*by Michael Sipser, ISBN: 113318779X (required)

You are welcome to use the second edition as well, which may be cheaper.

### Computer labs

You may use the computers and software in the Smith Computer Center. Some lab assistants may be able to help with assignments and pass off homework assignments for introductory courses.

Assignments are all written, but must be prepared using LaTeX. LaTeX is installed on the lab-managed Linux machines, but you can also install it and use your own personal computer. You will submit hard copies of each assignment at the beginning of class on the day it is due.

### Course web site

Assignment submissions and grades will be managed in the Canvas System.

## Assignments and exams

### Reading

The student is responsible for reading the material in the textbook. A reading schedule is provided with the class schedule on the course website. The student is expected to read the material before the class in which it is discussed. The book also includes material beyond what we will discuss in lecture, which you are encouraged to study on your own. Feel free to bring questions from the reading to lectures or to office hours.

### Assignments

Assignments will be graded for correctness and elegance. It is important that you start early and get each of your assignments done before its due date. Many problems will take much longer to solve in a single sitting than in many shorter sessions. Give yourself time to think; sleep on difficult problems. Finish early so you can go back and refine your initial approach.

All assignments must be typed and handed in before class on the day they are
due. Students are required to use LaTeX to prepare assignments. LaTeX is
available on the Linux machines in the labs, and can be downloaded at no cost
for use on any machine. If you use Ubuntu Linux, install the package
`texlive-full`

to get the complete distribution. The book *Guide to LaTeX*
provides a complete introduction.

Note that technology problems are not acceptable excuses for late homework. You are responsible for typing and printing your assignments in advance of the deadline.

### Exams

There will be three written exams, one at the end of part 1, one at the end of part 2, a final. Topics from lectures, assigned readings, and lab work are all eligible for examination. Exams may include extensions of homework assignments, so be sure to keep copies of all of your work. Students are required to take all exams in order to pass the class.

### Grading

Assignments and exams each contribute to your point total. The assignments comprise 55% of your grade, the written exams will each comprise 15%.

Letter grades are assigned based on the percentage of possible points attained, according to the following chart:

Minimum Percentage | Letter Grade | Minimum Percentage | Letter Grade | Minimum Percentage | Letter Grade | Minimum Percentage | Letter Grade |

94 | A | 84 | B | 74 | C | 64 | D |

90 | A- | 80 | B- | 70 | C- | 60 | D- |

87 | B+ | 77 | C+ | 67 | D+ | 0 | F |

## Course policies

### Attendance

Students are responsible for material covered and announcements made in class.
School-related absences may be made up only if prior arrangements are made. The
class schedule presented is approximate. The instructor reserves the right to
modify the schedule according to class needs. Changes will be announced in
class and posted to the website. Exams and quizzes cannot be made up unless
arrangements are made *prior* to the scheduled time.

Occasional absences are acceptable as long as the student keeps up with assignment work. Students who miss more than two consecutive weeks of class or who miss more than 20% of scheduled classes during the semester without making prior arrangements will receive a failing grade. Students who miss any scheduled exam (including midterm exams and the final exam) or fail to complete a final project without making prior arrangements will receive a failing grade.

This course can only be completed by attending classes and completing all assigned work to a satisfactory level. There is no procedure for testing out of the class.

### Time Commitment

Courses should require about 45 hours of work per credit hour of class. This class will require about 135 hours of work on the part of the student to achieve a passing grade, which is approximately 9 hours per week. If you do not have the time to spend on this course, you should probably rethink your schedule.

### Late Policy

No late work is accepted. Assignments must be completed before the
beginning of class on the day they are due. If you miss a class, you
must submit your work *before* the scheduled class time to receive
credit.

### Collaboration

Limited collaboration with other students in the course is permitted. Students may seek help learning concepts and developing programming skills from whatever sources they have available, and are encouraged to do so. Collaboration on assignments, however, must be confined to course instructors, lab assistants, and other students in the course. Students are free to discuss strategies for solving programming assignments with each other, but this must not extend to the level of programming code. Each student must code his/her own solution to each assignment. See the section on cheating.

### Cheating

Cheating will not be tolerated, and will result in a failing grade for the students involved as well as possible disciplinary action from the college. Cheating includes, but is not limited to, turning in homework assignments that are not the student’s own work. It is okay to seek help from others and from reference materials, but only if you learn the material. As a general rule, if you cannot delete your assignment, start over, and re-create it successfully without further help, then your homework is not considered your own work.

You are encouraged to work in groups while studying for tests, discussing class lectures, discussing algorithms for homework solutions, and helping each other identify errors in your homework solutions. If you are unsure if collaboration is appropriate, contact the instructor. Also, note exactly what you did. If your actions are determined to be inappropriate, the response will be much more favorable if you are honest and complete in your disclosure.

Where collaboration is permitted, each student must still create and type in
his/her own solution. Any kind of copying and pasting is *not* okay. If you
need help understanding concepts, get it from the instructor or fellow
classmates, but never copy another’s code or written work, either
electronically or visually. The line between collaborating and cheating is
generally one of language: talking about solutions in English or other natural
languages is usually okay, while discussions that take place in programming
languages are usually not okay. It is a good idea to wait at least
30 minutes after any discussion to start your independent write-up. This
will help you commit what you have learned to long-term memory as well as help
to avoid crossing the line to cheating.

## College policies

Click on this link: https://academics.dixie.edu/syllabus/ for comprehensive information on the Semester Dates, the Final Exam Schedule, University resources such as the library, Disability Resource Center, IT Student Help Desk, Online Writing Lab, Testing Center, Tutoring Center, Wellness Center and Writing Center. In addition, please review DSU policies and statements with regards to Academic Integrity, Disruptive Behavior and Absences related to university functions.

If you are a student with a medical, psychological, or learning disability or think you might have a disability and would like accommodations, contact the Disability Resource Center (652-7516) in the North Plaza. The Disability Resource Center (http://dixie.edu/drcenter/) will determine eligibility of the student requesting special services and determine the appropriate accommodations related to their disability.

Last Updated 12/17/2019