About this Course

6,401 recent views
100% online
Start instantly and learn at your own schedule.
Flexible deadlines
Reset deadlines in accordance to your schedule.
Approx. 36 hours to complete
English
100% online
Start instantly and learn at your own schedule.
Flexible deadlines
Reset deadlines in accordance to your schedule.
Approx. 36 hours to complete
English

Offered by

Placeholder

École normale supérieure

Syllabus - What you will learn from this course

Content RatingThumbs Up89%(1,477 ratings)Info
Week
1

Week 1

8 hours to complete

Vertex cover and Linear Programming

8 hours to complete
8 videos (Total 54 min), 13 readings, 8 quizzes
8 videos
Lecture: Definition4m
Lecture: Integer program6m
Lecture: A linear programming relaxation6m
Lecture: Approximation algorithm6m
Lecture: Analysis6m
Lecture: General facts5m
Half integrality (7:35 bug, fixed in pdf slides)10m
13 readings
Slides10m
All slides for all chapters of Approx Algs part 110m
Attempt to upload slides in Keynote format10m
Slides10m
Slides10m
Slides10m
Slides10m
Slides10m
Slides10m
Practice Exercises10m
PDF version of the peer-graded assignment10m
Half-integrality slides10m
All slides together in one file10m
7 practice exercises
Quiz 1: P vs. NP review30m
Quiz 230m
Quiz 330m
Quiz 430m
Quiz 530m
Quiz 630m
Quiz 730m
Week
2

Week 2

7 hours to complete

Knapsack and Rounding

7 hours to complete
7 videos (Total 52 min), 9 readings, 8 quizzes
7 videos
Lecture: Greedy algorithm5m
Lecture: Special dynamic program8m
Lecture: General dynamic program8m
Lecture: algorithm6m
Lecture: analysis7m
Lecture: approximation scheme4m
9 readings
Slides10m
Slides10m
Slides10m
Slides10m
Slides10m
Slides10m
Slides10m
Practise Exercises10m
All slides together in one file10m
7 practice exercises
Quiz 130m
Quiz 230m
Quiz 330m
Quiz 430m
Quiz 530m
Quiz 630m
Quiz 730m
Week
3

Week 3

7 hours to complete

Bin Packing, Linear Programming and Rounding

7 hours to complete
8 videos (Total 74 min), 10 readings, 8 quizzes
8 videos
Lecture: a linear program12m
Lecture: small items6m
Lecture: large items, few sizes11m
Large items, many sizes8m
Lecture: large items analysis8m
Lecture: general algorithm7m
Lecture: conclusion6m
10 readings
Slides (with typo corrected)10m
Slides10m
Slides10m
Slides10m
Slides10m
Slides10m
Slides10m
Slides10m
Practice Exercises10m
All slides together in one file10m
7 practice exercises
Quiz 130m
Quiz 230m
Quiz 330m
Quiz 430m
Quiz 530m
Quiz 630m
Quiz 730m
Week
4

Week 4

8 hours to complete

Set Cover and Randomized Rounding

8 hours to complete
8 videos (Total 58 min), 11 readings, 9 quizzes
8 videos
Lecture: randomized rounding4m
Lecture: cost analysis5m
Lecture: coverage analysis8m
Lecture: iterated algorithm4m
Lecture: stopping time algorithm4m
Lecture: stopping time analysis10m
Lecture:final remarks6m
11 readings
Slides10m
Slides10m
Slides10m
Slides10m
Slides10m
Slides10m
Slides10m
Slides10m
A reference on this stopping time analysis10m
Practise Exercise10m
All slides together in one file10m
8 practice exercises
Quiz 130m
Quiz 230m
Quiz 330m
Quiz 430m
Quiz 530m
Quiz 630m
Quiz 730m
Quiz 830m

Reviews

TOP REVIEWS FROM APPROXIMATION ALGORITHMS PART I

View all reviews

Frequently Asked Questions

More questions? Visit the Learner Help Center.