CS103: Mathematical Foundations of Computing

🗺️ Your Week 9 Task Map

⏰ Important Dates and Deadlines

• (Tue 3/4, 1:00 PM) Deadline to invoke the Regret Clause for Problem Set 7.
• (Fri 3/7, 1:00 PM) Deadline for Problem Set 8.
• (Mon 3/10, 11:59 PM) Deadline for Midterm 2 regrade requests.

⭐ Starred Readings
These readings will be posted Friday, 3/7

In a rare move, I am listing both of the guides that unlock this week as starred readings. They're lengthy, but as the final exam approaches, these can help shore up your understanding of this material in a way that could significantly boost your performance on the final exam (in addition to helping with PS9). Please consider setting aside time to at least skim through these guides.

• The Guide to the Lava Diagram talks about determining where on the Lava Diagram certain languages fall. This is a key learning outcome for the course and is non-trivial, but this amazing guide by Keith Schwarz offers some super helpful insights and tips on how to approach Lava Diagram questions. It will help you solidify your understanding of (and inutitions for!) the distinctions between REG, CFL, R, RE, and the languages that fall outside of RE. It will offer additional context for the Lava Diagram, and it'll leave you in great shape for any Lava Diagram questions that might appear on the final exam.

• The Guide to Self-Reference talks about how to execute self-reference proofs that show the limits of computation. This is a tricky (pun intended) technique when you first see it. If you have any uncertainty about how these proofs work, or if you just want to see additional examples that have been carefully and thoughtfully explained, check out this amazing guide created by Keith Schwarz.

📰 Other Updates

• Because the TA team devoted so much time to grading Midterm 2 this weekend, we need some extra time to get last week's problem set graded. We anticipate having PS7 graded this Friday, Mar. 7.

Course Overview and Welcome

Hi there 👋, and welcome to CS103: Mathematical Foundations of Computing! This class is an introduction to discrete mathematics (mathematical logic, proofs, and discrete structures such as sets, functions, and graphs), computability theory, and complexity theory. Over the course of the quarter, you’ll see some of the most impressive – and intellectually beautiful – mathematical results of the last 150 years. As we go, you’ll hone your ability to write clean, elegant, well-structured proofs. You’ll untangle interesting puzzles and encounter surprising mathematical results. In the latter half of the course, you’ll learn how to think about computation itself, how to show that certain problems are impossible to solve, and you’ll get a sense of what lies beyond the current frontier of computer science – especially with respect to the biggest open problem in math and computer science, the P = NP problem.

We’re excited to share our love of this material with you, and we have a superb team of TAs who will support you on your journey through this course. We hope you will ultimately find the class enriching and fulfilling and that you enjoy the fascinating topics we discuss along the way!

Teaching Team