Course Home | Syllabus | Assignments | Schedule | Downloads | [print]

CS 3530: Computational Theory

@ Utah Tech University

Fall 2025 Syllabus

Required of students pursuing a Computer Science degree or emphasis. Covers the theory of computation, including finite-state automata, pushdown automata, Turing machines, and equivalent formalisms. Also introduces complexity theory. **COURSE LEARNING OUTCOMES (CLOs) At the successful conclusion of this course, students will be able to: 1. Compare the capabilities of various computational models and formulating new models as needed to research new classes of problems. 2. Analyze formal systems with mathematical rigor and the appropriate formal notation. 3. Investigate computational problems and categorizing their algorithmic complexity. 4. Appraise and justify the limits of computational models and the real-world systems that rely on them. Course fee required. Prerequisites: CS 2420 (Grade C or higher); AND CS 2810 (Grade C or higher); and CS 3310 (can be concurrently enrolled). FA.

Students will complete written exercises.

Prerequisites

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

Course fees

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

Sections

One section:

1. TR 1:30 - 2:45 pm in Smith 116

   CRN: 40586

   Final exam on Tuesday, December 9 at 1:00 - 2:50 pm

Instructor

Instructor: Curtis Larsen

Email: curtis.larsen@utahtech.edu

Phone: 435-652-7972

Office: Holland Centennial Commons 463

Office Hours:

• Mondays 9:30 am - 11:30 am
• Tuesdays 3:00 pm - 4:00 pm
• Wednesdays 1:00 pm - 2:00 pm
• Thursdays 3:00 pm - 4:00 pm

Office hours are a fantastic opportunity to receive personalized assistance with any questions or concerns you may have about course concepts, assignments, or anything else on your mind.

I’m here to support you throughout the week with regular office hours. No need to worry about telling me in advance to use the scheduled office hours, just drop by whenever it suits you! Whether you prefer a face-to-face chat in my office at HCC 463 or joining me virtually via Zoom, the choice is yours. You can find the Zoom link conveniently posted in an announcement on Canvas.

If these times don’t fit your schedule, don’t hesitate to reach out to me. Simply shoot me an email or a message through Canvas, and we can find a time that works better for you. When you message me, suggesting a few alternative times would be incredibly helpful.

Looking forward to connecting with you during office hours!

Course Learning Objectives

At the successful conclusion of this course, students will be able to:

1. Compare the capabilities of various computational models and formulating new models as needed to research new classes of problems.

2. Analyze formal systems with mathematical rigor and the appropriate formal notation.

3. Investigate computational problems and categorizing their algorithmic complexity.

4. Appraise and justify 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:

1. 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 departmental 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.

Submission Format

All assignments are written, but must be prepared using LaTeX.
Most students use Overleaf to create the required PDF documents.
You will need to work from LaTeX source files and submit the final PDF to Canvas.

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

Assignment grading will consider promptness of submission, participation in class review of solutions, and earnest attempts to solve problems. 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 will be typeset in LaTeX to produce a PDF document. The PDF document will be submitted via Canvas file uploads. It is recommended that students use Overleaf for processing LaTeX documents into PDF documents. Overleaf has extensive documentation on how to use LaTeX effectively.

Note that technology problems are not acceptable excuses for late homework. You are responsible for completing all steps of the assignment submission in advance of the deadline.

Exams

There will be four written exams:
1. End of Part 1 of the text
2. End of Part 2 of the text
3. After selected topics from Part 3 of the text
4. Comprehensive final exam

Exams may cover material from lectures, assigned readings, assignments, and lab work. Some questions may extend or build on homework problems, so keep copies of all your work. All exams must be completed to pass the course.

Grading

Your grade is based on two parts: assignments and exams.

• Assignment group score – Add up all the points you earned on assignments, then divide by the total possible points. This will give you a number between 0 and 1.
  
• Examination group score – Each exam is worth 100 points. Add up your exam points, then divide by the total possible exam points. Again, you’ll get a number between 0 and 1.
  

