Class 4: Uncountability
What Cannot Be Represented by Bits? (Uncountable Sets) Schedule Reminders: Problem Set 1 is due this Friday (4:19pm). See the schedule for updated office hours. Slides (PDF) Video Here is 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) Its only a bit over 2 pages long, and its easy to see Cantor’s answer to the ``Is 0 a Natural Number?PS1 Posted
Problem Set 1: (Un)natural Numbers Problem Set 1 is available here: ps1.pdf (you will also need the ps1.zip file described in the PDF). It is due on Friday, 13 September at 4:19pm. In this assignment we’ll be working with constructive recursive definitions (mostly the definition of natural numbers discussed in lecture), and proofs by induction. Similarly to Problem Set 0, this assigned involves both pencil-and-paper problems (submitted as a PDF by editing the provided ps1.Class 3: Countable Sets
What Can Be Represented by Bits? Schedule Reminders: Problem Set 0 is due this Friday (4:19pm). See the schedule for updated office hours. Slides (PDF) Video Update (7 Sept): There is a correction on slide 10 to the way we defined addition for the Set-based Natural Numbers (thanks to Nijat Khanbabayev for pointing out the problem). Some of the material from today’s class (and what we will continue on Monday) is in the TCS Book, Chapter 2.Class 2: Defining Definitions
Schedule Reminders: Office hours start today! Full schedule (which will be updated) is posted here. The first office hours are tonight, 6:30-8pm, in Rice 442.
Is 0 a Natural Number?
The “Google dragon” image was drawn for this talk. You can find Sergey Brin’s resume here (note the high honors in Mathematics and (low) honors in Computer Science).
Office Hours Posted
Office hours have now been posted on the Course Schedule. These will be adjusted and likely some more office hours added over the next few weeks, but we wanted to have some posted now for help on Problem Set 0 as well the background material we are covering this week.
Course Pledge
To be in this class, students are expected to agree to the Course Pledge. The expectations there apply to everything connected with this class including all assignments, classes, and office hours. Before 2:59pm this Wednesday (Sept 4) you must read and agree to the contents of the Course Pledge, and submit this assignment (in collab) to acknowledge having done this. (It is not necessary to print and submit the pledge on paper or as a scanned PDF.PS0 Posted
Problem Set 0: Getting Started Hello students, Problem Set 0 is available here: ps0.pdf (you will also need the ps0.zip file described in the PDF). It is due on Friday, 6 September at 4:19pm. The goal of this assignment is to get you acquainted with the tools we will be using for future assignments this semester: LaTeX (and overleaf) and Jupyter notebooks (using Python). For this assignment you will be editing the ps0.Class 1: Introduction
Lecture 1: Course Introduction
Today we will be discussing course mechanics, course expectations, and the values of studying theory.
Course Registration Survey
Please complete the course registration survey by 4:19pm on Friday, August 30.
Syllabus
The course syllabus and pledge are now posted:
Syllabus (PDF)
Pledge