École normale supérieure

Free Approximation Algorithms Part I

This course focuses on algorithms & data structures, using Approximation Algorithms Part I as its central topic. It is delivered in English through Coursera.

Approximation Algorithms Part I — free course from École normale supérieure
Free learning access

The provider’s published access terms were checked on 16 November 2026 and identify the learning content as free. This listing does not rely on a paid subscription trial or a preview of only the first lesson. A provider account may be required; availability can change.

About this course

This course focuses on algorithms & data structures, using Approximation Algorithms Part I as its central topic. It is delivered in English through Coursera.

Work through the material in the order suggested by the provider. The listed duration is a guide; the time you need will depend on your starting knowledge and how much independent practice you add.

Official title Approximation Algorithms Part I
Provider École normale supérieure
Learning platform Coursera
Format Course
Language English
Level Professional (editorial estimate)
Listed duration Self-paced
Certificate No certificate or academic credit is awarded.

Topics in the published syllabus

  • Vertex cover and Linear Programming
  • Knapsack and Rounding
  • Bin Packing, Linear Programming and Rounding
  • Set Cover and Randomized Rounding

These are selected syllabus headings. The enrollment page contains the complete sequence and any prerequisites.

Build a small example you can explain

Recreate one manageable example in a practice environment, then change a single input or requirement. Observe what changes and explain why. Keep a note of the tool versions and any error messages so that your learning is reproducible.

Enroll Now ↗

Some enrollment links may be affiliate links. Coursya may receive a commission if you make a qualifying purchase, at no extra cost to you.

Related courses for your next step

Frequently asked questions

Is the complete learning content free?

The provider’s published access terms were checked on 16 November 2026 and identify the learning content as free. This listing does not rely on a paid subscription trial or a preview of only the first lesson. A provider account may be required; availability can change.

Does the course include a certificate?

No certificate or academic credit is awarded.

What should I check before enrolling?

Check the language, prerequisites and current access terms on the provider page. Use the free learning option described above. If the provider has changed its offer or only shows a paid option, do not assume that a trial is the same as free course access.

Share this course

Questions & discussion

Share a useful question or correction. Comments appear after moderation. Please avoid personal or sensitive information.

  1. This class is the one I am seeking for a long time. Theories of Combinatorial optimization and associated approximation algorithms involve lots of hot research topics in machine learning, image processing, and Bioinformatics. The faculty for this course is a leading expert in the related fields.

  2. The course deals not with programming, but rather with designing and analyzing approximation algorithms. The course is on a high level and focuses on the subject without too much side remarks on applications, connections to other subjects or motivational introductions. If you are a theory person, however, you will probably enjoyed it.

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

  4. Really good course, the material is quite advanced but very well structured and introduced in a very simple way. The assignments were a lot of fun: really enjoyed the peer-graded assignments where I needed to write short proofs, much more useful than regular multiple-choice answers. Looking forward to the next course!

  5. Excellent Course! I have learnt a lot about Approximation Algorithms in a short span of time.

  6. Excellent advanced course! Not for beginner in computer science, nor for people more interested in applying computer science than in theoretical foundations.

  7. This was a relatively easy but well paced introduction to approximation algorithms. I totally enjoyed it.

  8. The assignments could be a bit improved (some are less good, I would personally complain about knapsack), but in general it is a great course, as it gives an accessible introduction to approximation algorithms (for NP-hard problems), which is a very relevant topic, as NP-hard problems are everywhere.
    At the time of writing (end summer 2016), it is also a unique course for this very relevant topic.

  9. I love how this course delves into a very promising advanced research topic in Computational Complexity. It helps me a lot to understand trending publications in the area. Specially that the material is presented in an incremental approach. This way a researcher can live through the evolution of ideas. It is inspiring also in the way one comes up with a partial solution for the special case, and then generalizes with approximation factor that is satisfyingly good. I’m looking forward to more advanced courses in parameterized, streaming or quantum algorithms.

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

  11. I am a researcher and (in past) an instructor in SDP, Randomized and Approximation Algorithms.
    There are a few instances, where things are not explained as well as an advanced UG or a starting Grad student would like, e.g., Knapsack got a bit delirious somewhere in between (the “special special” case, which IMHO was not needed.)
    Otherwise, I love Claire’s enthusiasm, and the joy she finds in delivering the ideas. She is succinct everywhere (to me).

  12. A great course if you want to learn about approximation algorithms from the point of view of linear programming relaxation!

Add to the discussion

Your email address will not be published. Required fields are marked *