Welcome to this Theoretical Computer Science resource page!

(Sorry about the audio on this video!)

Navigating this site

You will find additional resources related to the topic of theoretical CS that I hope will help in solidifying your understanding of the material. I’ve organized each page to contain notes, exercises and recordings I think might be useful if you’re looking to deepen your understanding.

[NEW]: You might also be interested in this archived webpage of the Theory of Computation course I taught at McGill in Fall 2023. Lecture notes and lecture recordings are available for most of the lectures I gave. Assignments for you to practice are also available there.

Some thoughts about this topic

Some of the concepts that you will learn here will be very different from anything you’ve seen before. As such, it will require time and practice to fully digest. It will be absolutely normal to feel lost after a lecture. However, once any kind of confusion or doubt appears, it is important you immediately address it with your instructor, the TAs or even fellow classmates. In fact, I have found study groups to be one of the most insightful and rewarding ways of ironing out any conceptual doubts in this course. My tip is to take the lecture as a mere introduction/warm-up to the material. You can only get more familiar with it by reviewing it, asking (easy and hard) questions along the way, and, most crucially, solving problems!

In teaching this material over the last few years, I have noticed that students take in concepts at very different paces. This means that some of you will have no problem solving assignment questions easily, with not much practice. Others will struggle more. For those of you in the latter group (which I wholeheartedly admit I was a part of), do not despair! Remember that you’re not alone in this journey.

In my opinion, the topics you will come across in a theory of computation course are some of the most fun and rewarding ones you’ll see in computer science. I hope this has gotten you pumped and ready to learn!

Recognition

I want to thank Tianyi Liu who was an excellent TA I had the chance of working with while I TAed a version of this course at Concordia and with whom I developed some of this content. I also want to thank Prof. Shiri who helped us in reviewing the content of the tutorials. Finally, I also want to thank Prof. Panangaden for taking a chance and hiring me as a TA for a similar version of this course at McGill.