Week 1

Welcome to cs3102!

The main goals for the first week are:

  • Set up the cohorts, and have each group get to know each other and figure out how you will work well together to ensure everyone in your cohort succeeds in the course and has a good experience learning with others.

  • Re-awaken the mathematical thinking skills you have (hopefully) developed previously, and start applying them to problems in theory of computing.

  • Understand the relationship between functions and cardinalities of sets, including infinite sets.

  • Understand the Principle of Induction and how it enables proofs by induction.

  • Breakfast

Schedule

Wednesday, 25 August, 11:59pm: Cohort Scheduling

To schedule the cohorts, it is essential that everyone in the course submits their scheduling preferences by 11:59pm on Wednesday. We will send out the cohort assignments by Friday morning, and these will determine your schedule for the rest of the week (and semester).

Here is the expected schedule for cohorts, based on the day of your assessed cohort meeting. This schedule will repeat similarly throughout the semester.

Day “Tuesday” Cohort “Wednesday” Cohort “Thursday” Cohort “Friday” Cohort “Sunday” Cohort
Thurs 26 Aug Preparation (Week 0) (Week 0) (Week 0) (Week 0)
Fri 27 Aug Preparation Preparation (Week 0) (Week 0) (Week 0)
Sat 28 Aug Preparation Preparation Preparation (Week 0) (Week 0)
Sun 29 Aug Prep Cohort Meeting Preparation Preparation Preparation (Week 0)
Mon 30 Aug Revision Prep Cohort Meeting Preparation Preparation (Week 0)
Tues 31 Aug Assessed Meeting Revision Prep Cohort Meeting Preparation Preparation
Wed 01 Sep Writeup Due Assessed Meeting Revision Prep Cohort Meeting Preparation
Thurs 02 Sep (Week 2) Writeup Due Assessed Meeting Revision Preparation
Fri 03 Sep (Week 2) (Week 2) Writeup Due Assessed Meeting Prep Cohort Meeting
Sat 04 Sep (Week 2) (Week 2) (Week 2) Writeup Due Revision
Sun 05 Sep (Week 2) (Week 2) (Week 2) (Week 2) Assessed Meeting
Mon 06 Sep (Week 2) (Week 2) (Week 2) (Week 2) Writeup Due

Learning in cs3102

The concepts and techniques we hope you will learn in cs3102 are different from what you have learned before, and we hope they will lead you to develop new ways of thinking and approaching problems. It is not possible for most people to learn this passively; it is important that you are actively engaged in your learning, and it is a challenge for most people to do this in a virtual environment. We believe for most people this also involves a mix of solitary activities, that require internal effort and thought, and group activities, that require discussion and interaction with others.

Problems and Preparation: The weekly guides will include a set of problems (Cohort Problems below) that will be the focus on the assessed cohort meeting. We recommend reading through the problems at the beginning of the week, and starting to think about them before you do the readings and watch the course videos. Then, as you watch the videos and read the book chapters, you should return to the problems that are related to that material and try to solve them. For most students, we expect it will be better to mix up watching and reading with solving the problems, rather than doing all the preparation materials first before trying the problems.

Advice for watching the course videos: Most of us are well trained from thousands of hours of watching mindless television to let our minds go to mush as soon as a video starts playing. Staying engaged with videos is much harder than keeping focused in a physical classroom (which is already quite challenging for most people).

Here are a few tips that we hope will be helpful (if you have other suggestions, please share them with your classmates in the discord):

  • Watch together. If you are able to find others whose schedules’ align well enough with yours to watch the course videos as a group, this is a much better experience and more conducive to learning and discussion, than watching alone. There are several apps that allow a group to play youtube videos in sync (e.g., sync-tube.de), so you can watch the course videos as a group, pausing them to discuss and ask questions together. You can do this with other students in your cohort, but it is also fine to do it with other students in the class who are not in your cohort (or even with people not in the class).

  • Pause, think, and answer questions. Most of the videos are edited recording of lectures we have done in past offerings of this course. To make the videos watchable, “dead time” (such as long pauses waiting for questions and answers) is edited out of the videos (what was a typical 75 minute class, ends up as about 45 minutes of edited video). The “dead time” is time that students in the live lecture were (hopefully) spending thinking about what was just presented and the question that may have been posed. We encourage you to pause the video at points in the lectures, especially after the lecturer poses a question, to see if you can answer it yourself before proceeding with the recording.

  • Take notes. Writing things down helps understanding. It might seem silly to take notes when you know you can always replay the video, but the main value of taking notes is the act of the note-taking, not the product of the notes. We encourage you to approach the videos like you would an in person lecture, and take notes as you watch them, and take advantage of the opportunity to pause and rewind when helpful.

  • Speed-up. Youtube supposed watching videos at various speeds, up to 2x the normal speed. For parts of videos where you are confident in the material already, it is fine to watch at high speed (1.5x is usually reasonable). It is better to be engaged with a speeded-up video, than to be bored by a normal-speed one.

  • Take Breaks. Watching videos can be exhausting. Take breaks often (we include a few reminders and suggestions in the embedded videos below, but don’t limit your breaks to these, and don’t feel obligated to follow our suggestions). Get your eyes of the screen, and go outside if you can.

