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

CS 3530: Computational Theory

@ Utah Tech University

Fall 2023 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 3310, each with a C- or better.

Course fees

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

Sections

One section:

1. MWF 9:00 - 9:50 am in Smith 116

   CRN: 40697

   Final exam on Monday, December 11 at 9:00 am - 10:50 am

Instructor

Instructor: Curtis Larsen

Email: curtis.larsen@utahtech.edu

Phone: 435-652-7972

Office: North Burns 233

Office Hours:

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 North Burns 233 or joining me virtually via Zoom, the choice is yours. You can find the Zoom link conveniently posted in an announcement on Canvas.

For the Spring 2024 semester, I’ll be available during the following times:

• Mondays and Wednesdays from 11:00 am to 12:00 pm
• Tuesdays and Thursdays from 1:00 pm to 2:30 pm

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.

Assignments are all written, but must be prepared using LaTeX. Most students will use Overleaf to generate the required PDF documents. Students will be required to use LaTeX source files, and submit PDF documents 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 several written exams, one at the end of part 1, one at the end of part 2, one after covering some part 3 materials, and a final. Topics from lectures, assigned readings, assignments, 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

Your assignment group score will be a floating point number between 0 and 1, found by adding up the number of assignment points obtained, and dividing by the number of possible assignment points.

The examinations are worth 100 points each. Your examination group score will be a floating point number between 0 and 1, found by adding up the number of examination points obtained, and dividing by the number of possible examination points.

Your course score will be a floating number between 0 and 1, found by multiplying your assignment group score and your examination group score.

Your course letter grade will be assigned based on treating your course score as a percentage and looking up the grade in the 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 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.

University Policies

Utah Tech Student Policies

Disability/Accessibility Resources

Utah Tech strives to make learning materials and experiences accessible for all students so if you are a student with a medical, psychological, or learning disability or anticipate physical or academic barriers based on disability, you are welcome to let me know so we can discuss options. Students with documented disabilities are required to contact the Disability Resource Center located in the North Plaza Building, next to the Testing Center (435-652-7516) to explore eligibility process and reasonable accommodations related to disability.

Title IX Statement

Utah Tech seeks to provide an environment that is free of bias, discrimination, and harassment. If you have been the victim of sexual harassment/misconduct/assault we encourage you to report this to the university’s Title IX Director, Cindy Cole, (435) 652-7731, cindy.cole@utahtech.edu. If you report to a faculty member, she or he must notify the Title IX Director about the basic facts of the incident.

Email Disclaimer

You are required to frequently check your campus email account. Important class and university information will be sent to your campus email account, including Utah Tech bills, financial aid/scholarship notices, notices of canceled classes, reminders of important dates and deadlines, and other information critical to your success at Utah Tech and in your courses. To access your campus email account, visit mail.utahtech.edu. Your username is your Digital ID (e.g. D00111111) If you have forgotten your PIN, visit my.utahtech.edu and click the “Forgot Pin” button.

Useful Resources

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

Important Dates Spring 2024

Click on this link: for the official academic calendar, which has several important dates you should be aware of.

Jan 8 - Date classes begin

Jan 12 - Last day to add without instructor permission

Jan 20 - Last day for refund of 100% tuition and fees

Jan 22 - Late registration / payment fee – Purge date (students who have not paid tuition / fees IN FULL or made payment arrangements may be dropped from classes!)

Jan 29 - Pell Grant census date

Jan 29 - Last day for refund of 50% tuition and fees

Feb 5 - Last day to add or audit classes with instructor permission

Mar 1 - Midterm grades posted

Mar 5 - Last day to drop an individual class

Apr 9 - Last day for complete withdrawal from all classes

Apr 25 - Last day of classes

Apr 26 - Reading day (no classes or exams)

Apr 29-May 2 - Final Exam dates

May 3- Commencement

May 6 - Final grades posted

Last Updated 08/16/2023