Monthly Subscription Starting at AED 99 + VAT

Approximation Algorithms
  • Level Professional
  • Duration 15 hours
  • Course by EIT Digital
  • Offered by

About

Many real-world algorithmic problems cannot be solved efficiently using traditional algorithmic tools, for example because the problems are NP-hard. The goal of this course is to become familiar with important algorithmic concepts and techniques needed to effectively deal with such problems. These techniques apply when we don't require the optimal solution to certain problems, but an approximation that is close to the optimal solution. We will see how to efficiently find such approximations. Prerequisites: In order to successfully take this course, you should already have a basic knowledge of algorithms and mathematics. Here's a short list of what you are supposed to know: - O-notation, Ω-notation, Θ-notation; how to analyze algorithms - Basic calculus: manipulating summations, solving recurrences, working with logarithms, etc. - Basic probability theory: events, probability distributions, random variables, expected values etc. - Basic data structures: linked lists, stacks, queues, heaps - (Balanced) binary search trees - Basic sorting algorithms, for example MergeSort, InsertionSort, QuickSort - Graph terminology, representations of graphs (adjacency lists and adjacency matrix), basic graph algorithms (BFS, DFS, topological sort, shortest paths) The material for this course is based on the course notes that can be found under the resources tab. We will not cover everything from the course notes. The course notes are there both for students who did not fully understand the lectures as well as for students who would like to dive deeper into the topics. The video lectures contain a few very minor mistakes. A list of these mistakes can be found under resources (in the document called "Errata"). If you think you found an error, report a problem by clicking the square flag at the bottom of the lecture or quiz where you found the error.

Modules

1.1 Introduction

    • 1 Videos
    • 1 Readings
Show info about module content

1 Videos

  • Introduction to Approximation Algorithms

1 Readings

  • Course notes 1.1

Quiz: Introduction

    • 1 Assignment
Show info about module content

1 Assignment

  • Introduction

2.1 A greedy algorithm for load balancing

    • 1 Videos
Show info about module content

1 Videos

  • A greedy algorithm for load balancing

2.2 Analysis of the greedy-algorithm

    • 1 Videos
Show info about module content

1 Videos

  • Analysis of the greedy-algorithm

2.3 The ordered scheduling-algorithm

    • 1 Videos
Show info about module content

1 Videos

  • The ordered scheduling algorithm

2.4 Quiz: The load balancing problem

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

1 Programming

  • Load balancing

1 Assignment

  • The load balancing problem

1 Readings

  • Course notes 1.2

3.1 The vertex cover problem

    • 1 Videos
Show info about module content

1 Videos

  • The vertex-cover problem

3.2 An approximation algorithm for vertex-cover

    • 1 Videos
    • 1 Readings
Show info about module content

1 Videos

  • An approximation algorithm for vertex-cover

1 Readings

  • Course notes 3.1

3.3 A brief introduction to linear programming

    • 1 Videos
Show info about module content

1 Videos

  • A brief introduction to linear programming

3.4 Weighted vertex-cover

    • 1 Videos
Show info about module content

1 Videos

  • Weighted vertex-cover

3.5 LP relaxation for weighted vertex-cover

    • 1 Videos
Show info about module content

1 Videos

  • LP relaxation for weighted vertex-cover

3.6 LP relaxation: Analyzing approximation ratio

    • 1 Videos
    • 1 Readings
Show info about module content

1 Videos

  • LP relaxation: Analyzing approximation ratio

1 Readings

  • Course notes 3.2

3.7 Quiz: LP relaxation

    • 1 Assignment
Show info about module content

1 Assignment

  • LP Relaxation

4.1 Polynomial-time approximation schemes

    • 1 Videos
Show info about module content

1 Videos

  • Polynomial-time approximation schemes

4.2 Knapsack Problem

    • 1 Videos
Show info about module content

1 Videos

  • Knapsack Problem

4.3 A dynamic programming algorithm for knapsack

    • 1 Videos
    • 1 Readings
Show info about module content

1 Videos

  • A dynamic-programming algorithm for knapsack

1 Readings

  • Course notes 4.1

4.4 A PTAS for knapsack

    • 1 Videos
Show info about module content

1 Videos

  • A PTAS for knapsack

4.5 Analysis of the PTAS for knapsack: approximation ratio

    • 1 Videos
Show info about module content

1 Videos

  • Analysis of the PTAS for knapsack: approximation ratio

4.6 Analysis of the PTAS for knapsack: running time

    • 1 Videos
    • 1 Readings
Show info about module content

1 Videos

  • Analysis of the PTAS for knapsack: running time

1 Readings

  • Course notes 4.2

4.7 Quiz: Polynomial-time approximation schemes

    • 1 Programming
    • 1 Assignment
Show info about module content

1 Programming

  • PTAS for load balancing

1 Assignment

  • Polynomial-time approximation schemes

Auto Summary

"Approximation Algorithms" is an advanced course designed for professionals in Data Science & AI, taught by Coursera. It focuses on solving NP-hard problems using algorithmic techniques to find near-optimal solutions efficiently. Learners need a solid foundation in algorithms, mathematics, data structures, and graph theory. The course includes comprehensive video lectures and detailed course notes, spanning 900 minutes. Available under the Starter subscription, it's ideal for those looking to deepen their expertise in algorithmic problem-solving.

Mark de Berg
Instructor

Mark de Berg