Intro to Theoretical Computer Science

Overview

Learn the basic concepts in theoretical computer science. Discover what they imply for solving tough computational challenges.

Syllabus

• Lesson 1.1 - Challenging Problems
• Lesson 1.2 - Algorithm Analysis and the RAM
• Lesson 1.3 - Big O (Optional)
• Lesson 1.4 - Connecting Similar Problems
• Problem Set 1
• Lesson 2.1 - Many Solutions and Intractability
• Lesson 2.2 - Non-deterministic RAM
• Lesson 2.3 - SAT
• Lesson 2.4 - Proof of SAT (Optional)
• Lesson 2.5 - NP-Completeness Via Reductions
• Problem Set 2
• Lesson 3 - Solving NP-Complete Problems
• Problem Set 3
• Lesson 4.1 - Pruning the Input
• Lessons 4.2 - Preprocessing
• Lesson 4.3 - Measuring Hardness
• Problem Set 4
• Lesson 5.1 - Approximation Factor
• Lesson 5.2 - Shortest Tour
• Lesson 5.3 - Reductions & Approx. Factors
• Lesson 5.4 - PTAS
• Problem Set 5
• Lesson 6.1 - Randomization
• Lesson 6.2 - What You've Learnt
• Problem Set 6
• Lesson 7.1 - Limits of Computation
• Lesson 7.2 - More Undecidability
• Problem Set 7
• Exam

Instructors

• • Sebastian Wernicke
• • Sean Bennett
• • Sarah Norell