What Does MVP Stand For? It’s Not What You Think.
October 7, 2024
Article
This course is part of Foundations of Data Structures and Algorithms Specialization
Instructor: Sriram Sankaranarayanan
10,869 already enrolled
Included with
(41 reviews)
Recommended experience
Advanced level
Completion of previous courses. Calculus, probability theory: distributions, expectations and moments. Some programming experience with Python.
(41 reviews)
Recommended experience
Advanced level
Completion of previous courses. Calculus, probability theory: distributions, expectations and moments. Some programming experience with Python.
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
Add to your LinkedIn profile
19 assignments
Add this credential to your LinkedIn profile, resume, or CV
Share it on social media and in your performance review
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
This module introduces the basics of linear programs and shows how some algorithm problems (such as the network flow problem) can be posed as a linear program. We will provide hands-on tutorials on how to pose and solve a linear programming problem in Python. Finally, we will provide a brief overview of linear programming algorithms including the famous Simplex algorithm for solving linear programs. The problem set will guide you towards posing and solving some interesting problems such as a financial portfolio problem and the optimal transportation problem as linear programs.
7 videos2 readings5 assignments1 programming assignment4 ungraded labs
This module will cover integer linear programming and its use in solving NP-hard (combinatorial optimization) problems. We will cover some examples of what integer linear programming is by formulating problems such as Knapsack, Vertex Cover and Graph Coloring. Next, we will study the concept of integrality gap and look at the special case of integrality gap for vertex cover problems. We will conclude with a tutorial on formulating and solving integer linear programs using the python library Pulp.
6 videos5 assignments1 programming assignment4 ungraded labs
We will introduce approximation algorithms for solving NP-hard problems. These algorithms are fast (often greedy algorithms) that may not produce an optimal solution but guarantees that its solution is not "too far away" from the best possible. We will present some of these algorithms starting from a basic introduction to the concepts involved followed by a series of approximation algorithms for scheduling problems, vertex cover problem and the maximum satisfiability problem.
5 videos4 assignments1 programming assignment3 ungraded labs
We will present the travelling salesperson problem (TSP): a very important and widely applicable combinatorial optimization problem, its NP-hardness and the hardness of approximating a general TSP with a constant factor. We present integer linear programming formulation and a simple yet elegant dynamic programming algorithm. We will present a 3/2 factor approximation algorithm by Christofides and discuss some heuristic approaches for solving TSPs. We will conclude by presenting approximation schemes for the knapsack problem.
11 videos5 assignments1 programming assignment3 ungraded labs
We asked all learners to give feedback on our instructors based on the quality of their teaching style.
CU Boulder is a dynamic community of scholars and learners on one of the most spectacular college campuses in the country. As one of 34 U.S. public institutions in the prestigious Association of American Universities (AAU), we have a proud tradition of academic excellence, with five Nobel laureates and more than 50 members of prestigious academic academies.
École normale supérieure
Course
University of Colorado Boulder
Build toward a degree
Course
EIT Digital
Course
École normale supérieure
Course
This course is part of the following degree program(s) offered by University of Colorado Boulder. If you are admitted and enroll, your completed coursework may count toward your degree learning and your progress can transfer with you.¹
This course is part of the following degree program(s) offered by University of Colorado Boulder. If you are admitted and enroll, your completed coursework may count toward your degree learning and your progress can transfer with you.¹
University of Colorado Boulder
Degree · 24 months
¹Successful application and enrollment are required. Eligibility requirements apply. Each institution determines the number of credits recognized by completing this content that may count towards degree requirements, considering any existing credits you may have. Click on a specific course for more information.
41 reviews
90.47%
7.14%
2.38%
0%
0%
Showing 3 of 41
Reviewed on Jan 16, 2024
Much better than previous courses in this specialization
Unlimited access to 10,000+ world-class courses, hands-on projects, and job-ready certificate programs - all included in your subscription
Earn a degree from world-class universities - 100% online
Upskill your employees to excel in the digital economy
Access to lectures and assignments depends on your type of enrollment. If you take a course in audit mode, you will be able to see most course materials for free. To access graded assignments and to earn a Certificate, you will need to purchase the Certificate experience, during or after your audit. If you don't see the audit option:
The course may not offer an audit option. You can try a Free Trial instead, or apply for Financial Aid.
The course may offer 'Full Course, No Certificate' instead. This option lets you see all course materials, submit required assessments, and get a final grade. This also means that you will not be able to purchase a Certificate experience.
When you enroll in the course, you get access to all of the courses in the Specialization, and you earn a certificate when you complete the work. Your electronic Certificate will be added to your Accomplishments page - from there, you can print your Certificate or add it to your LinkedIn profile. If you only want to read and view the course content, you can audit the course for free.
If you subscribed, you get a 7-day free trial during which you can cancel at no penalty. After that, we don’t give refunds, but you can cancel your subscription at any time. See our full refund policy.
Yes. In select learning programs, you can apply for financial aid or a scholarship if you can’t afford the enrollment fee. If fin aid or scholarship is available for your learning program selection, you’ll find a link to apply on the description page.
These cookies are necessary for the website to function and cannot be switched off in our systems. They are usually only set in response to actions made by you which amount to a request for services, such as setting your privacy preferences, logging in or filling in forms. You can set your browser to block or alert you about these cookies, but some parts of the site will not then work.
These cookies may be set through our site by our advertising partners. They may be used by those companies to build a profile of your interests and show you relevant adverts on other sites. They are based on uniquely identifying your browser and internet device. If you do not allow these cookies, you will experience less targeted advertising.
These cookies allow us to count visits and traffic sources so we can measure and improve the performance of our site. They help us to know which pages are the most and least popular and see how visitors move around the site. If you do not allow these cookies we will not know when you have visited our site, and will not be able to monitor its performance.
These cookies enable the website to provide enhanced functionality and personalization. They may be set by us or by third party providers whose services we have added to our pages. If you do not allow these cookies then some or all of these services may not function properly.