Coursera

Approximation Algorithms Part II (Coursera)

Offered by École normale supérieure,

This is the continuation of Approximation algorithms, Part 1. Here you will learn linear programming duality applied to the design of some approximation algorithms, and semidefinite programming applied to Maxcut. By taking the two parts of 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.

Class Deals by MOOC List - Click here and see Coursera's Active Discounts, Deals, and Promo Codes.

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 second of a two-part course on Approximation Algorithms, this is the continuation of Approximation algorithms, Part 1

Syllabus

WEEK 1
Linear Programming Duality
This module does not study any specific combinatorial optimization problem. Instead, it introduces a central feature of linear programming, duality.

WEEK 2
Steiner Forest and Primal-Dual Approximation Algorithms
This module uses linear programming duality to design an algorithm for another basic problem, the Steiner forest problem.

WEEK 3
Facility Location and Primal-Dual Approximation Algorithms
This module continues teaching algorithmic applications of linear programming duality by applying it to another basic problem, the facility location problem.

WEEK 4
Maximum Cut and Semi-Definite Programming
We introduce a generalization of linear programming, semi-definite programming.This module uses semi-definite programming to design an approximation algorithm for another basic problem, the maximum cut problem.

Go to Class

MOOC List is learner-supported. When you buy through links on our site, we may earn an affiliate commission.

Related Courses

Coursera

Johns Hopkins University

Practical Machine Learning (Coursera)

Statistics & Data Analysis Data Science

One of the most common tasks performed by data scientists and data analysts are prediction and machine learning. This course will cover the basic components of building and applying prediction functions with an emphasis on practical applications. The course will provide basic grounding in concepts such as training and tests sets, overfitting, and error rates.

Jun 8th 2026

4 Weeks

Algorithms Machine Learning Regression

Coursera

University of California, San Diego,Higher School of Economics - HSE University

Advanced Algorithms and Complexity (Coursera)

CS: Software Engineering CS: Theory

You've learned the basic algorithms now and are ready to step into the area of more complex problems and algorithms to solve them. Advanced algorithms build upon basic ones and use new ideas. We will start with networks flows which are used in more typical applications such as optimal matchings, finding disjoint paths and flight scheduling as well as more surprising ones like image segmentation in computer vision.

Jun 8th 2026

5-12 Weeks

Algorithms Data Structures Machine Learning

Coursera

University of California, San Diego

Data Structures and Performance (Coursera)

CS: Theory Data Science

How do Java programs deal with vast quantities of data? Many of the data structures and algorithms that work with introductory toy examples break when applications process real, large data sets. Efficiency is critical, but how do we achieve it, and how do we even measure it? This is an intermediate Java course. We recommend this course to learners who have previous experience in software development or a background in computer science, and in particular, we recommend that you have taken the first course in this specialization (which also requires some previous experience with Java).

Jun 8th 2026

5-12 Weeks

Programming Java Algorithms

Coursera

Universitat Autònoma de Barcelona

Sistemas Digitales: De las puertas lógicas al procesador (Coursera)

CS: Theory Engineering

En este curso aprenderemos los fundamentos del diseño de los circuitos digitales actuales, siguiendo una orientación eminentemente práctica. A diferencia de otros cursos más "clásicos" de Circuitos Digitales, nuestro interés se centrará más en el Sistema que en la Electrónica que lo sustenta. Este enfoque nos permitirá sentar las bases del diseño de Sistemas Digitales complejos.

Jun 8th 2026

5-12 Weeks

Algorithms Engineering Digital Systems

Coursera

The State University of New York

International Cyber Conflicts (Coursera)

Security & Networking

By nature, cyber conflicts are an international issue that span across nation-state borders. By the end of the course, you will be able to apply the knowledge gained for analysis and management of international cyber incidents and conflicts including for activities such as development of policy related to cybercrime and cyberwarfare. Management of cyber incidents and conflicts requires an interdisciplinary perspective including an understanding of: 1) characteristics of the cyber threats and conflicts themselves, 2) international efforts to reduce and improve cyber security, and 3) psychological and sociopolitical factors.

