Syllabus (CSC 341 Fall 2022)

(Last updated: August 25, 2022)

Table of Contents

Introduction

Computer science is as much concerned with the analysis of computation as it is with implementation. In the study of algorithms, for example, we frequently analyze best, worst, and (when appropriate) average and amortized case runtimes. We might instead analyze the space requirements of an algorithm. For example, most sorting algorithms can be done in place requiring no more than linear space. Reachability (roughly speaking finding a path) can be done in as little as log space. Pursuing a formalization of these notions allows us to argue about the relative difficulty/tractability of problems or to determine if they are impossible outright.

In this course, we study the theory of computation to formally model problems and study their relationships with one another. In doing so, we can gain insight into not just a problem but all related problems. We can also identify problems which are intractable and might require probabilistic or approximation algorithms to solve with reasonable resources. Some problems, we will discover, can provably never have a solution, a fact which an imprecise understanding can often obscure.

Course Topics

  • Mathematical Literacy and Proof Techniques
    • Reading and writing mathematical proofs
    • Common formal mathematical argument
  • Regular Languages
    • Finite state automata
    • Nondeterminism
    • Equivalence of deterministic and nondeterministic models
    • Closure properties
    • Irregularity theorems
  • Context-free Languages
    • Pushdown automata
    • CF grammars
  • Context-sensitive Languages
    • Linear bounded automata
    • CS grammars
  • Turing Machines
    • Formal definition
    • Properties and variants
  • Computability Theory
    • Decidable languages
    • Undecidability
    • Reductions
    • Rice’s Theorem
    • Recognizable languages and co-recognizable languages
    • The halting problem
    • The Arithmetical hierarchy
  • Complexity Theory
    • P vs NP
    • Cook’s Theorem
    • NP-completeness
    • Savitch’s Theorem
  • Additional Topics in the Theory of Computation as Time Allows

Textbook

For this course, we will use Introduction to the Theory of Computation (3rd Edition) by Michael Sipser. Alternatively, the second edition of the text will likely suffice for the purposes of this course. Additional reading may be provided in html or pdf form on the main course page schedule as links.

Software

In this course, we will use both Microsoft Teams and email to facilitate communication. The former is the preferred means of communication but is also currently a work in progress.

For document creation, LaTeX is the usual go-to for scientific and mathematical work. There are many programs which facilitate its use. My personal recommendations are TexStudio for offline use (with MiKTEX as the LaTeX source) and Overleaf for online work. If you are unfamiliar with LaTeX, it would serve you well to learn it. If you do not have time, handwritten work will suffice for this class.

Diversity and Inclusion

I believe that any college-level course should challenge you and put you outside of your comfort zone. My mission as an instructor is to help you manage that discomfort so that you can grow in knowledge and maturity. Therefore, I strive to create a fully inclusive setting so that we all can ultimately succeed in the classroom.

Learning Needs

I welcome you to talk to me as early as possible about your distinctive learning needs. I particularly encourage students with disabilities to meet with me and discuss how our classroom and course activities could impact their work and what accommodations would be essential. As part of the accommodations process, I recommend talking to our Coordinator for Student Disability Resources for guidance and further instructions: Jae Hirschman.

If you require accommodations for this course, please email me, message me in Teams, or come in to my office hours so we can discuss them further in private.

Religious Observance Policy

I support the class’s religious diversity and anyone who needs to balance academic work with religious observations. Please let me know by week two if you will need to be absent from class for any religious holidays this semester, and we can work out an appropriate schedule for making up absences or missed work.

Other Accommodations and Absences

There are a limitless number of dimensions to diversity and inclusion, the totality of which are un-addressable with a finite set of policies. These may include other issues best addressed earlier in the semester (e.g., student-athlete scheduling) or as they arise (e.g., chronic health flare-ups). I will do my best to be flexible in these cases with the ultimate goal of facilitating your growth in this course. To do this, I need to receive advanced notice from you at least one week in advance (when possible) so we can make suitable arrangements.

Evaluation

As much as I would like to sit down at the end of the semester with each of you individually for an hour long chat to determine if you’ve learned the course material, I will not pretend that this is entirely practical at the current time. As such, your final grade in this course will be decided by a number of in-class activities, homeworks, and exams as follows.

Deliverables

There are several kinds of common deliverables (described below) I use to assess your mastery of the material that are described below in detail. The details of each are provided on the main page schedule once appropriate.

Labs

Labs are in-class activities or discussions (small group or whole class) that are designed to allow you to gain familiarity and fluency with the course concepts through grappling with the material directly. More often than not, labs will be completed in small groups so that you can take advantage of the benefits of collaborative learning.

Labs are graded on a satisfactory (S)/non-satisfactory (N) basis. If you have clearly put effort into your lab by considering the question at hand or completing the problems given to you (whether they are correct or not quite so), you can expect to receive a satisfactory grade. In many cases, it suffices to simply show up to class and engage with the material presented.

Homework

Homeworks are longer assignments consisting of five questions each in a similar vein to labs that are opportunities for you to demonstrate mastery of the course material. While you are free to discuss them with your peers, they should be completed on your own in your own words.

Homework problems are graded on a satisfactory (S)/non-satisfactory (N) basis. Clearly correct answers can expect to receive a satisfactory grade. Mostly correct answers may but will not necessarily receive a satisfactory grade. Note that readability is part of writing a correct solution to a problem. Solutions should be clear and concise.

