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-awaking the mathematical thinking skills you have (hopefully) developed previously, and start applying them to problems in theory of computing.
-
Developing your ability to understand and produce constructive definitions of mathematical concepts, including understanding the connection between sets and the Natural Numbers.
-
Understand the Principle of Induction and how it enables proofs by induction.
Schedule
Before First Meeting (if possible): Course Registration Survey
Wednesday, 26 August, 3:30-4:45pm: Full Class Welcome Meeting — Zoom Link
This will be the one full class meeting we plan to have during the semester, and it is at the officially scheduled class time. We hope everyone can make it to the meeting as scheduled.
Wednesday, 26 August, 10:59pm: Cohort Scheduling
To schedule the cohorts, it is essential that everyone in the course submits their scheduling preferences by 10: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 | "Monday" Cohort |
|---|---|---|---|---|---|---|
| Wed 26 Aug | Preparation | (Week 0) | (Week 0) | (Week 0) | (Week 0) | (Week 0) |
| Thu 27 Aug | Preparation | Preparation | (Week 0) | (Week 0) | (Week 0) | (Week 0) |
| Fri 28 Aug | Preparation | Preparation | Preparation | (Week 0) | (Week 0) | (Week 0) |
| Sat/Sun 29/30 Aug | Cohort Meeting | Preparation | Preparation | Preparation | (Week 0) | (Week 0) |
| Mon 31 Aug | Preparation | Cohort Meeting | Preparation | Preparation | Preparation | (Week 0) |
| Tue 1 Sep | Assessed Cohort Meeting | Preparation | Cohort Meeting | Preparation | Preparation | Preparation |
| Wed 2 Sep | Write-up Due | Assessed Cohort Meeting | Preparation | Cohort Meeting | Preparation | Preparation |
| Thu 3 Sep | Week 2 | Write-up Due | Assessed Cohort Meeting | Preparation | Cohort Meeting | Preparation |
| Fri 4 Sep | Week 2 | Week 2 | Write-up Due | Assessed Cohort Meeting | Preparation | Cohort Meeting |
| Sat/Sun 5/6 Sep | Week 2 | Week 2 | Week 2 | Write-up Due | Assessed Cohort Meeting | Preparation |
| Mon 7 Sep | Week 2 | Week 2 | Week 2 | Week 2 | Write-up Due | Assessed Cohort Meeting |
| Tue 8 Sep | Week 2 | Week 2 | Week 2 | Week 2 | Week 2 | Write-up 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 (Cohort Problems for Week 1 [PDF]), 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)
There is one additional reading for Week 1 (which you should have already done before submitting the registration survey):
Jeremy Kun, Habits of highly mathematical people (blog post on Medium, July 2016).
Videos
You can play all the week 1 videos using the playlist, but don’t forget to take breaks: Week 1 Playlist
These videos are edited from cs3102 Fall 2019 classes (we don’t generally recommend watching the unedited versions, but they are available if you want to):
Slides for “Why Study Theory?” through “Defining Equality” [PDF]
Slides for “Sets and the Natural Numbers” through the end of Week 1 [PDF]
Why Study Theory? (4:27)
Is Zero a Natural Number? (17:24)
Constructing the Natural Numbers (12:10)
Defining Equality (14:35)
Slides for “Sets and the Natural Numbers” through the end of Week 1 [PDF]
Sets and the Natural Numbers (7:53)
Defining Addition (8:04)
Principle of Induction (9:19)
Using the Induction Principle (1:28)
Defining the Binary Strings (5:49)
Defining Set Cardinality (5:28)
Contable Sets (6:40)
This video sets up, but doesn’t complete, the proof about the cardinality of the powerset.
See if you can finish it on your own. Then, look at our proof here: Powerset Proof
Cohort 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]
Write-up Problem
After the Assessed Cohort Meeting, your Cohort Leader will select one problem that your cohort needs to write-up and submit. The write-up is due by 11:59pm on the day after your assessed cohort meeting (see the schedule above).
The PS1 Template provides directions and a template for producing the PDF file you will submit as your write-up.
Download the Problem Set 1 Template