Diversity statement

At Pitt, we are always striving to improve our commitment to diversity and inclusion, and that includes promoting the most inclusive learning environmennt possible. I view diversity as a resource and a strength of our community, and I want to make this course work for studeents of all identities. It is my intent to teach in a way that is as respectful and inclusive as possible with regard to: race, gender/gender identity, sexual orientation, socioeconomic status, age, cultural background, as well as any other identities that I have unintentionally missed. I am always open to your suggestions, comments, concerns, and constructive criticism on how I carry out this ethos.

At Pitt we have stringent community standards for the treatment of others. I will not tolerate any hate speech, bullying, or harassment of any kind, and I will report any violations of our code of conduct to the Title IX office.

Please feel free to let me know what name and pronouns you prefer to go by, and/or how you want your name to be pronounced, and I will make sure to address you how you want to be addressed.

Religious Observances

In order to accommodate the observance of religious holidays, students should inform the instructor (by email, within the first two weeks of the term) of any such days which conflict with scheduled class activities.

Students with Disabilities

If you have a disability for which you are or may be requesting an accommodation, you are encouraged to contact both your instructor and Disability Resources and Services (DRS), 140 William Pitt Union, (412) 648-7890, drsrecep@pitt.edu, (412) 228-5347 for P# ASL users, as early as possible in the term. DRS will verify your disability and determine whether reasonable accommodation(s) for this course are warranted. It is the responsibility of any student seeking accommodation(s) for this course to present any necessary documentation to the instructor by the start of the term.

Remote attndance

There will be a remote option for attending lectures; however, there are some strings attached. For Pitt to maintain its accrediation, a certain percentage of its courses must be run as "in-person". Unfortunately, this means that I am not allowed to give unfettered Zoom access to class. I have to do everything within reason to encourage in-class attendance. If you want to attend class remotely, you must email me at least one full hour prior to the start of class. You must provide a reason why you are physically unable to come to class. My general policy will be not to ask too many questions, however I reserve the right to ask for a note from a parent or doctor. You must email me each time you want to attend class remotely; if you attend one class remotely, that does not automatically grant you remote access for the next lecture. You should make sure to join the Zoom call 5 minutes before the start of class; if you try to join in the middle of my lecture I can't guarantee that I will see you in the breakout room.

To attend remotely, use the Zoom app. You can access all Zoom links through the Zoom tab in Canvas. Each lecture will be recorded through Zoom. You can find the lecture recordings through the Panopto video tab on Canvas.

Update: The first 2.5 weeks of the semester will be fully remote. The rules above will apply starting on Thursday, January 27th 2022.

Prerequisites

The prerequisites for this courses are CS 441 (discrete structures for computer science), and CS 445 (data structures and algorithms I), or equivalent. What this means is that I am assuming that have had some exposure to proofs (especially proof by contradiction and induction), first order logic, sets, and graphs. I am also assuming that you have done quite a bit of programming in your time at Pitt; this course will some programming, but I won't devote lecture time towards teaching you computer programming. If you are unsure about whether you have enough mathematical or programming background for this course, please feel free to reach out to me.

Textbook

This course will be self-contained. That said, I (strongly) suggest you obtain a copy of Michael Sipser's Introduction to the Theory of Computation (3rd Edition). This will provide much more thorough explanations of the material we cover. Furthermore, if you enjoy this course and choose to pursue the material further, you will probably need Sipser for future computability and complexity courses.

Grading Scheme

By default we will use the following grading cutoffs:

These cutoffs may be lowered if need be, but they will never be raised.

Below we describe all of the components that we will use to calculate your score. You may notice that the percentages add up to 110%, which is more than 100%. This is because different people learn in different ways, and different people succeed at different forms of evaluation. By structuring the class like this, you will have some leeway, and with enough effort you can earn a high grade without having to be perfect on every component of the course.

Note: The best way to think about this is that you have 110 chances to get 100 points. This grading scheme does NOT mean that you get 10 "free" percentage points. It means you get 10 "free" opportunities to earn percentage points. If you have any questions about how to calculate the grade, you should email me for clarification.

Participation and effort (10%)

Part of your grade will be based on simply demonstrating that you are putting your best foot forward, and going above and beyond simply showing up for class. The main way I will measure participation is by taking attendance on Top Hat. I will also administer in-class questions to help practice the material and diagnose any misconceptions. These questions are graded based on completion, not correctness. As long as you attempt the question you will get credit. Your participation grade will primarily be based on your overall top hat score.

We understand that circumstances will come up, and you may not be able to make it to every second of class. Thus, if you answer at least 80% of the Top Hat questions, you will get the full 20% of participation points. If you answer less than 80% of the Top Hat questions, you will get an extra 20% added to your score - so for example, if you answered 70% of the Top Hat questions, your Top Hat score would be augmented to 90%, and you would get 9% for your participation score.

