Overview

Course Description: The goal of this course is to understand the fundamental limits on what can be efficiently computed in our universe and other possible (or imaginary) universes. These limits reveal deep and mysterious properties about information, communication, and computing, as well as practical issues about how to solve problems.

Two fundamental questions about any problem are:

Can it be solved using a machine of a certain type? (computability)
How much does it cost to solve it? (complexity)

We explore these questions by developing abstract models of computing machines and reasoning about what they can and cannot compute efficiently. We will also look at some applications in cryptography that take advantage of problems being hard to solve, and what can be done when a problem cannot be solved or is too expensive to solve.

Course Objectives: Students who complete the course will:

Improve their mathematical thinking skill and habits, including thinking precisely about definitions, stating assumptions carefully, critically reading arguments, and being able to write convincingly.
Be able to understand both finite and infinite formal models of computation and to reason about what they can and cannot compute.
Understand both intuitively and formally what makes some problems too expensive to solve, and what can be done in practice when an unsolvable or intractable problem is encountered.
Reason formally about the cost of computation, and be able to prove useful bounds on the costs of solving problems, including showing that certain problems are intractable.
Learn about some interesting aspects of theoretical computer science, including cryptography and machine learning.

Class Meetings: The course is officially scheduled for Mondays and Wednesdays, 3:30-4:45pm. We will use this time for a full class welcome meeting on the first day of the course, Wednesday, 26 August. For subsequent weeks, students will have cohort meetings (see details below).

Pandemic. The challenges we are facing with the current pandemic places our community under tremendous stress, and we appreciate that many of our students are dealing with extreme personal challenges this semester. You should prioritize your own physical and mental health, and the well-being of your friends and family, over any class.

We endeavor to teach the class in a way that provides a learning opportunity and experience that is as valuable as what you would receive if we were able to hold in person classes, but know that remote learning presents substantial challenges both for teachers and learners, and that many students will have circumstances that make things especially difficult. We want the class to be a low stress, high value experience for everyone.

We will do everything we can to accommodate students varying situations, and to ensure that every student has the best opportunity possible to succeed in the class and have a good experience. Please communicate with Dave or Nathan (see details below) to let us know about difficulties you are facing, or anything we can do to make things better for you.

Preparation

Official Prerequisites: CS 2102 and CS 2110 (or comparable courses) with grades of C- or higher. (We will waive this prerequisite for students who convince us that they satisfy the expected background below.)

Expected Background: We expect students entering cs3102 to be comfortable using proof techniques including proof-by-contradiction, using quantifiers, and induction; reasoning about finite and infinite sets; and understanding recursive definitions and problem solving.

Programming: We also expect students to be able to read and write short programs. We will use the Python programming language for some assignments in the class. It is not necessary to have previous experience with Python, but you should have enough programming experience to be able to pick up what you need to read and write short Python programs on your own. If you do not satisfy the prerequisites, you should meet with one of the instructors to discuss whether you should take the class.

Course Staff

Instructors: The course is co-taught by Nathan Brunelle (njb2b@virginia.edu) and David Evans (evans@virginia.edu). Feel free to contact either of us with any questions about the course, computer science, or anything else you think we can help with (but please read the section below on communications to determine if it would be better to post a message in discord before emailing us).

Teaching Assistants: See the Team Page for all our wise and wonderful teaching assistants.

Office Hours: Office hours will be held using the course discord server. The full office hours schedule will be posted on the course site later.

Learning Materials

Textbook: Boaz Barak, Introduction to Theoretical Computer Science.

This is a new textbook that is freely available from https://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.

In addition to the course textbook, a few readings will be assigned from other (freely available) sources.

Lectures: Due to Covid-19, we will not have any in-person lectures this semester. Instead, we will be providing recorded videos, primarily adapted from lectures recorded from previous lectures for this course, and supplemented by other available materials. Each week’s preparation materials will include links to relevant (and maybe some irrelevant) videos.

Communication

We will primarily use the course website for one-to-many communications (posting course materials), and use the course discord for interactive communications.

Course Website: We will post all course materials at https://uvatoc.github.io. We will also use a custom-built Kytos site for assignment submissions, and may occasionally use the collab site to post materials we cannot post publicly.

Discord: We will use the course discord server for most other course communications (you will receive information on joining the server by email). We expect students to receive messages we send to the #general channel as well as any direct messages we send to you on discord. Each cohort will have a channel on the Discord server.

If you have questions about course materials or assignments that will be relevant to other students, please ask them in the #general channel. This will get the fastest response, since all of the course staff and students will see your question there and be able to respond to it. If you have questions of a personal nature that you only want to make to the instructors, please use the course discord to contact both of us (@nateb @DaveE) in a Direct Message channel instead of emailing us independently.

Email: Managing email for a large class like this is difficult, and we prefer to use the course discord for most communications relevant to the class. You should feel free to use email for messages peripherally related to the course (e.g., emailing an instructor about interest in their research). You should also use email if you post a question on slack but don’t receive an adequate response within 24 hours.

Cohorts

