1 Logistics

1.1 Meetings

We will meet Tuesday and Thursday 3:30–4:45PM, in Ruffner Hall G008.

Lecture attendance is optional, but strongly encouraged. In the event you are unable to attend a lecture, recordings of lectures are provided on the schedule page.

1.2 Contact

Instructor TAs
Name Nathan Brunelle TBA
Location Rice 209 TBA
Office Hours MW 3:30pm-5:30pm TBA
Phone 243-3845 (none)
Email njb2b@virginia.edu use Piazza

For communication about course content, Piazza is preferred to email. For communication about personal circumstances, email or in-person visits are preferred. If you email, include either theory or 3102 in the subject line to prevent your email from skipping my inbox and never getting read.

Our TAs are students too, with duties and work outside of their TAing. Please do not ask them to act as your TA except at the scheduled on-the-clock times they have listed as their office hours. They are also kind people; please don’t put them in the position of having to say no or (worse) being nice to you at the expense of their own schooling.

1.3 Readings

We will primarily use the free online textbook Introduction to Theoretical Computer Science by Boaz Barak. Please first refer to the copy availble on our page. We will refer to the textbook as TCS when listing readings.

This is a new textbook that is freely available from introtcs.org under a Creative Commons license. In addition to costing $271.95 less than the traditional textbook for this class, this book takes a modern and innovative approach to introducing theory of computation which has several advantages (and a few disadvantages) of the traditional approach (which we will discuss some in class, and be happy to elaborate on during office hours). We plan to follow the organization and material in the textbook fairly closely, but will also cover some topics that are not included, and present some of the material in ways that are different from how it is presented in the book. Although the book is available free to read on-line, we do recommend printing out the chapters you are reading from the PDF files. Numerous studies have found that essentially everyone reads faster and comprehends better from printed paper than from even the best on-screen reading. To encourage on-paper reading, we will provide links on the course website to PDF files for relevant chapters. In addition to the course textbook, some readings will be assigned from other (freely available) sources.

This textbook is still in development, and Nathan Brunelle is in frequent communication with the author on improvements. If you find any errors in the textbook, feel free to submit an issue in the book github. Doing so will earn extra credit (with factual errors being worth more than typographical errors).

1.4 Lectures

I do my best to make lectures as valuable, engaging, and enlightening as possible for all students. For a schedule of lecture topics, please see the course webpage. Although we believe nearly all students will benefit from attending all classes, we also respect that as mature (ideally) college students, you are entrusted to figure out how best to learn and make use of your time here. Hence, I will not assess attendance or impose any penalties for missing class (other than the scheduled in-class exams, which you will find it difficult to pass if you do not attend class those days!). I will make a best effort to post all lecture materials (recordings, slides documents, etc.) on the course webpage, including video recordings of lectures. Be advised that there are occasional technical difficulties which sometimes cause the recordings to fail, and even when they do succeed these recordings are not an adequate substitute for attending class in person.

1.5 Tasks

You will be expected to read instructional material and either understand it or ask questions to clarify what you found confusing. We strongly recommend forming study groups that meet at least weekly all semester long to discuss readings, as even if they appear simple at first they will often contain nuances that will only emerge with conversions.

You will be asked to perform three kinds of evaluations:

  • Quizzes: open-resource assessments of your understanding of broad course topics. These are intended to verify that you develop and maintain an intuitive understanding of the course concepts. These must be completed independently.
  • Exercises: problems for you to solve. These may be programming assignments or formal mathematical arguments. These are to provide opportunities for you to develop working familiarity with course concepts. You are encouraged to work on these with a small work group of up to 3 people (yourself plus 2).
  • Exams: closed-book in-class exams. These are meant to evaluate your overall understanding of the course materials. You must complete these on your own.

2 Grading

In February 2019 the CS faculty approved a definition of what we believe grades mean. It is my intent to approximate that definition in this course. As a brief summary,

