About this Course
9,765 recent views

100% online

Start instantly and learn at your own schedule.

Flexible deadlines

Reset deadlines in accordance to your schedule.

Approx. 22 hours to complete

Suggested: 4 hours/week...

English

Subtitles: English
User
Learners taking this Course are
  • Data Engineers
  • Data Scientists
  • Machine Learning Engineers
  • Software Engineers
  • Researchers
User
Learners taking this Course are
  • Data Engineers
  • Data Scientists
  • Machine Learning Engineers
  • Software Engineers
  • Researchers

100% online

Start instantly and learn at your own schedule.

Flexible deadlines

Reset deadlines in accordance to your schedule.

Approx. 22 hours to complete

Suggested: 4 hours/week...

English

Subtitles: English

Syllabus - What you will learn from this course

Week
1
6 hours to complete

Vertex cover and Linear Programming

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 review6m
Quiz 28m
Quiz 34m
Quiz 46m
Quiz 54m
Quiz 64m
Quiz 74m
Week
2
5 hours to complete

Knapsack and Rounding

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 12m
Quiz 22m
Quiz 34m
Quiz 42m
Quiz 52m
Quiz 62m
Quiz 72m
Week
3
5 hours to complete

Bin Packing, Linear Programming and Rounding

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 14m
Quiz 26m
Quiz 32m
Quiz 46m
Quiz 54m
Quiz 66m
Quiz 76m
Week
4
5 hours to complete

Set Cover and Randomized Rounding

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 12m
Quiz 22m
Quiz 32m
Quiz 44m
Quiz 52m
Quiz 62m
Quiz 72m
Quiz 84m
4.7
35 ReviewsChevron Right

Top reviews from Approximation Algorithms Part I

By DAJan 27th 2016

The course provides a high-level introduction to approximation algorithm. There is no programming assignments but it provides nice introduction to approximation algorithm.

By ZWSep 17th 2017

This course is awesome. Prof. managed to elaborate the problem and analysis clearly and homework is properly assigned.

Instructor

About École normale supérieure

L’École normale supérieure (ENS) est un établissement d'enseignement supérieur pour les études prédoctorales et doctorales (graduate school) et un haut lieu de la recherche française. L'ENS offre à 300 nouveaux étudiants et 200 doctorants chaque année une formation de haut niveau, largement pluridisciplinaire, des humanités et sciences sociales aux sciences dures. Régulièrement distinguée au niveau international, l'ENS a formé 10 médailles Fields et 13 prix Nobel....

Frequently Asked Questions

  • Once you enroll for a Certificate, you’ll have access to all videos, quizzes, and programming assignments (if applicable). Peer review assignments can only be submitted and reviewed once your session has begun. If you choose to explore the course without purchasing, you may not be able to access certain assignments.

More questions? Visit the Learner Help Center.