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.
|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|
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.
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.
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].
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:
- Cantor’s original proof (in German, but the math is universal, so somewhat understandable even without knowing German): Georg Cantor, Ueber eine elementare Frage der Mannigfaltigkeitslehre. Published in Jahresbericht der Deutschen Mathematiker-Vereinigung, Volume 1, 1891. (About this Scan)
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)::
Python vs. Mathematics (5:57)
Binary Relations (9:47)
Do Infinite Sets Exist? (7:57)
Are there Sets Bigger than the Natural Numbers? (5:58)
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:
Vi Hart video’s on Proof some infinities are bigger than other infinities and How many kinds of infinity are there? (sample youtube comment: watching this makes me feel like i’ve just taken the red pill and the blue pill, crushed them into a single, purple powder and snorted it).
Numberphile’s, Infinity is bigger than you think.
What is a Computer? (7:30)
Modeling Computers (8:16)
Programming with AND, OR, NOT (3:55)
Equivalence of Two Computing Models: NAND and AON (9:35)
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
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
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.