Students in the class will be partitioned into cohorts, small groups of 5 – 7 students, who we hope will form effective learning sub-communities. Each cohort will be expected to work as a group to help all members succeed, and each individual will be expected to contribute to their own success as well as the success of the other members of their cohort.

Cohorts will have two scheduled weekly meetings, one of which will include a member of the course staff. For the first meeting, students in the cohort will work together to learn the concepts in the course and prepare solutions to the assigned problems for the week. Before the cohort preparation meeting, each student in the cohort will be expected to study the course materials and to work on these problems on their own. At the end of a successful cohort preparation meeting, every student in the cohort should understand all the main ideas from the course materials for that week, and be able to solve and discuss the assigned problems.

For the second weekly cohort meeting, a teaching assistant will join the cohort. The TA will (pseudorandomly) select students in the cohort to present problems from the assigned problem set. The primary assessment for the course will be how well students do in demonstrating their understanding and preparation in presenting these problems.

The typical weekly schedule for students in the course is below (this is a representative schedule for a cohort with assessed cohort meetings on Mondays; the schedule will adjust based on which day of the week the cohort meeting is scheduled):

Day	Activity	Time
Wednesday	Preparation Materials: Video Lectures	120 minutes
	Preparation Materials: Readings	90 minutes
Thursday	Work on Problem Set (individually)	120 minutes
Friday	Cohort Meeting (without staff)	75 minutes
Saturday/Sunday	Complete Problem Set, Review	60 minutes
Monday	Cohort Meeting (with TA)	75 minutes
Tuesday	Write-up Selected Problem	60 minutes
Total Time		10 hours/week

The schedule is designed to expect 10 hours of total work per week, commensurate with a 3-unit course, and we expect this will work best for most students by spreading the work throughout the week following a schedule similar to the one above.

Although we have sequentialized the preparation and problem working efforts, we expect for most students these will be done more fluidly. It will be valuable to read through the assigned problems at the beginning of the week, and to attempt to solve problems as you complete the relevant preparation materials, rather than doing all the preparation materials first and then approaching the problems.

The actual schedule will vary based on the date of a student’s assessed cohort meeing, and all students are expected to participate fully in their cohort’s scheduled meetings (both the preparation meeting without staff, and the assessed meeting with the TA).

Students will be assigned to cohorts based on the information you provide in the beginning-of-course survey. Cohort assignments will be done around student’s provided scheduling constraints.

Problem Sets

