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


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.

Grading Scheme

By default we will use the following standard scale:

These cutoffs may be lowered if need be, but they will never be raised. Your grade will be rounded to the nearest integer percentage when we compute your grade.

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. Ways to demonstrate your participation and effort include:

Basically, as long as I have some memory of seeing you interact with me and/or your fellow students, you will get the full 10%.

Written Assignments (30%)

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/grammars, and writing proofs about what types of problems different machines can 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 (20%)

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

Final Project (25%)

You will complete a group project in which you will integrate the topics from this course with your own interests. Working in groups of up to four, you will pick a topic that is related to, but more advanced than, the topics we have covered in this course. You will learn about the topic, and prepare an 8-10 minute presentation on the topic that makes it digestible for your fellow classmates. This is a chance for you to engage the creative half of your brain, engage in critical thinking, and flavor this course in a way that matches your unique tastes. I am not expecting you to present at the level of an experienced theory instructor; as long as your presentation gets the main ideas across and demonstrates substantial effort and intellectual curiosity, you can expect to get the full points.

Final Exam (25%)

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 a take-home exam during finals week. The exam will be untimed, open book, and open note. I am trusting all of you to complete the exam with integrity.

The exam 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, I will give each of you 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 0.5% extra credit 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. You can use software such as Flap.js or JFlap for drawing state diagrams. 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.

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 and the final project, you should not consult with other groups. And for the final exam, 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. 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 the instructor and tell him which assignment you want to use a late token on (and how many tokens you want to use). You may not use a late token on the final exam or final project.

Extenuating Circumstances

If you have a family or a medical emergency (including a mental health emergency), 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 some sort of doctors or parent's note 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.