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

Day	“Monday” Cohort	“Tuesday” Cohort	“Wednesday” Cohort	“Thursday” Cohort	“Friday” Cohort
Wed 22 Sept	Preparation	(Week 4)	(Week 4)	(Week 4)	(Week 4)
Thurs 23 Sept	Preparation	Preparation	(Week 4)	(Week 4)	(Week 4)
Fri 24 Sept	Preparation	Preparation	Preparation	(Week 4)	(Week 4)
Sat 25 Sept	Prep Cohort Meeting	Preparation	Preparation	Preparation	(Week 4)
Sun 26 Sept	Revision	Prep Cohort Meeting	Preparation	Preparation	Preparation
Mon 27 Sept	Assessed Meeting	Revision	Prep Cohort Meeting	Preparation	Preparation
Tues 28 Sept	Writeup Due	Assessed Meeting	Revision	Prep Cohort Meeting	Preparation
Wed 29 Sept	(Week 6)	Writeup Due	Assessed Meeting	Revision	Prep Cohort Meeting
Thurs 30 Sept	(Week 6)	(Week 6)	Writeup Due	Assessed Meeting	Revision
Fri 01 Oct	(Week 6)	(Week 6)	(Week 6)	Writeup Due	Assessed Meeting
Sat 02 Oct	(Week 6)	(Week 6)	(Week 6)	(Week 6)	Writeup 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:

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.

There is no programming problem this week.

Writeup Problem

You writeups for this week will work a little differently from previous weeks. Since we will have a final exam in the course (and a midterm-like activity during the week of fall break) we wanted to give you experience solving problems on your own so that you can check your progress. As such, this week’s writeup will not be taken directly from this week’s problem set, and instead will be a new problem in the same style as problem 4.

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