Jun 8th 2026

5-12 Weeks

Networks Cybercrime Computer Science

Coursera

University of California, San Diego

Machine Learning With Big Data (Coursera)

Statistics & Data Analysis Data Science

Want to make sense of the volumes of data you have collected? Need to incorporate data-driven decisions into your process? This course provides an overview of machine learning techniques to explore, analyze, and leverage data. You will be introduced to tools and algorithms you can use to create machine learning models that learn from data, and to scale those models up to big data problems.

Jun 8th 2026

5-12 Weeks

Algorithms Machine Learning Big Data

Coursera

École Polytechnique Fédérale de Lausanne

Parallel programming (Coursera)

CS: Software Engineering CS: Programming

With every smartphone and computer now boasting multiple processors, the use of functional ideas to facilitate parallel programming is becoming increasingly widespread. In this course, you'll learn the fundamentals of parallel programming, from task parallelism to data parallelism. In particular, you'll see how many familiar ideas from functional programming map perfectly to to the data parallel paradigm.

Jun 8th 2026

4 Weeks

Algorithms Data Structures Parallel Computing

Coursera

University of California, San Diego,Higher School of Economics - HSE University

Algorithmic Toolbox (Coursera)

CS: Software Engineering CS: Theory

The course covers basic algorithmic techniques and ideas for computational problems arising frequently in practical applications: sorting and searching, divide and conquer, greedy algorithms, dynamic programming. We will learn a lot of theory: how to sort data and how it helps for searching; how to break a large problem into pieces and solve them recursively; when it makes sense to proceed greedily; how dynamic programming is used in genomic studies. You will practice solving computational problems, designing new algorithms, and implementing solutions efficiently (so that they run in less than a second).

Jun 8th 2026

5-12 Weeks

Algorithms Debugging Data Structures

Coursera

University of Illinois at Urbana-Champaign

Unordered Data Structures (Coursera)

CS: Software Engineering Computer Science

The Unordered Data Structures course covers the data structures and algorithms needed to implement hash tables, disjoint sets and graphs. These fundamental data structures are useful for unordered data. For example, a hash table provides immediate access to data indexed by an arbitrary key value, that could be a number (such as a memory address for cached memory), a URL (such as for a web cache) or a dictionary.

Jun 10th 2026

4 Weeks

Algorithms Data Structures Graph Algorithms

Coursera

University of Alberta

Client Needs and Software Requirements (Coursera)

CS: Design & Product

This course covers practical techniques to elicit and express software requirements from client interactions. Upon successful completion of this course, you will be able to: Create clear requirements to drive effective software development; visualize client needs using low-fidelity prototypes; maximize the effectiveness of client interactions - adapt to changing product requirements.

Jun 8th 2026

4 Weeks

Computer Science Interaction Software Development

Coursera

University of California, Irvine

Networking and Security in iOS Applications (Coursera)

Security & Networking

You will learn to extend your knowledge of making iOS apps so that they can securely interact with web services and receive push notifications. You'll learn how to store data securely on a device using Core Data. You’ll also learn to securely deploy apps to the App Store and beta users over-the-air. The format of the course is through a series of code tutorials. We will walk you through the creation of several apps that you can keep as a personal app toolbox. When you make your own apps after this course, you can bring in these capabilities as needed. When necessary we pop out of the code tutorials to talk about concepts at a higher level so that what you are programming makes sense.

Jun 8th 2026

4 Weeks

Security JSON Networks

Coursera

University of Alberta

Reviews & Metrics for Software Improvements (Coursera)

CS: Design & Product

This course covers techniques for monitoring your projects in order to align client needs, project plans, and software production. It focuses on metrics and reviews to track and improve project progress and software quality. What you will learn: apply techniques to measure and visualize project progress, integrate Agile review practices to increase project visibility; reflect on lessons learned in software projects through retrospective exercises; improve project and process quality through ongoing measurement

Jun 8th 2026

4 Weeks

Software Agile Project Management