Reading

The main textbook we will use is Introduction to Theoretical Computer Science by Boaz Barak. We will refer to this as the “TCS” book.

This is an open textbook, you can download the full PDF from https://files.boazbarak.org/introtcs/lnotes_book.pdf and contribute to the book by submitting Issues and Pull Requests at https://github.com/boazbk/tcs. (See the Syllabus section on “Bonus Points” for a bit of extra motivation for doing this, if just making the world better for future generations of Theory of Computing students isn’t enough already.)

For Week 1, you should read these two chapters from the TCS book:

Chapter 0: Introduction [PDF]
Chapter 1: Mathematical Background [PDF] (you can skip 1.4.8 and 1.4.9 on Asymptotics and Big-O Notation for now; we will go into more depth on this later in the course)

Videos

You can play all the week 1 videos using the playlist, but don’t forget to take breaks: Week 1 Playlist

An Introduction to Problem Solving

Proofs and Pancakes (25:01)

Discrete Math Background

If there are discrete match concepts which you feel you might be rusty on, these videos are intended as a refresher. Feel free to skip if you’re comfortable with these things.

High Level Overview

Professor Harry Porter Has a great video that briefly touches many of the topics from discrete math that you’re expected to know for this course. You’re definitely welcome to watch the whole thing, but I’ve identified what I think are the most important pieces:

Brief but Deeper

Sets (11:11)

Functions (09:06)

Motivating The Math We’ll Use

We just talked about a lot of math in the previous videos. In the next couple of videos we’re discussing why we need to use that math, and how it’s going to fit into a course about computing.

Why bother with infinity? (07:14)

What do we compute on, exactly? (15:41)

Natural Numbers

Natural Numbers (03:12)

Induction

Induction (11:37)

Countability

Countability (09:30)

Problems

These are the problems you should discuss in your Cohort Meeting, and everyone in your cohort should be prepared to present and discuss solutions to at the Assessed Cohort Meeting:

Cohort Problems for Week 1 [PDF]

Writeup

This write-up is due by 11:59pm on the day after your assessed cohort meeting (see the schedule above). Unlike with other weeks, you task this week is not to write up one of the problems from this week’s problem set. Instead, this week your writeup is intended to familiarize you with LaTeX1, a document-editing programming language.

Your ultimate goal for this writeup is to submit a pdf that looks similar to this one by editing this template. Your submission should reproduce the proof as closely as you can, and should include a character/image of Professor Brunelle, Professor Evans and/or pancakes. As with the example, everything must fit on one page.

Register for Overleaf

Visit https://www.overleaf.com and register for an Overleaf account (if you don’t already have one). UVA has a site license to Overleaf, so if you register with your @virginia.edu email address you will have full access to all the Overleaf features for free.

Set Up Your Repository

Create your own copy of the Week 1 repository by following these steps:

  1. Download the Week 1 template
  2. In Overleaf, click on Create First Project or New Project in Overleaf and select Upload Project from the menu.
  3. Click Select a .zip file then select the week1_template.zip you downloaded in step 1

Edit the File

  1. Look in week1.text for the line, submitter{TODO: your name} and replace the TODO: your name with your name and UVA id: submitter{Nathan Brunelle (njb2b)}
  2. Replace the line, \usepackage{toc} (the second line in the file) with \usepackage[response7]{toc}. You can do this by using the LaTeX comment token, %. The rest of the line after a % is treated as a comment.
  3. Then, try rebuilding the PDF by clicking Recompile. You should see many things disappear, with only problem 7 remaining. (Note that response7 will leave only problem 7 in the pdf, response6 will leave only problem 6, etc. feel free to play around!)
  4. Put your reproduction of the proof in between \begin{proof} and \end{proof}.
  5. Upload your image to your repository
  6. Include your image in the pdf using \includegraphics[]{}. Put the name of the image between the curly braces (i.e. {}). Put options for display, like resizing, between [].
  7. If you get stuck, check out overleaf’s tutorials. I recommend starting by looking up \align.

Download and Submit

  1. Click on PDF in the left-hand size menu in overleaf
  2. Click recompile, and make sure the pdf appears as you’d expected
  3. Download the pdf to your machine, name it week1.pdf.
  4. Upload your pdf to kytos to submit.

  1. To Quote Leslie Lamport (the creator LaTeX) “One of the hardest things about LaTeX is deciding how to pronounce it. This is also one of the few things I’m not going to tell you about LaTeX, since pronunciation is best determined by usage, not fiat. TeX is usually pronounced teck, making lah-teck, and lay-teck the logical choices; but language is not always logical, so lay-tecks is also possible.” ↩︎