Lesson 1

# Intro to Theoretical Computer Science

Course

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

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

Last Updated March 7, 2022

## Course Lessons

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.

Get help from subject matter experts

Learn industry best practices

Gain valuable insights and improve your skills

## Get Started Today

Intro to Theoretical Computer Science

## Month-To-Month

- Unlimited access to our learning catalog
- Always-on learning assistant
- Personalized project reviews
- Program certificates
- Learner community

## 4 Months

- All the same great benefits in our month-to-month plan
- Most cost-effective way to acquire a new set of skills