Approximation Algorithms and Linear Programming

Course Overview

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. Learn more: MS in Computer Science: https://coursera.org/degrees/ms-computer-science-boulder