I do not schedule Top Hat make-up sessions, for the simple reason that it would be a logistical nightmare to try to schedule different make-up sessions for all of the different students who had to miss lectures (or parts of lectures). If you miss a lecture, don't stress, and remind yourself that you have quite a bit of leeway to miss some Top Hat questions without incurring a significant penalty to your participation grade.

Of course, some of you may not want or need to come to lecture very often. You can still get participation for being active in the class in other ways, including:

Basically, if I can put a name to your face, and if I have a distinct memory of you interacting with me and/or your fellow students, I will gladly add some "fudge points" to your participation score.

Additionally, as a part of your participation grade I ask that you complete a short syllabus quiz on Canvas, to help you be fully prepared for what to expect in this class. Finally, if we cover all of the required material fast enough, we may cover some special topics. Each of these will come with in-class assignments that contribute to your participation grade.

Written Assignments (50%)

Every week you will complete an assignment based on material covered in the previous week's lecture. These assignments will involve designing different types of machines/expressions/grammars, describing algorithms, and writing proofs about what types of problems different machines can or can't solve. To succeed in this course, it will not be sufficient to simply get the correct answer on homeworks. You should aim to fully understand and digest the solution to each problem. A good rule of thumb is that you should aim to get to the point where you can reproduce the solution without referring to your writeup.

Each homework problem be graded as follows: you will get 50% for simply making a serious attempt, 80% for getting an answer that is mostly correct, and 100% for getting the answer fully correct. This means you have the freedom to make mistakes without getting severely penalized. If you are stuck on a problem, if you simply come to student hours I will give you enough help to get to that 80% threshold for free, and hints on how to finish off the problem.

Programming Assignments (10%)

You will have three programming assignments in which you will put into practice some of concepts and techniques we learn about in class. Each part will build on the previous part, and by the end you will have written a regular expression parser that is not all that different from how the grep command line tool works. This is not a programming class, and as such you will not be graded on programming style. As long as your program is correct, you will get full points. That said, if you program with good style it will be easier for me to help you. You may write your code in either Python3 or Java. If possible I highly recommend that you program in Python; I guarantee you this will make it easier to complete the assignment, and it will be easier for me to help you debug your code.

You may work on programming assignments alone, or with a partner. If you are working with a partner, you should both contribute equally to the project, and you should both fully understand all of the code that you submit. You are encouraged to use the pair-programming technique, in which one student will dictate code that the other student physically types.

When you write your code, external libraries are explicitly prohibited. You may NOT use any libraries or packages that are not part of the base languages. You may import packages or libraries that are part of the base language, however you may not import packages or libraries that are designed specifically for these problems (i.e., you should not import a regular expression parser even if it is part of the base language). If you are unsure, please contact the professor to get explicit permission for which libraries you may import. If you use libraries that I do not find acceptable, I reserve the right to ask you to resubmit the assignment without using that library.

Midterm Exam (20%)
Final Exam (20%)

I need some way to evaluate how well you yourself can understand the course material without the help of your peers and/or the instructional staff. That said, I do not believe in timed exams. Instead, I will administer two take-home exams: a midterm, which will be available in the middle of the semester, and a final exam, which will be available during finals week. The exams will be untimed, open book, and open note. I am trusting all of you to complete the exam with integrity. The exams will not be cumulative; the mideterm will be based on the first five assignments, and the final will be based on the final six assignments (or whatever material we cover after the midterm).

The exams will test your conceptual understanding of the material. You should not expect to be able to simply regurgitate the solutions to problems we did class and on the homework. You will need to have a thorough understanding of the techniques we used to solve those problems.

Extra Credit (~1%)

There will be some opportunities for extra credit. First, if and when time permits I will give students the chance to present solutions to homework problems in class. The first time you present a solution to a homework problem, you will get 5 extra credit points for that assignment. After that, you will get 1 point for each problem for which you present the solution. The catch is that you must be able to come up with a full solution without referring to your asssignment writeup. This is meant to incentivize you to not just complete the homework but understand the problems inside-out.

For each written assignmennt, you will receive 1 extra credit point for typing up your solutions. This is a reward for putting extra effort into your assignments to make it easier for me to read, as well as an incentive to learn how to write documents like a professional mathematician. To type up your work, I recommend that you use LaTeX, and in particular I recommend using Overleaf (aka "Google docs for LaTeX") for typsetting your writeups. You can access Overleaf's pro features for free using your Pitt credentials (see instructions here), or you can create a free account with your personal email. I will send out a survey to find the best time to schedule a LaTeX/Overleaf tutorial over Zoom. If you don't want to learn Latex, you are free to use a more familiar typesetting software (e.g. Word, Google docs, Pages, etc.) - you'll still get the bonus as long as you type it up.

