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

Here is the expected schedule for cohorts, based on the day of your assessed cohort meeting. This schedule will repeat similarly throughout the semester, with minor alterations occurring due to break days.

Day	“Monday” Cohort	“Tuesday” Cohort	“Wednesday” Cohort	“Thursday” Cohort	“Friday” Cohort
Wed 1 Sept	Preparation	(Week 1)	(Week 1)	(Week 1)	(Week 1)
Thurs 2 Sept	Preparation	Preparation	(Week 1)	(Week 1)	(Week 1)
Fri 3 Sept	Preparation	Preparation	Preparation	(Week 1)	(Week 1)
Sat 4 Sept	Prep Cohort Meeting	Preparation	Preparation	Preparation	(Week 1)
Sun 5 Sept	Revision	Prep Cohort Meeting	Preparation	Preparation	Preparation
Mon 6 Sept	Assessed Meeting	Revision	Prep Cohort Meeting	Preparation	Preparation
Tues 7 Sept	Writeup Due	Assessed Meeting	Revision	Prep Cohort Meeting	Preparation
Wed 8 Sept	(Week 3)	Writeup Due	Assessed Meeting	Revision	Prep Cohort Meeting
Thurs 9 Sept	(Week 3)	(Week 3)	Writeup Due	Assessed Meeting	Revision
Fri 10 Sept	(Week 3)	(Week 3)	(Week 3)	Writeup Due	Assessed Meeting
Sat 11 Sept	(Week 3)	(Week 3)	(Week 3)	(Week 3)	Writeup Due

Sept 6 Meeting

In class on Monday Sept 6 we discussed content related to week 2. In particular, we discussed models of computing, comparing models of computing, and uncountability (in particular diagonalization). A recording of this discussion is available in collab under “online meetings”. The slides presented are available here.

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

Download the Problem Set 2 Template [zip] and upload to overleaf. From there, add your solution to the appropriate .tex file for the problem assigned. Modify week2.tex to comment out \usepackage{toc} and instead be \usepackage[response#]{toc} where # refers to the number of the problem assigned.

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:

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)