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:

1. Can it be solved using a machine of a certain type? (computability)
2. 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 either impossible or too expensive to solve with a computer, 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 cannot be solved efficiently.

• Learn about some interesting aspects of theoretical computer science, and why understanding them matters even if you are only interested in building practical computing systems.

Class Meetings: The full class meetings of the course are scheduled for Mondays and Wednesday, 3:30pm - 4:45pm in Maury Hall 209. In addition to the full class meetings, each student will be assigned to a cohort of five to seven students, who will meet twice a week. Detailed on the cohort meetings are below).

Due to the ongoing pandemic and current understanding of the transmitability of the Delta variant even through vaccinated individuals, we think it would be both unsafe and uncomfortable to many to cram the over 250 students in this class into a room with maximum capacity of 300. We are also aware that many students are eager to enjoy an in-person class experience, and as instructors, we share this desire to have the kinds of engaging interactions that seem to be much more likely in in-person environments than virtual ones.

Hence, we have planned the scheduled full class meetings to be inessential, but worthwhile, and structured in such a way that most students will come to one of the two full class meetings each week. By inessential, we mean that we will not introduce any course material upon which you will be evaluated during the class meetings which is not also covered by the provided course videos and written materials.

For most weeks, we will use the full class meetings as follows:

• Monday classes will be for covering examples, providing context, and answering student questions about the current week’s content, designed to help students understand the materials you will be assessed on during your cohort meetings. These will be before any of that week’s assessed cohort meetings, so all students will have the chance to benefit from these before your assessed cohort meetings.

• Wednesday classes will not cover anything directly related to the current week’s content (since this seems unfair to students who have their assessed cohort meetings on that material on Mondays or Tuesdays), but instead will include discussion of the previous week’s problems and excursions into topics we think are interesting and enlightening, and that have some connection to the course content, but that we don’t expect would provide any help for the specific cohort problems you are being assessed on that week.

All the full class meetings are strictly optional (other than the final exam at the end of the semester), and we will not be introducing any new material that you will be assessed on during these meetings. We will also be live streaming and recording them for students who are unable to attend in person.

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

We will expect everyone associated with the class (including the instructors, cohort leaders, and students) to follow state laws and University policies regrading health and safety requirements. These regulations are likely to change during the semester. The ones currently in effect as of 18 August 2021 state that “Masks are required for all people (students, faculty, staff, contractors, and visitors), both vaccinated and unvaccinated, who enter UVA properties.” This applies to all indoor spaces, including our classroom. Following these regulations is both important for your own health, but also essential for the safety and comfort for everyone in the community, including many who may have different risk profiles than your own such as living with elderly relatives or children too young to be vaccinated.

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

Cohort Leaders: See the Team Page for all our wise and wonderful cohort leaders (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.

Video Lectures: Each week’s preparation materials will include links to relevant (and maybe some irrelevant) videos that cover the material students are expected to learn in the course. These videos are mostly edited recordings of lectures from previous versions of this course, but also will include some additional videos and other materials.

In-Person Lectures: As discussed in Class Meetings above, we will be using the in-person full class meetings primarily for answering students’ questions on the content in the video lectures and course assignments.

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. A major part of the 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 Tuesdays; the schedule will adjust based on which day of the week the cohort meeting is scheduled):

Day	Activity	Time
Thursday	Preparation Materials: Video Lectures	90 minutes
	Preparation Materials: Readings	90 minutes
Friday	Work on Problem Set (individually)	90 minutes
Sunday	Cohort Meeting (without staff)	75 minutes
Monday	Class Meeting	75 minutes
	Complete Problem Set, Review for Cohort Meeting	45 minutes
Tuesday	Assessed Cohort Meeting	75 minutes
Wednesday	Write-up Selected Problem	60 minutes
Wednesday	Class Meeting	75 minutes

The schedule is designed to expect about 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 and the time needs for preparation will vary. 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

We encourage students to 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 a final exam, scheduled by the registrar at 2-5pm on Friday, 10 December 2021. The logistics of the final will depend on pandemic conditions in December, and we will announce more details on how the final will be conducted before Thanksgiving break. The content of the final will be comprehensive, designed to assess students’ understanding of the most important concepts in the course and ability to use them to solve problems and communicate arguments in writing.

Cohort Grading. Students performance in the weekly cohort meetings 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.

Writing Grading. Each week during the assessed cohort meeting the TA will assign one problem for a formal write-up. Students will be assessed by how well they can apply their knowledge and TA feedback to clearly present a complete and correct solution to this problem.

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.

Students will be assigned a grade based on their writeup quality on this scale:

Grade	Meaning
2	Writeup correctly solves the problem with a clearly-presented description
1	Writeup is correct except for some missing components or minor errors
0	Writeup contains major misconceptions, does not consider feedback from assessed meeting, or else presentation is unclear.

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 (thus 60 total points available for full credit, and some opportunities for bonus points). The individual cohort performance grade for students will be based on this scale:

Cohort + Writeup Points	Individual Grade
51	A
42	B
36	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.

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 video, 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 what students did last year.

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. This will be mainly determined by the 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. It will also benefit a cohort’s community grade if all members of the cohort do well on the final exam.

The community grade typically will impact individual final grades by up to half a letter grade. 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.

Final Grade Determination. The final grade in the course will be determined by combining the cohort grade and the final exam grade with both counting substantially. In most cases, we expect the cohort and exam grades will be consistent and provide clear evidence supporting the grade a student has earned in the course. In cases where they are inconsistent, we will consider a student’s performance through the course in more detail including the detailed feedback provided from the cohort meetings, and view signs of improvement throughout the semester positively. 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.

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.

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. Although University policy only recognizes religious accomodations, the course instructors believe they are many other valid reasons for accomdations that are at least as justifiable as ones for religious observance and consider family obligations, personal crises, and extraordinary opportunities to all be potentially valid reasons for accomodations. Students who wish to request academic accommodation 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 the University policy on 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.

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:

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