In this class you will have to draw several state diagrams. You have a few options for putting them into your document. You can draw them by hand, take a picture or scan it, and insert the picture/scan into your document. You can also use software such as Flap.js or JFlap for drawing state diagrams. If you feel comfortable with python, you can use Dr. David Chiang's Theory of Computing Toolkit (tock). If you use these tools, please cite or acknowledge them in your writeup. Finally, you can actually draw diagrams from within Latex - this may seem intimidating at first but if you persevere you will see that this is actually the fastest and most convenient way to get state diagrams into your writeup. Here is a tutorial by Dr. David Chiang and Dr. Satyaki Sikdar on drawing state diagrams in Latex.

I always ask my students to give me feedback halfway through the term, and of course the university will have you fill out course evaluations at the end of the term. You will get extra credit for filling out these two feedback reports and helping me become a better teacher. Each of these surveys will be worth 0.5%, for a total of 1% extra credit.

Academic Integrity

We want you to succeed in this course, but we also want you to succeed with integrity. We want to make sure that you actually learn the material, so that the impact of the course doesn't disappear once the quarter ends. We also want to make sure that every student has a fair chance to succeed, and isn't being taken advantage of by his or her peers. You worked very hard to get into a prestigious school like Pitt, and without enforcing academic integrity that very prestige would quickly crumble. Personally, I can assure you that any grade increase that you receive in this class due to cheating will not benefit you nearly enough to offset the guilt.

In this course we expect students to adhere to the University of Pittsburgh of Scholarship Policy. This means that you will complete your work honestly, with integrity, and support and environment of integrity within the class. For written assignments, you are allowed (and encouraged) to collaborate on solutions; however, you are writing up your own solutions in your own words. A good rule of thumb is that you should never have more than one person's writeup in front of you; this will ensure that anything you write up is from your own memory and understanding, rather than mindlessly copying someone else's solution.

For the programming assignments, you should not consult with other groups. And for the exams, you may not collaborate with any other students.

Late Policy

Late Penalty

I will accept late work; however, I will impose a late penalty of 0.5% for each hour that an assignment is late. This means that if an assignment is a full day late, you will lose 24 * 0.5% = 12%. Note that canvas rounds up to the next hour, so if you are just 5 minutes late, this will be rounded up to 1 hour and you will still lose 0.5%. This late penalty applies to all assigned written and programming assignments, but not exams (which will not be accepted late). There is, however, a way to avoid late penalties...

Late Tokens

I understand that circumstances come up - family or medical situations, tough work in other classes, extracurricular commitments, your social life, etc. For this class, you have three (3) late tokens. A late token grants you the ability to turn in an assignment 24 hours late without incurring any penalties. You may use late tokens on any assignment, and you may use multiple tokens on the same assignment. Late tokens are cannot be transferred from one student to another. Late tokens cannot be split into fractional tokens. When you want to use a late token, email me and tell me which assignment you want to use a late token on (and how many tokens you want to use). You may request to use a late token at any time during the semester. You may use late tokens retroactively even after an assignment is due. You may retract a late token to save it or re-allocate it to a different assignment. You may not use a late token on exams.

You may use a late token on group assignments. However, your late token will only grant you an extension. Your other group members will still receive a late penalty. Perhaps this is fine with you; but if you want your entire group to have an extension, each person needs to use a late token.

Mulligans

If you ever accidentally submit the wrong document, and you don't realize this until well after the deadline has passed, you can get a one-time "mulligan" to resubmit the assignment without penalty. However, you must use a late tokens to get a mulligan. Furthermore, you may only get one mulligan per semester. Please be careful and make sure you upload the right document when you submit an assignment! Some additional notes:

Extenuating Circumstances

If you have a family or a medical emergency (including a mental health emergency), or if we encounter the literal apocalypse, I can grant you an extension without using a late token. In most circumstances, however, I will probably ask you to simply use a late token or take the late penalty. I reserve the right to request a note from a parent or doctor should you make such a request.

Grade Appeals

Grades can be appealed up to two weeks after they have been posted; no appeals will be considered after that time. Please note that the entire assignment will be regraded upon appeal.

Audio/Video Recordings

To ensure the free and open discussion of ideas, students may not record classroom lectures, discussion and/or activities without the advance written permission of the instructor, and any such recording properly approved in advance can be used solely for the student's own private use.

Copyrighted Materials

All material provided through course websites is subject to copyright. This applies to class notes, slides, assignments, exams, solutions, project descriptions, etc. You are allowed (and expected!) to use all of the provided material for personal use. However, you are strictly prohibited from sharing the material with others in general and from posting the material on the web or other file sharing venues in particular.

Covid Statement

At Pitt, we are committed to providing instruction in the safest and most responsible manner possible. We strongly encourage you to get a vaccine and a booster. You are also exptected to wear a mask when you are in the classroom or in my office for student hours. Please check out https://www.coronavirus.pitt.edu/ for more information on the guidelines that Pitt is recommending to mitigate the effects of the pandeminc.