This is a core undergraduate computer science course on the foundations of computing. The questions it aims to answer are: (1) What is computation? (2) What is computable? (3) What is computable given our limited resources?
We'll answer these questions and, in the process, explore important concepts such as Turing machines, languages, reductions, and NP-completeness. Welcome to the tree-mendous world of theoretical computer science, and we hope you'll join us in exploring it!
The first midterm will be in class on Thursday, October 19. The second midterm will be take-home. It will be released on Thursday, November 9, and will be due on Thursday, November 16. The final will be at 2PM on Thursday, December 14.