Letter Student demonstrated Recommendation re future courses1
A mastery of all topics likely to do well
B competence in significant topics able to do well with some review
C sufficient competence likely to be challenging
D minimal competence unlikely to succeed
F less than minimal competence retake this course first

We will consider the grade assigned by the following point-based breakdown to be a guideline for the grade earned according to the definitions above.

Task Weight Comments
Quizzes 15% We aim to have one quiz each week
Exercises 45% Excercises will be due frequently throughout the semester. Not all exercises will necessarily carry the same weight.
Exams 40% (12% each midterm, 16% final) Per College policy, Unexcused absence from a final examination results in an automatic grade of F in the course.
Professionalism Penalty 0–100% Excessive missed classes, rude behavior toward instructor or classmates, unauthorized homework assistance, contacting TAs when they are not on the clock, etc., can be held against a student when final grades are calculated.

The exact weights of assignments is subject to change as we further refine the assignments we will give.

Your final letter grade will then be assigned as follows:

You get if you score GPA value
A+ near the top 4.0
A ≥ 93% 4.0
A− ≥ 90% 3.7
B+ ≥ 86% 3.3
B ≥ 83% 3.0
B− ≥ 80% 2.7
C+ ≥ 76% 2.3
C ≥ 73% 2.0
C− ≥ 70% 1.7
D+ ≥ 66% 1.3
D ≥ 63% 1.0
D− ≥ 60% 0.7
F otherwise 0.0

Rounding: By default, grades will not be rounded in this course.

This numerical calculation is to be considered a guideline on your score in the course. Final letter grades may take other factors into account so that your grade is the most accurate reflection of your understanding of course materials. I expect that qualitative adjustments will only result in a student’s grade increasing (though in extreme circumstances I reserve the right to decrease grades).

2.1 Deadlines

Deadlines for all assignments and dates for all examinations are available on the schedule page. Please note that these dates may change in order to adjust for course pacing.

If you feel that extenuating circumstances justify late submission for any assignment, please request a deadline extension. You can do that on the same page where you would submit an assignment.

You may submit any assignment within 48 hours after the deadline with a grade penalty of 25%.

2.2 Regrades

We acknowledge that professors and TAs are people, and people make mistakes. For this reason, you are able to request regrades on assignments within 1 week of your grade being returned.

For exercises and exams, please only submit a regrade request if you believe the rubric was misapplied to your submission. In your request, identify specifically what in your submission demonstrates the misapplication.

The goal of quizzes is to help you to form a better conceptual understanding of course materials, and therefore we consider them primarily as an opportunity to identify and correct misconceptions. For this reason, you may submit one regrade request per quiz to revise your answers.

3 Miscellanea

3.1 Pledge

All students of CS3102 are expected to abide by the course pledge.

3.2 Professionalism

Behave professionally.

Never abuse anyone, including the emotional abuse of blaming others for your mistakes. Kindness is more important than correctness.

Let our TAs be students when they are not on the clock as TAs.

Lack of professionalism has an overall detrimental impact on our community of learning, and therefore egregiously unprofessional behavior could incur arbitrary penalty to your grade.

3.3 Honesty

I always hope everyone will behave honestly. I know we all are tempted to do what we ought not; if you do something you regret, the sooner you tell me the sooner (and more leniently) we can correct it.

3.3.1 No plagiarism (nor anything like it)

Quizzes: You must complete quizzes entirely on your own, do not discuss the contents of a quiz with anyone outside the course staff prior to its deadline. You may use only officially-provided or personally-created materials when completing at-home quizzes. This means you may only use:

  • The course textbook
  • Anything on the course webpage or linked to from the course webpage
  • Your personal notes (or those of a note-taker if you receive them as accommodation)
  • Lecture recordings

