About this Course

25,487 recent views
Shareable Certificate
Earn a Certificate upon completion
100% online
Start instantly and learn at your own schedule.
Flexible deadlines
Reset deadlines in accordance to your schedule.
Intermediate Level
Approx. 15 hours to complete
English
Subtitles: English
Shareable Certificate
Earn a Certificate upon completion
100% online
Start instantly and learn at your own schedule.
Flexible deadlines
Reset deadlines in accordance to your schedule.
Intermediate Level
Approx. 15 hours to complete
English
Subtitles: English

Offered by

Placeholder

EIT Digital

Syllabus - What you will learn from this course

Week
1

Week 1

1 hour to complete

Introduction to Approximation algorithms

1 hour to complete
1 video (Total 13 min), 1 reading, 1 quiz
1 reading
Course notes 1.130m
1 practice exercise
Introduction20m
Week
2

Week 2

5 hours to complete

The Load Balancing problem

5 hours to complete
3 videos (Total 45 min), 1 reading, 2 quizzes
3 videos
Analysis of the greedy-algorithm19m
The ordered scheduling algorithm14m
1 reading
Course notes 1.245m
1 practice exercise
The load balancing problem25m
Week
3

Week 3

3 hours to complete

LP Relaxation

3 hours to complete
6 videos (Total 69 min), 2 readings, 1 quiz
6 videos
An approximation algorithm for vertex-cover11m
A brief introduction to linear programming12m
Weighted vertex-cover15m
LP relaxation for weighted vertex-cover7m
LP relaxation: Analyzing approximation ratio12m
2 readings
Course notes 3.120m
Course notes 3.245m
1 practice exercise
LP Relaxation30m
Week
4

Week 4

6 hours to complete

Polynomial-time approximation schemes

6 hours to complete
6 videos (Total 62 min), 2 readings, 2 quizzes
6 videos
Knapsack Problem6m
A dynamic-programming algorithm for knapsack16m
A PTAS for knapsack12m
Analysis of the PTAS for knapsack: approximation ratio11m
Analysis of the PTAS for knapsack: running time8m
2 readings
Course notes 4.145m
Course notes 4.245m
1 practice exercise
Polynomial-time approximation schemes45m

Frequently Asked Questions

More questions? Visit the Learner Help Center.