Mary Lyon Snow
CS 3780: Theory of Computation
(Fall 2019)

Syllabus

LMS

Teachers

Assignments



Other Pages
Syllabus

Course Description

Please see the department listing for important stats (credits, catalog description, pre/co-requisites, etc).

Goals

Successful students will:

  • Understand different models of computation.
  • Be aware of undecideable problems.
  • Be able to think abstractly about computing machinery.

Helpful Humans

Contacting Kyle

I love answering your questions! The basic rule of thumb for contacting me is: in-person > Slack > email. (People in person generally have priority over Slack messages, which generally have priority over emails.) The absolute best way to get in touch with me is to physically come to my office (check my schedule to see when I'm likely around). If I'm not in at the moment you arrive, I have a wheel to let you know where I'm at. If you need to schedule a time outside of my office hours, that's fine. If you just drop by to see if I'm there, that's great too! Please feel free to swing by and ask me questions even if I'm not expecting you. Getting in-person help is often the best way to clear something up!

If you can't reach me in person, the next best thing to do is to use Slack. You can find me on the department server and reach out in the course channel (tagging me is fine) or as a direct message to me. If you have something more serious that you want a better "paper" trail for, then I recommend emailing me (kburke@flsouthern.edu). I try to respond to all my email at least once per work day, but sometimes I don't keep up. If you don't hear from me via email after 24 hours during a work week, feel free to reply to the email with just the word "Bump" to get it back up to the top of my inbox. If you send me a message any other way, please do not wait for me to respond, as I probably won't see it. (E.g. via Canvas.)

When communicating with me, it is perfectly okay to call me "Kyle". (This is not true for everyone; please make sure you are respectful to other faculty members.)

Texts/Resources

Required:

Recommended:

Grading

Rubric
Homework:55%
Exams:45%
Letter Grades
[90, ∞):A[60, 70):D
[80, 90):B[0, 60):F
[70, 80):C

At the end of the semester, the final grade will be determined by the highest letter grade for which all minimum requirements are met according to the table above.

I am dedicated to getting your grade right. If you ever think I graded something incorrectly or you didn't understand how something was graded, please come talk to me about it. Grading is hard; I'm often fixing grading mistakes I made. However, I will never take off points for grading errors I discover because you came to talk to me!

Homework

Homework will be assigned regularly. There are very important rules for completing your homework:
  • A physical copy of your homework must be handed in (at the beginning of class).
  • Homework must be created in LaTeX. I recommend using CoCalc to write your LaTeX source so you don't have to install it natively. If you've never used it before, give this LaTeX tutorial a try. If you're not sure how to make a specific symbol, you can either visit me or use detexify.
  • Each problem must be clearly labelled and separated from other problems. The students who want to make my life easiest will include the problems book number, the assignment problem number, and the text of the question.
  • Your homework should always show adequate steps to answer any questions I may have while reading. I will deduct points for poorly-explained work. There are usually sample problems in the lecture notes that show the kind of supporting work I'm expecting.
  • You will need to make many figures for assignments. Your figures must be electronically generated; you may not use hand-drawn figures or images of hand-drawn figures. I use LibreOffice when I want to create with a WYSIWYG GUI, but I've found that the TikZ automata package has almost everything you want. Here's an automata example in a Stack Overflow question.

Exams

There will be a final exam and at least one exam during the semester.

Late Assignments

Late assignments will be penalized 10 points for each day it is late. (Fractions of days are rounded up.) Late assignments submitted after the final day of classes receive no credit. Far worse than any late penalty is the delay that will occur in the assignment getting graded by me. Due dates are often planned with so that I can grade them soon after. By missing the deadline, students risk a very long return on getting feedback.

Course Evaluations

Course Evaluations are an effective tool for me to improve my teaching each semester. I want to know which parts of the course worked well for you, and which did not. Please fill out an evaluation at the end of the semester!

In order to motivate evaluations, each course has the chance to earn 2 bonus (percentage) points. Everyone in the class earns this bump if 75% or more of the students complete evaluations before the beginning of the course's final exam period.

Office Hours

My office hours are listed on my schedule. This is special time I've put aside to take questions from anyone in any of my courses. I love answering questions, and I love having lots of students visit during office hours. If there are too many students to fit in my office, I'll usually move to an empty classroom. Be sure to check the wheel on my door when you visit for office hours; it will tell you where I am if I'm not there.

If I have a bunch of students, I usually handle things in a round robin fashion, giving each person the chance to ask one question each time around. I do my best to help as many people as possible.

If you need to speak to me about something sensitive and my office hours are busy, we can schedule another meeting, just send me an email. (This philosophy may differ from that of other instructors.)

I keep my door open lots (this helps me stay productive). Even if office hours aren't technically happening, I'd still rather be answering your questions than whatever else I'm doing. Ask me if I'm available. Sometimes I'm just too busy keeping up with grading and course bureaucracy.

Every so often I have to cancel my office hours for different reasons. I'll do this via Slack and will give you as much advance notice as I can.

Evening Tutoring

The department holds evening tutoring hours on the third floor of Memorial from 6-8pm, Monday - Thursday. This is done in conjunction with the PASS Office, who also offers one-on-one tutoring for most undergraduate courses at PSU. If you think you would benefit from working with a tutor, stop by their office in Speare 209, or visit https://www.plymouth.edu/centers/plymouth-academic-support-services/ to learn more.

Attendance

During the semester, each student may only have up to 3 unexcused absences/late-arrivals. Any student with 4 or more unexcused absences and/or late-arrivals automatically fails the course. Unexcusable reasons include oversleeping, weather, and workload. Excusable reasons include travel for conferences, illnesses, and emergencies. If you're not sure whether your reason is excusable, please ask me.

If you know ahead of time that you'll be absent, please give me at least two weeks notice. This is especially important if you'll be missing an exam! Otherwise, to get an absence excused, please email me as soon as it is reasonable to do so.

Class sessions before the add deadline count! If you are choosing between multiple courses, you should be attending meetings and completing work for all of them!

Illnesses

If you are feeling ill, even if you haven't been diagnosed with any sickness yet, please do not come to class. It doesn't matter whether there's an exam or a big due date or anything else. I both want you to rest up to help you get better and don't want to get anyone else in the class sick. If you aren't feeling well enough to attend class virtually, just email me whenever you can to let me know what's going on. If you can attend class virutally (and can give me enough warning) please email me to let me know. Even if I don't get back to you, please try logging on to zoom during the class time. If you have a friend in class, it is totally okay to message them to tell me to turn that on.

Catching Up

Even if you miss part of class, you are still responsible for everything that was discussed, including assignments, administrative changes, and other announcements. Please do not first come to me and ask me to go over the material with you. (It is considered especially egregious to ask "Did I Miss Anything?") Before coming to me:

  1. Look at the class schedule and do any of the reading that was covered. Don't just skim it, read it.
  2. Look over the notes of a classmate. (It's best to find people you can swap notes with before you are absent!)
  3. Try out some of the challenge problems I gave to the class, if any.

If you've done all of those and still have questions, come visit me so we can get you all caught up!

For absences that are both unexpected and excusable, you can have some extra time to complete assignments. These are the automatic extensions that may apply:

  • If you were absent for more than half of the school days during an assignment, the deadline is automatically extended by the amount of school days you were absent.
  • Otherwise, if you were absent during the deadline, the deadline is automatically extended by one day after you return to school.

If neither of these apply, talk to me if you feel you need extra time. Otherwise, if the new deadline goes past the last day of classes, you might need to request an extension. The paperwork for that can be found on the registrar's page. Please email me if this isn't clear!

My Expectations

This is a university-level course, and should not be taken lightly. There are many expectations I have of students planning to pass this course.

Academic Integrity

Academic Integrity is taken very seriously. Please make sure you're aware of all rules regarding working with others. Violations are reported and handled using the Academic Integrity Policy.

Honorably Reusing Code

It is important to be careful with the reuse of code and how academic integrity and the honor code apply to that. There are many potential sources of code that may or may not be allowed depending on the course. Here are the allowances for this course:

  • ✓ You may use code from class texts/resources listed in that section of this syllabus.
  • ✓ You may use code samples from the official documentation of the language(s) used in the class. ((Be careful to be only using the built-in packages and not docs from external packages that may not be allowed in this class. If you're not sure, ask me!))
  • ✓ You may use code presented as part of lecture.
  • ✓ You may use code from team members.
  • ✓ You may use code from school-employed student tutors and teaching assistants.
  • ⊘ You may not use code from any other people. (This includes students in and out of this course. If you provide code to anyone else in this way, you have violated this as well and will be penalized accordingly.)
  • ⊘ You may not use code from any other web sites or resources found online. (This includes from videos and other multimedia.)
  • ⊘ You may not use code generated by AI. (This includes ChatGPT and other AI programs as well as AI assistants in your IDE. It is your responsibility to know whether your IDE has an AI assistant and to shut if off. Do that right now!)
  • ✓ You may use generative AI to explain code and errors. (Important: You MUST include a link to all conversations you had with any of these along with your submission in a separate .txt file. Be very careful! You need to make sure you ask questions in such a way that the conversation doesn't violate any other items in this list. If you're ever not sure whether you're going to do something unallowed, please ask me first.)
If you do use code from anywhere (whether or not you're supposed to) please include a citation. If you use code without citing the source, that is one form of plagiarism! If you aren't sure about any of these rules, please ask first! All violations will be handled in accordance with the handbook.

Programming Collaboration

A vital part of this course is learning to work in teams. The following rules apply to teamwork.

  • Your group is allowed to work without the entire group present. Although you are allowed to write code on your own, this is a purposeful pit-trap. Pair programming is a very fast way to develop strong code! Cowboy coding is a good way to spend 5 hours doing something that would take two people working together only 1 hour.
  • Everyone should still be putting equal effort into the projects, so be certain to keep work loads balanced. I ask for an email from each participant where they detail the percentage of effort they think each person contributed to the project.
  • If a team member does not contribute adequately to a project, they will not receive any points for that project. If it is later discovered that they did not contribute adequately, any credit for the assignment will be removed.
  • If a student needs to change teams during the semester, I will try to assist in finding a new team, but it is ultimately up to the student to find a team. If they cannot find a team to work with, they will be unable to earn points for remaining team projects.

Accessibility Accommodations

Plymouth State University is committed to providing students with documented disabilities equal access to all university programs and facilities. If you think you have a disability requiring accommodations, you should contact Campus Accessibility Services (CAS), located in Speare 210 (phone: (603) 535-3300) to determine whether you are eligible for such accommodations. Academic accommodations will only be considered for students who have registered with CAS. If you have a Letter of Accommodation for this course from CAS, please provide the instructor with that information privately so that you and the instructor can review those accommodations.

Non-academic Student Support

Our Student Support Foundation (SSF) provides short-term emergency financial assistance and long-term student support. For more information, see the foundation's homepage. SSF also runs a food pantry located in Belknap Hall. To learn more about SSF or access the food pantry, either via open hours or a private appointment, contact the SSF advisor, at psu-ssf@plymouth.edu.

Old Work

I keep old completed work for at least one semester after the course has ended. This includes written homework, exams, etc. If you want any of your work, just come ask me. I'm very happy to get rid of it!


Schedule
WeekMondayWednesdayFriday
0
Week of
Aug. 25
Course Intro
Limits of Computation
Halting Problem
Languages
Computing Models
LaTeX Basics
LaTeX Basics
DFAs (1.1)
1
Week of
Sept. 1
Labor Day
DFAs (1.1)
LaTeX automata
Homework 0 due
More DFAs (1.1)
2
Week of
Sept. 8
More DFAs (1.1)
More DFAs (1.1)
DFA back-and-forth game (1.1)
DFA back-and-forth game (1.1)
NFAs (1.2)
Homework 1 due
3
Week of
Sept. 15
NFAs (1.2)
NFAs (1.2)
Language Operations (1.2)
Language Operations (1.2)
Subset Construction (1.2)
Homework 2 due
4
Week of
Sept. 22
Push-Down Automata (2.2)
Push-Down Automata (2.2)
LaTeX help (2.2)
Homework 3 due
5
Week of
Sept. 29
PDAs (2.2)
PDAs (2.2)
Deterministic PDAs (2.4)
Homework 4 due
6
Week of
Oct. 6
Turing Machine Examples (3.1)
Turing Machine Examples (3.1)
Turing Machine Examples (3.1)
TM Variants (3.2)
Regular Expressions (1.3)
Homework 5 due
7
Week of
Oct. 13
Indigenous People's Day
Regular Expressions (1.3)
Context-Free Grammars (2.1)
ICPC-Boston
Homework 6 due
8
Week of
Oct. 20
MSRI
MSRI
Midterm
9
Week of
Oct. 27
Context-Free Grammars (2.1)
Context-Free Grammars (2.1)
Context-Free Grammars (2.1)
Decideable Languages (2.1)
Homework 7 due
10
Week of
Nov. 3
Decideable Languages (2.1)
Inclusion vs Uninclusion
Pumping Lemma (RLs) (1.4)
Pumping Lemma Examples (1.4)
Pumping Lemma Examples (1.4)
Non-regular Languages (1.4)
11
Week of
Nov. 10
Veterans Day
Non-regular Languages (1.4)
Pumping Lemma (CFLs) (2.3)
Non-Context-Free Languages (2.3)
Homework 8 due
Non-Context-Free Languages (2.3)
Undecideable Languages and Reductions (?.?)
12
Week of
Nov. 17
Legal Affairs
Undecideable Languages and Reductions (?.?)
Undecideable Languages and Reductions (?.?)
Countable vs. Uncountable (?.?)
13
Week of
Nov. 24
Countable vs. Uncountable (?.?)
Unrecognizeable Languages (?.?)
Thanksgiving
Thanksgiving
14
Week of
Dec. 1
Unrecognizeable Languages (?.?)
Complexity Basics (?.?)
Complexity Basics (?.?)
Homework 9 due
P vs. NP History (?.?)
15
Week of
Dec. 8
Finals Week
Finals Week
Finals Week

Thank you for reading this long syllabus. Now that you've read the whole thing, you probably won't have this problem. If you think something is missing or isn't clear here, please let me know so I can clarify and improve my syllabi. The purpose of this "contract" is not to help you optimize your grade. Instead it is a mechanism to promote intellectual honesty and curiosity. I think I like this syllabus better, but it lacks the formality needed to address complaints.

Found here: https://www.reddit.com/r/Professors/comments/ac8qv6/youve_had_the_truth_all_along/