Monthly Subscription Starting at AED 99 + VAT

Approximation Algorithms Part I
  • Level Foundation
  • Duration 36 hours
  • Course by École normale supérieure
  • Offered by

About

Approximation algorithms, Part I How efficiently can you pack objects into a minimum number of boxes? How well can you cluster nodes so as to cheaply separate a network into components around a few centers? These are examples of NP-hard combinatorial optimization problems. It is most likely impossible to solve such problems efficiently, so our aim is to give an approximate solution that can be computed in polynomial time and that at the same time has provable guarantees on its cost relative to the optimum. This course assumes knowledge of a standard undergraduate Algorithms course, and particularly emphasizes algorithms that can be designed using linear programming, a favorite and amazingly successful technique in this area. By taking this course, you will be exposed to a range of problems at the foundations of theoretical computer science, and to powerful design and analysis techniques. Upon completion, you will be able to recognize, when faced with a new combinatorial optimization problem, whether it is close to one of a few known basic problems, and will be able to design linear programming relaxations and use randomized rounding to attempt to solve your own problem. The course content and in particular the homework is of a theoretical nature without any programming assignments. This is the first of a two-part course on Approximation Algorithms.

Modules

Introduction: a roadmap to this module and to this course

    • 1 Videos
    • 3 Readings
    • 1 Assignment
Show info about module content

1 Assignment

  • Quiz 1: P vs. NP review

1 Videos

  • Lecture: Introduction

3 Readings

  • Slides
  • All slides for all chapters of Approx Algs part 1
  • Attempt to upload slides in Keynote format

What is vertex cover? Some examples

    • 1 Videos
    • 1 Readings
    • 1 Assignment
Show info about module content

1 Assignment

  • Quiz 2

1 Videos

  • Lecture: Definition

1 Readings

  • Slides

An integer program for vertex cover

    • 1 Videos
    • 1 Readings
    • 1 Assignment
Show info about module content

1 Assignment

  • Quiz 3

1 Videos

  • Lecture: Integer program

1 Readings

  • Slides

Integer programming and linear programming

    • 1 Videos
    • 1 Readings
    • 1 Assignment
Show info about module content

1 Assignment

  • Quiz 4

1 Videos

  • Lecture: A linear programming relaxation

1 Readings

  • Slides

An approximation algorithm for vertex cover

    • 1 Videos
    • 1 Readings
    • 1 Assignment
Show info about module content

1 Assignment

  • Quiz 5

1 Videos

  • Lecture: Approximation algorithm

1 Readings

  • Slides

Analysis: how good is our algorithm ?

    • 1 Videos
    • 1 Readings
    • 1 Assignment
Show info about module content

1 Assignment

  • Quiz 6

1 Videos

  • Lecture: Analysis

1 Readings

  • Slides

General facts

    • 1 Videos
    • 1 Readings
    • 1 Assignment
Show info about module content

1 Assignment

  • Quiz 7

1 Videos

  • Lecture: General facts

1 Readings

  • Slides

Exercises

    • 1 Videos
    • 4 Readings
    • 1 PeerReview
Show info about module content

1 Peer Review

  • Peer Graded Assignment 1

1 Videos

  • Half integrality (7:35 bug, fixed in pdf slides)

4 Readings

  • Practice Exercises
  • PDF version of the peer-graded assignment
  • Half-integrality slides
  • All slides together in one file

The knapsack problem: Definition

    • 1 Videos
    • 1 Readings
    • 1 Assignment
Show info about module content

1 Assignment

  • Quiz 1

1 Videos

  • Lecture: Definition

1 Readings

  • Slides

Greedy algorithm

    • 1 Videos
    • 1 Readings
    • 1 Assignment
Show info about module content

1 Assignment

  • Quiz 2

1 Videos

  • Lecture: Greedy algorithm

1 Readings

  • Slides

Dynamic programming in special case

    • 1 Videos
    • 1 Readings
    • 1 Assignment
Show info about module content

1 Assignment

  • Quiz 3

1 Videos

  • Lecture: Special dynamic program

1 Readings

  • Slides

Dynamic programming in general

    • 1 Videos
    • 1 Readings
    • 1 Assignment
Show info about module content

1 Assignment

  • Quiz 4

1 Videos

  • Lecture: General dynamic program

1 Readings

  • Slides

Approximation algorithm

    • 1 Videos
    • 1 Readings
    • 1 Assignment
Show info about module content

1 Assignment

  • Quiz 5

1 Videos

  • Lecture: algorithm

1 Readings

  • Slides

Analysis

    • 1 Videos
    • 1 Readings
    • 1 Assignment
Show info about module content

1 Assignment

  • Quiz 6

1 Videos

  • Lecture: analysis

1 Readings

  • Slides

Approximation scheme

    • 1 Videos
    • 1 Readings
    • 1 Assignment
Show info about module content

1 Assignment

  • Quiz 7

1 Videos

  • Lecture: approximation scheme

1 Readings

  • Slides

Exercises

    • 2 Readings
    • 1 PeerReview
Show info about module content

1 Peer Review

  • Peer Assignment Knapsack

2 Readings

  • Practise Exercises
  • All slides together in one file

The Next-Fit algorithm

    • 1 Videos
    • 1 Readings
    • 1 Assignment
Show info about module content

1 Assignment

  • Quiz 1

1 Videos

  • Lecture: Next Fit

1 Readings

  • Slides (with typo corrected)

A linear program for Bin-Packing

    • 1 Videos
    • 1 Readings
    • 1 Assignment
Show info about module content

1 Assignment

  • Quiz 2

1 Videos

  • Lecture: a linear program

