University of Colorado Boulder - Approximation Algorithms and Linear Programming
- Offered byCoursera
Approximation Algorithms and Linear Programming at Coursera Overview
Duration | 48 hours |
Total fee | Free |
Mode of learning | Online |
Official Website | Explore Free Course  |
Credential | Certificate |
Approximation Algorithms and Linear Programming at Coursera Highlights
- Earn a certificate of completion
- Add to your LinkedIn profile
- 18 quizzes, 1 assignment
Approximation Algorithms and Linear Programming at Coursera Course details
- What you'll learn
- Formulate linear and integer programming problems for solving commonly encountered optimization problems.
- Develop a basic understanding of how linear and integer programming problems are solved.
- Understand how approximation algorithms compute solutions that are guaranteed to be within some constant factor of the optimal solution
- This course continues our data structures and algorithms specialization by focussing on the use of linear and integer programming formulations for solving algorithmic problems that seek optimal solutions to problems arising from domains such as resource allocation, scheduling, task assignment, and variants of the traveling salesperson problem
- Next, we will study algorithms for NP-hard problems whose solutions are guaranteed to be within some approximation factor of the best possible solutions
- Such algorithms are often quite efficient and provide useful bounds on the optimal solutions
- The learning will be supported by instructor provided notes, readings from textbooks and assignments
- Assignments will include conceptual multiple-choice questions as well as problem solving assignments that will involve programming and testing algorithms
- This course can be taken for academic credit as part of CU Boulder's Masters of Science in Computer Science (MS-CS) degrees offered on the Coursera platform
- This fully accredited graduate degree offer targeted courses, short 8-week sessions, and pay-as-you-go tuition. Admission is based on performance in three preliminary courses, not academic history
- CU degrees on Coursera are ideal for recent graduates or working professionals
- MS in Computer Science: https://coursera.org/degrees/ms-computer-science-boulder
Approximation Algorithms and Linear Programming at Coursera Curriculum
Linear Programming
Introduction to Linear Programming
What is a Linear Program?
Example: Cake-Sharing Problem
Solving Linear Programs
Network Flow Problems and Linear Programs
Geometry of Linear Programs
Algorithms for Solving Linear Programs
Earn Academic Credit for your Work!
Course Support
Basics of Linear Programs
Solving LPs using PULP
Network Flow Problems as LPs
Geometry of Linear Programs
LP Algorithms
Linear Programming
Interactive Notes: Basics of Linear Programs
Lab: Formulate and Solve LPs using PULP
Interactive Notes: Diet Problem and Network Flow Problems
Interactive Notes on Geometry of Linear Programs and Simplex Algorithm
Integer Linear Programming
What is an Integer Linear Program?
Formal Introduction to Integer Linear Programs
NP Hardness of Integer Linear Programming
Vertex Cover as an Integer Linear Program
Linear Programming Approximations to Vertex Cover
Branch and Bound Algorithm for Solving Integer Linear Programs
Integer Linear Programming
Formulating/Solving ILPs
Vertex Cover ILP, LP Relaxation and Integrality Gap.
Branch and Bound Solvers
Vertex Cover Problem ILP formulation
Integer Linear Programs
Tutorial on solving ILPs using Python/PuLP package
Interactive Notes: Vertex Cover as an ILP
Interactive Notes: Integrality Gap for Vertex Cover
Interactive Notes: Branch and Bound Solvers for ILPs
Approximation Algorithms : Scheduling, Vertex Cover and MAX-SAT
Introduction to Approximation Algorithms
Introduction to Jobshop Scheduling and Algorithm Design
Analysis of Jobshop Scheduling
Approximation Algorithms for Vertex Cover and their Analysis
Approximation Algorithms for the Maximum Satisfiability Problem
Approximation Algorithm Basics
Job Shop Scheduling Questions
Vertex Cover
Max-SAT Approximation
Approximation Algorithms
Interactive Notes: Jobshop Scheduling
Interactive Notes on Vertex Cover Approximation Algorithms
Interactive Notes on Maximum Satisfiability Approximation
Travelling Salesperson Problem (TSP) and Approximation Schemes
Introduction to TSP and its applications
NP-Hardness of TSPs
Hardness of Approximating General TSPs
Held and Karp's Dynamic Programming Algorithm
Integer Linear Programming Formulation
Subtours and Subtour Elimination Formulation
Metric TSP and Shortcutting
Eulerian Walks for approximating TSPs
Christofides Algorithm and its Analysis
Heuristics for TSPs
Full Polynomial Time Approximation Scheme and Knapsack
TSP Basics
Held-Karp Algorithm
TSP Integer Programming
Approximations for Metric TSPs
Fully Polynomial Time Approximation Scheme
Travelling Salesperson Problems (TSP)
Interactive Notes on TSP Basics, NP-Hardness and Inapproximability
Interactive Notes on Exact Approaches to TSP
Interactive Notes: Approximations for Metric TSPs
Other courses offered by Coursera
Student Forum
Anything you would want to ask experts?
TechnologyComputer ScienceData Structures and AlgorithmsApproximation Algorithms and Linear Programming