Week 2

Week 2: Bit Strings and Computing Models

At this point you should have been assigned to a cohort and met with them at least twice (once during your assigned prep time and once during your assessed time with a TA). This week, our main goals are:

  • Now that you’ve had some cohort experience, reflect on how to make the most out of your cohort experience this semester.
  • Begin exploration of the theory of computing, most importantly seeing the motivations for significant themes.
  • Discuss some similarities and differences between the theory and practice of computing.
  • Have you mind blown by infinities.
  • See and example of the limits of computing.
  • Learn a first model of computing.

Schedule

Day "Tuesday" Cohort "Wednesday" Cohort "Thursday" Cohort "Friday" Cohort "Sunday" Cohort "Monday" Cohort
Wed 2 Sep Preparation (Week 1) (Week 1) (Week 1) (Week 1) (Week 1)
Thu 3 Sep Preparation Preparation (Week 1) (Week 1) (Week 1) (Week 1)
Fri 4 Sep Preparation Preparation Preparation (Week 1) (Week 1) (Week 1)
Sat/Sun 5/6 Sep Cohort Meeting Preparation Preparation Preparation (Week 1) (Week 1)
Mon 7 Sep Preparation Cohort Meeting Preparation Preparation Preparation (Week 1)
Tue 8 Sep Assessed Cohort Meeting Preparation Cohort Meeting Preparation Preparation Preparation
Wed 9 Sep Write-up Due Assessed Cohort Meeting Preparation Cohort Meeting Preparation Preparation
Thu 10 Sep Week 3 Write-up Due Assessed Cohort Meeting Preparation Cohort Meeting Preparation
Fri 11 Sep September 11 and Distributed Hashing [video available Sept 11] (links below)
Week 3 Week 3 Write-up Due Assessed Cohort Meeting Preparation Cohort Meeting
Sat/Sun 12/13 Sep Week 3 Week 3 Week 3 Write-up Due Assessed Cohort Meeting Preparation
Mon 14 Sep Week 3 Week 3 Week 3 Week 3 Write-up Due Assessed Cohort Meeting
Tue 15 Sep Week 3 Week 3 Week 3 Week 3 Week 3 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 2 [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.

The above problems include completing the function implementations in this python file (the comments in the file itself will guide you, please read everything linearly): straightline.py.

If you already have python3 on your machine, you should be good to go for the programming problems. If you don’t, please follow these directions to setup Python.

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 PS2 Template provides directions and a template for producing the PDF file you will submit as your write-up.

Download the Problem Set 2 Template [zip].

Reading

Material in this week’s lectures parallels with:

  • TCS Chapter 2 for our discussions on what can and cannot be represented by binary strings.
  • This week’s discussion of Boolean circuits gives a high-level treatment of several sections of TCS Chapter 3. In particular, we give semi-formal coverage of sections 3.1, 3.2, 3.3, 3.5, and 3.6 (but we’ll discuss much of this in more detail next week).

Here are some things that may be of interest to you:

Videos

You can play all the videos using this playlist, but don’t forget to take breaks:Week 2 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 “Python vs. Mathematics” through “Counting the Binary Strings” [PDF]
Slides for “What is a Computer?” through the end of Week 2 [PDF]

Python vs. Mathematics (5:57)

Binary Relations (9:47)

Breaktime: Tell someone a Joke, share it on the off-topic discord channel if they laugh.

Do Infinite Sets Exist? (7:57)

Are there Sets Bigger than the Natural Numbers? (5:58)

Do some Minecraft Yoga

Cantor's Shocking Proof (7:20)

Counting the Binary Strings (4:40)

The proof that infinite binary strings are uncountable can be difficult to grasp, and is on its own pretty remarkable. Here are some additional presentations on the same proof we recommend watching:

Go Outside and Stargaze (if its nighttime) or Birdwatch

Slides for “What is a Computer?” through the end of Week 2 [PDF]

What is a Computer? (7:30)

Modeling Computers (8:16)

Play with Legos (or the closest thing you have to them, but if you don't have any legos, you should definitely get some)

AND-OR-NOT (4:32)

Programming with AND, OR, NOT (3:55)

Equivalence of Two Computing Models: NAND and AON (9:35)

Make a (non-alcoholic) beverage you've never had before

Boolean Circuits (10:31)

Daniel Lewin, 14 May 1970 – 11 September 2001

If you missed the link to the video for September 11, here it is (visible on Sept 11, but not earlier): September 11 and Distributed Hashing.

This is "course-optional" in the sense that you are not expected to answer any questions related to it, but we do hope you find it worthwhile to watch.

Hiawatha Bray. A Lost Spirit Still Inspires, Boston Globe, 4 September 2011.

Tom Leighton’s Remarks on Danny Lewin

No Better Time: The Brief, Remarkable Life of Danny Lewin, the Genius Who Transformed the Internet by Molly Knight Raskin.

David Karger, Eric Lehman, Tom Leighton, Matthew Levine, Daniel Lewin, Rina Panigrah. Consistent Hashing and Random Trees: Distributed Caching Protocols for Relieving Hot Spots on the World Wide Web. (Note: tradition in theory papers is to list all authors alphabetically). 29th ACM Symposium on Theory of Computing, 1997.