Homework is to be physically turned in (legibly handwritten or typed) at the beginning of class on the date on which it is due. We reserve the right to not grade illegible solutions.

One week after a homework’s original due date, you may resubmit solutions deemed non-satisfactory to be regraded. Similarly, these resubmissions should be turned in at the beginning of class. These resubmissions should not contain previously satisfactory solutions, nor should they contain the previous submission’s solutions.

Exams

To directly access your mastery of this course’s learning outcomes, we will conduct a series of three exams over the semester covering the three major categories of the theory of computation: formal automata and languages, computability theory, and computational complexity. Each exam will be of the take home variety consisting of ten problems to be completed entirely on your own without discussion amongst peers, professors, Internet access, or any other source. Use of your notes and your textbook, however, is permitted.

Each exam problem is graded on a satisfactory (S)/non-satisfactory (N) basis. Clearly correct answers can expect to receive a satisfactory grade. Mostly correct answers may but will not necessarily receive a satisfactory grade. Note that readability is part of writing a correct solution to a problem. Solutions should be clear and concise and, as always, legible if handwritten.

Letter Grades

Major letter grades for the course are determined by a nine point system. The chart below lists the minimum amounts required to gain each number of points in a category of deliverables.

PointsLabs (42)Homeworks (10×5)Exams (3×10)
115xS35xS15xS
225xS40xS20xS
335xS45xS25xS

To convert points into letter grades, you may consult the chart below.

Points0123456789
GradeFDC-CC+B-BB+A-A

Note that I reserve the right to update the requirements for grades as circumstances dictate during the semester. For example, if a homework need be cut, the total number of satisfactory homework problems required will be adjusted accordingly. I will, in this process, update the requirements so that they are no stricter than they were previously.

Late Policy

Each student is allowed three Late Tokens (LT). Each LT allows a homework to be submitted one class period late. Multiple LTs may be used on a single homework assignment if desired. No homework may be submitted later than the last day of class.

Help, Collaboration, and Academic Honesty

Instructor and Course Mentor

When asking questions about the course, please use the Q&A channel on our Microsoft Teams site (a work in progress) as a first stop, so that your peers can benefit from your insight. Feel free to ask questions of these sort in the channel:

  • General logistics questions, e.g., questions about how grading works.
  • Any general questions about course content not related to deliverables.
  • Any questions about lab exercises.
  • Any general questions about demonstration exercises.

We will prioritize answering questions in the Q&A channel first.

Please use direct messages (DM) on Microsoft Teams or email (not public Teams posts) to contact the course staff directly about individual issues concerns logistics, grades, or demonstration exercises. Note that even though may be marked online we will generally not respond immediately—we will check and respond to our messages at fixed times throughout the day.

We will usually respond to emails as well; however, Teams is the preferred method of contacting us about course questions/concerns.

If you would like to discuss things in more detail (whether course content or more general questions about computer science, research, etc), feel free to stop by my office during my office hours (time/location kept up to date on the main page) or any other time my door happens to be open.

Mentor Sessions

The course mentors also holds optional mentor sessions outside of regular class time. In these sessions, the mentors guide you through practice problems designed to help you master the material and answer any questions about the course. I highly recommend you attend each of these sessions, even if you feel like you understand the material.

Peer Collaboration

Peer collaboration is an essential skill not just in scientific pursuits but in all careers and indeed in all aspects of life. However, this must be balanced in education with one’s own intellectual growth. While I actively encourage you to discuss both assignments and the course material with fellow students (or anyone else), all material presented as your own work must in fact be your own work. For example, if you work through a homework problem together with a classmate, you both should write the solution up individually in your own words and cite all resources you used in authoring your work. As a rule of thumb, you should be capable of reproducing your own work on the spot with minimal effort. Your goal should be to incorporate the course material into your greater body of knowledge rather than pursuit of a grade and degree.

Keep in mind that adaptation of pre-existing code or solutions, whether it comes from a peer, myself, or the Internet, requires a citation in cases where it is allowed.

If you feel that the stress and pressure of the course are compelling you to violate the academic honesty policies of the course and the college as explained in the student handbook, please talk to me as soon as possible. The course’s grading policies are designed to help you manage your time in light of the different stressors in your life. I will do my best to work with you to figure out how to help you better manage your time relative to your learning goals and desired achievement level for the course.

Course Materials

Our goal is to create an inclusive learning environment where people feel free to share, fail, and ultimately grow in knowledge. To create such an environment, we must be mindful of what we share outside of our learning space. To this end, I request that you refrain from sharing any recordings of our class meetings with others outside of the class. Recordings of class meetings that we provide, e.g., recorded through Microsoft Teams, are meant for your personal use and should not be shared outside of the class. By “recordings,” we mean video and audio capture, include static screenshots.

Furthermore, while you retain copyright of the work you produce in this course, we must still uphold the academic integrity of this course. To this end, you may not share copies of your assignments with others (unless otherwise allowed by the course policies) or upload your assignments to third-party websites unless substantial changes are made to the assignment (for example, significant extensions and improvements to your code). Ultimately, it must be clear that the end product is significantly different from what was asked in the original assignment.

Acknowledgements

I give thanks to PM for letting me copy-paste large swaths of his original syllabus here.