Your course score is found by multiplying your assignment group score by your examination group score. This final number will also be between 0 and 1.

To find your course letter grade, treat your course score like a percentage (e.g., 0.87 = 87%) and use the grading table below.

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 will be accepted. All assignments must be submitted before class begins on the due date.
If you can’t attend class, you still need to turn in your work before the scheduled class start time to get 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.

University Policies

Code of Student Rights and Responsibilities (Academic dishonesty / academic integrity policy, student academic conduct policy)

Financial Aid

Registration

Student Association

Student absence related to college function

Sexual Harassment

Disability/Accessibility Resources

Utah Tech welcomes all students and strives to make the learning experience accessible. If you are a student with a medical, psychological, or learning disability that may require accommodations for this course, you are encouraged to contact the Disability Resource Center (DRC) as soon as possible. You may request reasonable accommodations at any time during the semester; however, they are not retroactive. The DRC is located next door to the Testing Center in the North Commons Building. (435-652-7516, drc@utahtech.edu).

Title IX Statement

Utah Tech University affirms its commitment to the promotion of fairness in all aspects of the educational institution. Harassment and discrimination – including sex/gender discrimination, gender identity, gender expression, sexual harassment, sexual misconduct, gender-based violence, dating violence, domestic violence, stalking, pregnancy or parental , family or marital status and or retaliation –not only disrupts our commitment to maintaining an environment in which every member of the University community is treated with respect and dignity, but may also violate University policy and federal, state, and/or local law. Should you or someone you know experience behavior that is coercive, discriminatory, harassing, and or sexually violent in nature, or if you or someone you know has questions about their rights and options regarding such behavior, you are encouraged to contact:

   Hazel Sainsbury
   Dir. Of Equity Compliance, Title IX Coordinator
   435.652.7747 (ext. 7747)
   hazel.sainsbury@utahtech.edu
   titleix@utahtech.edu

Incidents may also be reported directly to law enforcement, either separately or in conjunction with any report made to the University’s Title IX Coordinator, and the University will aid in making contact if requested.

      Utah Tech University Police
      435.275.4300 or by calling 9-1-1

Maintaining a safe and inclusive University community is a shared responsibility. For more information on how Title IX protections can benefit you and help us keep a productive campus environment, visit titleix.utahtech.edu to learn more.

Email Disclaimer

You are required to frequently check your Utah Tech email account as important class and university information will be sent to this account, including bills, financial aid/scholarship notices, notices of canceled classes, reminders of important dates and deadlines, course information, and other information critical to your success at UT. To access your Utah Tech email account, visit mail.utahtech.edu. Your email account username is Digital-ID@utahtech.edu (e.g. D12345678@utahtech.edu). If you don’t know or have forgotten your Digital-ID or password, please visit changepassword.utahtech.edu.

Useful Resources

• Disability Resource Center
• IT Help Desk
• Library
• Testing Center
• Tutoring Center
• Writing Center

Important Dates Fall 2025

Click on this link for important dates: https://catalog.utahtech.edu/academiccalendar

Aug 20 - Classes Begin

Aug 26 – Last day to add w/out instructor signature

Aug 29 – $10 drop/audit fee begins ($10 per class)

Sept 1 Labor Day Holiday (no classes)

Sept 2 - Residency application deadline, $100 late registration/payment fee

Sept 10 – Last day for refund; Last day to drop w/out a W, Pell Grant Census

Sept 17 – Last day to add/audit any course w instructor signature

Oct 9-Oct 10 - Semester Break (no classes)

Oct 13 - Midterm grades due

Oct 17 - Last day to drop an individual class

Nov 14 - Last day for complete withdrawal from all classes

Nov 24-Nov 28 - Thanksgiving Break (no classes)

Dec 5 - Classes End

Dec 8 - Dec 11 - Final Exams

Dec 15 Final grades due by instructors

Last Updated 08/08/2025