Free

Intro to Theoretical Computer Science

Course

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

Last Updated March 7, 2022

Prerequisites:

No experience required

Course Lessons

Lesson 1

Lesson 1.1 - Challenging Problems

Lesson 2

Lesson 1.2 - Algorithm Analysis and the RAM

Lesson 3

Lesson 1.3 - Big O (Optional)

Lesson 4

Lesson 1.4 - Connecting Similar Problems

Lesson 5

Problem Set 1

Lesson 6

Lesson 2.1 - Many Solutions and Intractability

Lesson 7

Lesson 2.2 - Non-deterministic RAM

Lesson 8

Lesson 2.3 - SAT

Lesson 9

Lesson 2.4 - Proof of SAT (Optional)

Lesson 10

Lesson 2.5 - NP-Completeness Via Reductions

Lesson 11

Problem Set 2

Lesson 12

Lesson 3 - Solving NP-Complete Problems

Lesson 13

Problem Set 3

Lesson 14

Lesson 4.1 - Pruning the Input

Lesson 15

Lessons 4.2 - Preprocessing

Lesson 16

Lesson 4.3 - Measuring Hardness

Lesson 17

Problem Set 4

Lesson 18

Lesson 5.1 - Approximation Factor

Lesson 19

Lesson 5.2 - Shortest Tour

Lesson 20

Lesson 5.3 - Reductions & Approx. Factors

Lesson 21

Lesson 5.4 - PTAS

Lesson 22

Problem Set 5

Lesson 23

Lesson 6.1 - Randomization

Lesson 24

Lesson 6.2 - What You've Learnt

Lesson 25

Problem Set 6

Lesson 26

Lesson 7.1 - Limits of Computation

Lesson 27

Lesson 7.2 - More Undecidability

Lesson 28

Problem Set 7

Lesson 29

Exam

Taught By The Best

Sebastian Wernicke

Instructor

Sean Bennett

Instructor

Sarah Norell

Instructor

The Udacity Difference

Combine technology training for employees with industry experts, mentors, and projects, for critical thinking that pushes innovation. Our proven upskilling system goes after success—relentlessly.

Demonstrate proficiency with practical projects

Projects are based on real-world scenarios and challenges, allowing you to apply the skills you learn to practical situations, while giving you real hands-on experience.

Gain proven experience
Retain knowledge longer
Apply new skills immediately

Top-tier services to ensure learner success

Reviewers provide timely and constructive feedback on your project submissions, highlighting areas of improvement and offering practical tips to enhance your work.