1 Readings

  • Slides

Small items

    • 1 Videos
    • 1 Readings
    • 1 Assignment
Show info about module content

1 Assignment

  • Quiz 3

1 Videos

  • Lecture: small items

1 Readings

  • Slides

Large items, few sizes

    • 1 Videos
    • 1 Readings
    • 1 Assignment
Show info about module content

1 Assignment

  • Quiz 4

1 Videos

  • Lecture: large items, few sizes

1 Readings

  • Slides

Large items, many sizes

    • 1 Videos
    • 1 Readings
    • 1 Assignment
Show info about module content

1 Assignment

  • Quiz 5

1 Videos

  • Large items, many sizes

1 Readings

  • Slides

Large items, analysis

    • 1 Videos
    • 1 Readings
    • 1 Assignment
Show info about module content

1 Assignment

  • Quiz 6

1 Videos

  • Lecture: large items analysis

1 Readings

  • Slides

General algorithm

    • 1 Videos
    • 1 Readings
    • 1 Assignment
Show info about module content

1 Assignment

  • Quiz 7

1 Videos

  • Lecture: general algorithm

1 Readings

  • Slides

Bin packing: conclusion

    • 1 Videos
    • 1 Readings
Show info about module content

1 Videos

  • Lecture: conclusion

1 Readings

  • Slides

Exercises

    • 2 Readings
    • 1 PeerReview
Show info about module content

1 Peer Review

  • Peer Assignment: Bin-Packing

2 Readings

  • Practice Exercises
  • All slides together in one file

Set Cover Definition

    • 1 Videos
    • 1 Readings
    • 1 Assignment
Show info about module content

1 Assignment

  • Quiz 1

1 Videos

  • Lecture: definition

1 Readings

  • Slides

Randomized Rounding

    • 1 Videos
    • 1 Readings
    • 1 Assignment
Show info about module content

1 Assignment

  • Quiz 2

1 Videos

  • Lecture: randomized rounding

1 Readings

  • Slides

Cost Analysis

    • 1 Videos
    • 1 Readings
    • 1 Assignment
Show info about module content

1 Assignment

  • Quiz 3

1 Videos

  • Lecture: cost analysis

1 Readings

  • Slides

Coverage Analysis

    • 1 Videos
    • 1 Readings
    • 1 Assignment
Show info about module content

1 Assignment

  • Quiz 4

1 Videos

  • Lecture: coverage analysis

1 Readings

  • Slides

Iterated Algorithm

    • 1 Videos
    • 1 Readings
    • 1 Assignment
Show info about module content

1 Assignment

  • Quiz 5

1 Videos

  • Lecture: iterated algorithm

1 Readings

  • Slides

Stopping Time Algorithm

    • 1 Videos
    • 1 Readings
    • 1 Assignment
Show info about module content

1 Assignment

  • Quiz 6

1 Videos

  • Lecture: stopping time algorithm

1 Readings

  • Slides

Stopping Time Analysis

    • 1 Videos
    • 1 Readings
    • 1 Assignment
Show info about module content

1 Assignment

  • Quiz 7

1 Videos

  • Lecture: stopping time analysis

1 Readings

  • Slides

Remarks

    • 1 Videos
    • 2 Readings
    • 1 Assignment
Show info about module content

1 Assignment

  • Quiz 8

1 Videos

  • Lecture:final remarks

2 Readings

  • Slides
  • A reference on this stopping time analysis

Exerices

    • 2 Readings
    • 1 PeerReview
Show info about module content

1 Peer Review

  • Peer Assig Set Cover

2 Readings

  • Practise Exercise
  • All slides together in one file

What is the Multiway Cut problem?

    • 1 Videos
    • 1 Readings
    • 1 Assignment
Show info about module content

1 Assignment

  • Quiz 1 : Some context on cuts

1 Videos

  • Lecture: definition

1 Readings

  • Slides

A linear programming relaxation

    • 1 Videos
    • 1 Readings
    • 1 Assignment
Show info about module content

1 Assignment

  • Quiz 2

1 Videos

  • Lecture: linear programming relaxation

1 Readings

  • Slides

Randomized rounding

    • 1 Videos
    • 1 Readings
    • 1 Assignment
Show info about module content

1 Assignment

  • Quiz 3

1 Videos

  • Lecture: randomized rounding

1 Readings

  • Slides

Analysis

    • 1 Videos
    • 1 Readings
    • 1 Assignment
Show info about module content

1 Assignment

  • Quiz 4

1 Videos

  • Lecture: analysis

1 Readings

  • Slides

Conclusion

    • 1 Videos
    • 1 Readings
    • 1 Assignment
Show info about module content

1 Assignment

  • Quiz 5

1 Videos

  • Lecture: conclusion

1 Readings

  • Slides

Exercises

    • 3 Readings
    • 1 PeerReview
Show info about module content

1 Peer Review

  • Peer-graded assignment 5

3 Readings

  • Practice exercise
  • All Chapter Slides together in one file
  • Slides for all chapters of Approx Algs Part 1 together in one file

Auto Summary

Explore the fascinating world of Approximation Algorithms with this foundational course in Data Science & AI, led by expert instructors on Coursera. Dive into NP-hard combinatorial optimization problems, learning to craft efficient approximate solutions using linear programming and randomized rounding techniques. With a focus on theoretical computer science, this course spans 2160 minutes and requires prior knowledge of undergraduate algorithms. Ideal for learners aiming to tackle complex optimization challenges, subscription options include Starter and Professional tiers. Join now to enhance your problem-solving skills and computational theory expertise.

Claire Mathieu
Instructor

Claire Mathieu