Learn the basic concepts in theoretical computer science. Discover what they imply for solving tough computational challenges.
Overview
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
Taught by
Sebastian Wernicke
Related Courses
Related Articles
-
13 Best Data Structures & Algorithms Courses for 2026
-
[2026] 140+ Universities Just Launched 900+ Online Courses. Here’s the Full List.
-
Harvard CS50 in 2026: How to Get a Free Certificate
-
[2026] 1000+ Free Computer Science Courses from World’s Top Universities
-
10 Best CSS Animation Courses for 2026: Bring HTML to Life
-
[2026] Harvard CS50 Guide: How to Pick the Right Course (with Free Certificate)
Reviews
3.0 rating, based on 2 Class Central reviews
4.7 rating at Udacity based on 3 ratings
-
A good introduction to computational complexity, with some subtle theoretical concepts presented in a clear and amenable way. Stressing the importance of good theoretical foundations and the analysis of algorithms.
-
Pacing of this course is all off. If you're gonna be doing this be prepared for a lot of frustrated evenings and hair-pulling frustration trying to get a grasp on what the lecturer is even trying to tell you.
