Goals
The main goals for Week 5 are to:
- Understand what a complexity class is and how to provide properties about circuit-size complexity classes.
- Learn the asymptotic operators (Big-O, Ω, and Θ) and how to use them correctly.
- Be able to both intuitively understand what functions are in O(f(n)), and to prove membership or non-membership.
- Be able to connect the formal definitions of computing costs to practical questions about the cost of computing.
Schedule
The schedule is identical to previous weeks, and repeated here (with updated dates).
| Day | "Tuesday" Cohort | "Wednesday" Cohort | "Thursday" Cohort | "Friday" Cohort | "Sunday" Cohort | "Monday" Cohort |
|---|---|---|---|---|---|---|
| Wed 23 Sep | Preparation | (Week 4) | (Week 4) | (Week 4) | (Week 4) | (Week 4) |
| Thu 24 Sep | Preparation | Preparation | (Week 4) | (Week 4) | (Week 4) | (Week 4) |
| Fri 25 Sep | Preparation | Preparation | Preparation | (Week 4) | (Week 4) | (Week 4) |
| Sat/Sun 26/27 Sep | Cohort Meeting | Preparation | Preparation | Preparation | (Week 4) | (Week 4) |
| Mon 28 Sep | Preparation | Cohort Meeting | Preparation | Preparation | Preparation | (Week 4) |
| Tue 29 Sep | Assessed Cohort Meeting | Preparation | Cohort Meeting | Preparation | Preparation | Preparation |
| Wed 30 Sep | Write-up Due | Assessed Cohort Meeting | Preparation | Cohort Meeting | Preparation | Preparation |
| Thu 1 Oct | Week 6 | Write-up Due | Assessed Cohort Meeting | Preparation | Cohort Meeting | Preparation |
| Fri 2 Oct | Week 6 | Week 6 | Write-up Due | Assessed Cohort Meeting | Preparation | Cohort Meeting |
| Sat/Sun 3/4 Oct | Week 6 | Week 6 | Week 6 | Write-up Due | Assessed Cohort Meeting | Preparation |
| Mon 5 Oct | Week 6 | Week 6 | Week 6 | Week 6 | Write-up Due | Assessed Cohort Meeting |
| Tue 6 Oct | Week 6 | Week 6 | Week 6 | Week 6 | Week 6 | Write-up Due |
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 5 [PDF]
The problems are posted here and we think its a good idea to look at them early, but you’re not expected to be able to solve them until after doing the readings and watching the videos below.
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).
Reading
This week focuses on material in Chapter 5: Code as data, data as code from the TCS textbook (which you already read last week, but we go into more depth on this week). The main theorems we focus on are in Section 5.2.
The TCS book does not provide a detailed presentation of the asymptotic operators, but reviews them in Section 1.4.8. Many books provide more detailed presentations of these concepts, and lots of examples. If you would like a more complex textbook explanation, the course instructors (at least one of them!) recommends this chapter: Chapter 7: Cost (from Introduction to Computing Explorations in Language, Logic, and Machines).
Videos
You can play all the videos using this playlist, but don’t forget to take breaks: Week 5 Playlist
These videos are edited from these cs3102 classes (we don't generally recommend watching the unedited versions, but they are available if you want to):
- (Spring 2020) Feb 13: Complexity - Full Video, Slides
- (Fall 2019) Class 11: Cost and Counting - Full Video, Slides
We don’t have exams this semester, but adventurous students may find the exam review from Fall 2019 useful (we may include some clips from this in a future class).
Introducing Complexity (8:02)
Complexity Classes: SIZE (6:19)
First Complexity Proof (4:39)
Asympototic Operators (7:05)
Using Big-O (Theorem 5.2) (4:51)
Understanding 𝑂, Ω, and Θ (7:20)
Big-O Examples (5:35)
Common Misuses of Asymptotic Notation (5:52)
Some Functions are Expensive (7:35)
Cost of Computing (5:02)