Exercises: You may collaborate with up to 2 other people (i.e. a group of up to 3 total) when completing exercises. You may additionally use external materials with following restrictions:

  • Your write-ups must be done entirely independently. You may take notes while meeting with your collaborators, but we expect that the answers you submit be expressed in your own words.
  • You must understand everything you submit. Do not submit anything you could not explain to a member of the course staff.
  • You must cite any and every source you consult beyond officially-provided materials (see list above). Included in your citation, you must identify which components of your submission came from each source (it will be understood that content with no citation is your own exclusive work). Your collaborators are considered to be sources, and so should be cited. An example citation might look like: I collaborated with David Evans on the pdf style, I consulted for help with the align environment, Robbie Hott helped me to debug the for loop on line 107 of my code.

Exams: You are permitted a printed-out 1 page (front and back) reference sheet for the exam. You may put anything you would like on this reference sheet. You are not permitted to use any other resources on the exam. This means that the following non-exhaustive list of items is not permitted:

  • Laptops
  • Cell Phones
  • Neighbors
  • Textbooks
  • Smart watches

3.3.2 Consequences of Dishonesty

If I believe you have acted dishonestly, I will communicate this fact to you and propose a penalty. If you have information I lack, please share that with me; I may thereafter change my belief and/or proposed penalty.

3.4 Personal accommodations

3.4.1 Special Circumstances

The University of Virginia strives to provide accessibility to all students. If you require an accommodation to fully access this course, please contact the Student Disability Access Center (SDAC) at (434) 243-5180 or sdac@virginia.edu. If you are unsure if you require an accommodation, or to learn more about their services, you may contact the SDAC at the number above or by visiting their website. For this course, we ask that students with special circumstances let us know as soon as possible, preferably during the first week of class.

3.4.2 Religious observances

It is the University’s long-standing policy and practice to reasonably accommodate students so that they do not experience an adverse academic consequence when sincerely held religious beliefs or observances conflict with academic requirements. Students who wish to request academic accommodation for a religious observance should submit their request in writing to Prof. Brunelle as far in advance as possible. If you have questions or concerns about academic accommodations for religious observance or religious beliefs,contact the University’s Office for Equal Opportunity and Civil Rights (EOCR) at UVAEOCR@virginia.edu or 434-924-3200. Accommodations do not relieve you of the responsibility for completion of any part of the coursework missed as the result of a religious observance.

3.4.3 Safe Environment

The University of Virginia is dedicated to providing a safe and equitable learning environment for all students. To that end, it is vital that you know two values that I and the University hold as critically important:

  1. Power-based personal violence will not be tolerated.
  2. Everyone has a responsibility to do their part to maintain a safe community on Grounds.

If you or someone you know has been affected by power-based personal violence, more information can be found on the UVA Sexual Violence website that describes reporting options and resources available. As your professor and a human, know that I care about you and your well-being and stand ready to provide support and resources as we can. As a faculty member, I am responsible employee, which means that I am required by University policy and federal law to report what you tell me to the University’s Title IX Coordinator. The Title IX Coordinator’s job is to ensure that the reporting student receives the resources and support that they need, while also reviewing the information presented to determine whether further action is necessary to ensure survivor safety and the safety of the University community. If you would rather keep this information confidential, there are Confidential Employees you can talk to on Grounds. The worst possible situation would be for you or your friend to remain silent when there are so many here willing and able to help.

3.4.4 Life

Bad things happen. People forget things and make mistakes. Bad days coincide with due dates. Etc.

If you believe that circumstances warrant an change in deadline, a second chance, or some other accommodation in order to more accurately synchronize grade with knowledge, come talk to me and we’ll resolve the situation as best we can.

If you are feeling overwhelmed, stressed, or isolated, there are many individuals here who are ready and wanting to help. The Student Health Center offers Counseling and Psychological Services (CAPS) for all UVA students. Call 434-243-5150 (or 434-972-7004 for after hours and weekend crisis assistance) to get started and schedule an appointment. If you prefer to speak anonymously and confidentially over the phone, Madison House provides a HELP Line at any hour of any day: 434-295-8255.


  1. While there are no regularly-offerred UVA undergraduate courses which list cs3102 as a prerequisite, this recommendation will be mostly relative to a hypothetical follow-on course.↩︎