Problem Set Nine goes out today and is due on Friday, March 15 at 12:50PM. This problem explores P and NP and concludes with a wrap-up of all the complexity and computability classes we've covered in this course.

You may use a late day on this assignment if you would like. If so, it is due immediately after you take the final exam. Due to university policy, we cannot accept any submissions received after 11:30AM.

Good luck!

Problem Set Eight goes out today and is due on Monday, March 11 at 12:50PM. This problem explores unsolvable problems and the limits of what computers can do. It concludes with an exploration of why languages like A_TM and L_D matter in the real world, and I hope that this forms a satisfying coda to our treatment of computability.

Good luck!

Problem Set Seven goes out today and is due on Monday, March 4 at 12:50PM. This problem set explores the RE and R languages and the limits of Turing machines. This will be your first experience probing the limits of what problems can be solved by computers, and I hope you find it exciting!

Good luck!

Anna Saplitski found an awesome video describing how self-assembling molecules can simulate Turing machines. This incredible video details the amazing connection between computational processes, emergent behavior, and how complex objects can be built from smaller pieces. I highly recommend it!

Problem Set Six goes out today and is due on Monday, February 25 at 12:50PM. It explores context-free languages, their representations, their properties, and their limits.

Good luck!

Julius will be holding an online review session on Saturday from 7PM-10PM. We will send out the Google hangout link when the time approaches.

Maurizio will be holding an in-person review session on Sunday, Feb. 10 from 5PM-7PM in Hewlett 200.

Problem Set Five went out today and is due next Friday, February 15 at the start of class. This problem set explores regular languages, their representations, and their limits. This will be your first foray into computability theory, and I hope that you find it fun and exciting!

We have two online tools you can use in this course of this problem set, both of which are linked under the "Resources" section of this page. Our DFA/NFA developer is a full development environment in which you can design, build, test, and debug finite automata. The regular expression developer will let you build regular expressions and test them on a variety of different inputs.

Good luck!

We have posted a second practice midterm exam you can use to help prepare for the upcoming midterm. Solutions to the first practice midterm are also available.

The CS103 midterm is next Tuesday, February 12 from 7PM - 10PM, location to be announced soon. It is open-book, open-note, open-computer, but closed-network, so it's totally fine to bring your laptop with you to the exam.

We have posted a practice midterm exam. This was the exam given in fall quarter, so its content, form, and structure should be similar to that of the real exam. We will release solutions on Wednesday.

Problem Set Four went out today. The checkpoint assignment is due next Monday, February 4 at 12:50PM and the remaining problems are due next Friday, February 8 at the start of class. This problem set explores properties of propositional and first-order logic, as well as the power of SAT solving algorithms.

Good luck!

Problem Set Three went out today. The checkpoint assignment is due next Monday, January 28 at 12:50PM and the remaining problems are due next Friday, February 1 at the start of class. This problem set explores relations, functions, cardinality, and the pigeonhole principle. After completing it, you'll have a much stronger understanding of discrete structures.

Good luck!

Problem Set Two went out today. The checkpoint assignment is due next Tuesday, January 22 at 5:00PM and the remaining problems are due next Friday, January 25 at the start of class. This problem set is all about induction and its applications in computer science. By the time you're done, you'll have a much deeper understanding of just how versatile induction can be.

Good luck!

There is a positively fascinating essay on the division algorithm, its proof, and why it's mathematically so important. I highly recommend giving it a read. It's available online if you are interested in reading through it.

An interesting consequence of proof by contradiction is that starting with a false statement, it's possible to prove anything.

Here is a fun proof online that uses the incorrect assumption that 1 = 0 to prove that Winston Churchill is a carrot. If you have the time to read over it, it's quite entertaining.

Problem Set One went out today. The checkpoint assignment is due next Monday, January 14 at the start of class and the remaining problems are due next Friday, January 18 at the start of class. This problem set is designed to get you used to writing mathematical proofs and to get you thinking about set theory, the integers, and even a bit of cryptography!

Good luck!

Here is Vi Hart's video about Pythagoras and √2. Enjoy!

Welcome to CS103, an exciting and fast-paced introduction to discrete mathematics, computability theory, and complexity theory! We have an great quarter ahead of us filled with interesting and exciting results in the power and limits of computation, and I hope that you're able to join us.

If you have any questions in the meantime, feel free to email me at htiek@cs.stanford.edu with questions.

See you soon!