This is an archived page from the Fall 2019 version of the course.
For the latest version, see https://uvatoc.github.io.

Week 5

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

Problem Set 5 Template [zip].

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

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)

Breaktime

Asympototic Operators (7:05)

Using Big-O (Theorem 5.2) (4:51)

Understanding 𝑂, Ω, and Θ (7:20)

Breaktime

Big-O Examples (5:35)

Common Misuses of Asymptotic Notation (5:52)

Breaktime

Some Functions are Expensive (7:35)

Cost of Computing (5:02)