Congratulations on finishing this course! We hope that throughout this semester CS170 was able to give you a sense about algorithmic thinking and analysis. As we finalize the grades, please take some time to relax and congratulate yourself for completing this course. We know that this semester was challenging and we know that your hard work will pay off!

If you’re wondering on where you can go after taking this class, we have a couple of suggestions!

Note: many of the graduate classes are not offered regularly, especially the special topics ones.

Will build off from the complexity part of 170 and introduce you to the heart of theory of computation. In this course, you will learn about different computation models, finite automata and of course, more complexity theory. If you enjoyed the complexity part of the course, we surely recommend you to give it a try, especially considering that it hasn’t been offered in a long time. Offered next semester.

Builds off from basic probability covered in 70 and analysis skills in 170. In this class, you will learn about how we generate randomness in theory and how we exploit its power when dealing with NP-hardness. If you enjoyed probability, especially the probabilistic analysis we saw in special topics this year, this would be a good class for you. Offered next semester.

This is the most natural extension of 170, and a must-take class if you want to learn more about combinatorial algorithms. Offered next semester.

You may have noticed that in 170, we didn't really cover many randomized algorithms outside of primality testing and streaming. For example, we never discussed quicksort, which is a very popular sorting algorithm that is randomized. Like CS 270, this is a must-take class if you want to learn more about algorithms. Last offered Spring 2018.

This class is about cryptography, so things like public/private key encryption, one-way functions, pseudorandomness, etc. In this class, you will formally prove that these systems are secure under some complexity theory assumption (such as P ≠ NP) using reductions. If you liked the reductions part of the class, you will probably enjoy this class too! Last offered Fall 2018.

This class is about information theory, so it covers topics like entropy, mutual information, and the channel coding theorem. If you like probability and thought Huffman coding was cool, then take this class! Last offered Fall 2018.

A proof is a string that allows an efficient verifier to check the validity of an NP statement, e.g. that a 3-SAT formula is satisfiable. One can consider two different related notions of a proof. In a probabilistically checkable proof, the verifier is restricted to only reading a small number of bits from the proof, and in an interactive proof, the prover talks to the verifier to try to convince the verifier that the NP statement is true. Offered next semester.

Design of Approximation Algorithms

Approximation Algorithms

A Theoretician's Toolkit