For each week, we will provide a reading assignment (these will nearly always be from the Introduction to Theoretical Computer Science textbook and a set of recorded videos that cover the concepts for the week.

There will be a problem set with problems designed to develop your understanding of these concepts. We hope students will find value in applying theoretical insights to computer science practice, and we will also provide more concrete exercises to help students grasp theoretical ideas. For this reason, problem sets will contain a mixture of theoretically-focused written problems (with an emphasis on developing proofs) and integration-focused programming problems.

The assessed cohort meetings will focus on presenting and discussing problems in the assigned problem set. At the end of the cohort meeting, one or two problems will be selected to write-up and students in the cohort will be expected to write up a clear, correct, and well explaned solution to the selected problem. The cohort as a group will be responsible for writing the solution and submitting it as a group.

Grading

Spend your energy focusing on what you are learning, instead of worrying about your grade. That said, we understand students are often stressed about grading and understandably want to know where they stand in a class without having to rely just on the judgment of the course staff. We aim to grade in a way that is useful (provides students with accurate measure of how well they understood what they should), motivating (encourages the behaviors we prefer, including hard but not obsessive work), fair (assigned higher grades to more deserving students), robust (arbitrary small perturbations do not have a material impact on someone’s grade), and low stress (for both students and the course staff).

Exams. There will be no traditional exams in the course.

Individual Grading. The main assessment will be based on students performance in the weekly cohort meetings. Each student will be evaluated based on how well they are able to present problems at these meetings. It is not necessary or expected that students can solve every problem or have a complete solution, and the cohort meetings are meant more for learning than assessment, but it is expected that every student in the cohort is prepared to discuss every problem in the assigned problem set.

Students will be assigned a grade based on their performance at the cohort meeting on this scale:

Grade	Meaning
3	Able to present on the selected problem well and to demonstrate good understanding of key concepts.
2	Able to demonstrate some understanding of key concepts and preparation effort, but not able to make progress on the selected problem.
1	Showed some understanding of the concepts needed to solve the selected problem, but not well prepared or able to make steps towards a reasonable solution.
0	Not able to contribute to the cohort meeting.

We will make allowances for cases where a student is not able to make a scheduled cohort meeting due to extenuating circumstances and provide a way for students to request an exemption due to a valid reason for being unable to make a cohort meeting. Otherwise, a student who misses a cohort meeting received 0 cohort assessment points for that week. We consider medical issues, personal trauma, legal obligations, family responsibilities, and other justifiable conflicts to be valid reasons for missing cohort meetings, and students who are not able to make a scheduled cohort meeting for such reasons will not be disadvantaged as a result. In cases where a student has to miss more than two cohort meetings during the semester, we will provide an alternate assessment through an individual video meeting.

Following each cohort meeting, students will receive a grade and brief feedback from their TA. We hope this grading will be simple and clear enough that students will nearly always understand and agree with the grade they are assigned, but in cases where students feel they were graded unfairly there will be a mechanisms to request a reconsideration by the course instructors. To support this, the assessed cohort meetings will be recorded, but the recordings will not be released beyond the course staff.

We will have 12 assessed cohort meetings during the semester (with 36 total points available for full credit, and some opportunities for bonus points). The individual grade for students will be based on this scale:

Cohort Assessment Points	Individual Grade
30	A
24	B
16	C

With the exception of cases of academic dishonesty or inappropriate behavior, we guarantee that you will at least receive the minimum letter grade given in the table (possibly modified by a - based on the community grading described below), but you may be assigned a higher grade based on your overall performance and showing improvement over the course of the semester.

In cases where a student’s grade is not clear based on their cohort assessments, we will provide option for students to request an oral final exam to be scheduled with one of the instructors during the exam period.

Bonus Points. We hope students will go beyond the provided assignments and do other things to contribute to the class as well as beyond. We provide some concrete opportunities for this in the form of Challenge Problems, but also will award bonus points for relevant and creative activities that students invent on their own. We also offer bounty bonuses for contributions to the course textbook: having a Pull Request accepted by the author is worth something (even if it is just a simple typo fix) is worth one or more bonus cohort assessment points, and becoming the #2 contributor (by “Additions”) to the book repository is worth an automatic A in the class.

An additional bonus opportunity is to create an interesting artifact (could be a vi deo, song, comic book, or some other artifact that can be distributed on the Internet) that conveys something (at least loosely) related to theoretical computer science. We will post more information on this later, but to get an idea of what it will be and to start thinking of ideas for this, see Problem Set Ω (from cs2102).

Community Grading. In addition to the individual cohort assessment grades, each cohort will receive a community grade based on how well the cohort does as a group.

Two main factors will contribute to a cohort’s community grade:

Overall performance of the cohort during assessed cohort meetings. Doing well on this depends on all members of the cohort being prepared to present problems well. This will be determined based on the sum of the individual cohort assessments, the weekly individual minimum individual cohort assessment, and the trend of these values over the semester.
The quality of the cohort’s written problem submissions. The cohort will submit the problem write-up as a group, and everyone in the cohort receives the same grade.

The community grade typically will impact individual final grades by either a + or a - added to the individual letter grade (resulting from the individual grading above).

In most cases, the community grade will apply equally to all members of the cohort. In unusual cases where it is clear that one member of a cohort is not contributing, or there are reasons why a cohort is not succeeding that are beyond the responsiblity of individual students in that cohort, appropriate adjustments will be made.

Honor Expectations

We believe strongly in the value of a community of trust, and expect all of the students in this class to contribute to strengthening and enhancing that community.

The course will be better for everyone if everyone can assume everyone else is trustworthy. The course staff starts with the assumption that all students at the university deserve to be trusted.

To ensure that expectations are clear to everyone, all students are required to read, understand, and sign the course pledge: https://uvatoc.github.io/pledge.

Collaboration Policy: We believe it is important for students to learn by thinking about problems on their own, so it is expected that each student studies the provided materials and attempts to solve the problems on their own, before discussing the problems with cohortmates at the cohort meeting. You are welcome to also discuss problems with students and others who are not in your cohort, and to share what you learn from them with your cohortmates.

Many problems in this course will be selected from problems used in previous courses, as well as well known problems. The goal of these problems is to lead students to develop understanding of the underlying concepts by working through the problems themselves and in discussions with others, and this goal would be defeated if you instead use posted solutions to the problems (it will also probably be clear in the assessed cohort meetings if you do not understand a problem as deeply as you would if you solved in yourself). Other than using solutions to the specific problems you are given, students are encouraged to use any other resources they find helpful.

The collaboration policy will be described on each assignment document. We aim to make the language describing the policy as clear and unambiguous as possible, but if anything is ever unclear about the stated policy for an assignment, please clarify with the course staff. The penalty for policy violations will be considered on a case-by-case basis, with a penalty commensurate the severity of the offense.

Additional Information

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 https://studenthealth.virginia.edu/sdac

For this course, we ask that students with special circumstances let us know as soon as possible, preferably during the first week of class. This will be especially important if there is a reason you would not be able to participate fully in a scheduled cohort.

Religious Accommodations: 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 or Prof. Evans as far in advance as possible. If you have questions or concerns about academic accommodations for religious observance or religious beliefs, visit https://eocr.virginia.edu/accommodations-religious-observance or 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.

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 we and the University hold as critically important:

Power-based personal violence will not be tolerated.
Everyone has a responsibility to do their part to maintain a safe community on grounds (including in virtual environments).

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: https://www.virginia.edu/sexualviolence.

As your professors and as humans, know that we each care about you and your well-being and stand ready to provide support and resources as we can. As faculty members, we are responsible employees, which means that we are required by University policy and federal law to report what you tell us 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 (see https://eocr.virginia.edu/chart-confidential-resources ). 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.

Well-being: 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.

Syllabus