University of California San Diego

Delivery Problem

This course is part of Introduction to Discrete Mathematics for Computer Science Specialization

Taught in English

Some content may not be translated

Alexander S. Kulikov
Владимир Подольский

Instructors: Alexander S. Kulikov

20,594 already enrolled

Included with Coursera Plus

Course

Gain insight into a topic and learn the fundamentals

4.7

(370 reviews)

Beginner level
No prior experience required
13 hours (approximately)
Flexible schedule
Learn at your own pace

Details to know

Shareable certificate

Add to your LinkedIn profile

Assessments

8 quizzes

Course

Gain insight into a topic and learn the fundamentals

4.7

(370 reviews)

Beginner level
No prior experience required
13 hours (approximately)
Flexible schedule
Learn at your own pace

See how employees at top companies are mastering in-demand skills

Placeholder

Build your subject-matter expertise

This course is part of the Introduction to Discrete Mathematics for Computer Science Specialization
When you enroll in this course, you'll also be enrolled in this Specialization.
  • Learn new concepts from industry experts
  • Gain a foundational understanding of a subject or tool
  • Develop job-relevant skills with hands-on projects
  • Earn a shareable career certificate
Placeholder
Placeholder

Earn a career certificate

Add this credential to your LinkedIn profile, resume, or CV

Share it on social media and in your performance review

Placeholder

There are 3 modules in this course

We start this module with the definition of mathematical model of the delivery problem — the classical traveling salesman problem (usually abbreviated as TSP). We'll then review just a few of its many applications: from straightforward ones (delivering goods, planning a trip) to less obvious ones (data storage and compression, genome assembly). After that, we will together take the first steps in implementing programs for TSP.

What's included

4 videos1 reading5 quizzes2 ungraded labs

We'll see two general techniques applied to the traveling salesman problem. The first one, branch and bound, is a classical approach in combinatorial optimization that is used for various problems. It can be seen as an improvement of the brute force search: we try to construct a permutation piece by piece, but at each step we check whether it still makes sense to continue constructing the permutation (if it doesn't, we just cut off the current branch). The second one, dynamic programming, is arguably the most popular algorithmic technique. It solves a problem by going through a collection of smaller subproblems.

What's included

4 videos2 quizzes1 ungraded lab

As we've seen in the previous modules, solving the traveling salesman problem exactly is hard. In fact, we don't even expect an efficient solution in the nearest future. For this reason, it makes sense to ask: is it possible to find efficiently a solution that is probably suboptimal, but at the same time is close to optimal? It turns out that the answer is yes! We'll learn two algorithms. The first one guarantees to find quickly a solution which is at most twice longer than the optimal one. The second algorithms does not have such guarantees, but it is known to work pretty well in practice.

What's included

2 videos1 quiz1 ungraded lab

Instructors

Instructor ratings
4.5 (27 ratings)
Alexander S. Kulikov
University of California San Diego
13 Courses799,044 learners

Offered by

Recommended if you're interested in Algorithms

Why people choose Coursera for their career

Felipe M.
Learner since 2018
"To be able to take courses at my own pace and rhythm has been an amazing experience. I can learn whenever it fits my schedule and mood."
Jennifer J.
Learner since 2020
"I directly applied the concepts and skills I learned from my courses to an exciting new project at work."
Larry W.
Learner since 2021
"When I need courses on topics that my university doesn't offer, Coursera is one of the best places to go."
Chaitanya A.
"Learning isn't just about being better at your job: it's so much more than that. Coursera allows me to learn without limits."

Learner reviews

Showing 3 of 370

4.7

370 reviews

  • 5 stars

    76.21%

  • 4 stars

    17.83%

  • 3 stars

    2.97%

  • 2 stars

    2.43%

  • 1 star

    0.54%

AT
5

Reviewed on Nov 19, 2019

LB
5

Reviewed on Jan 10, 2024

ES
5

Reviewed on Jun 18, 2018

New to Algorithms? Start here.

Placeholder

Open new doors with Coursera Plus

Unlimited access to 7,000+ world-class courses, hands-on projects, and job-ready certificate programs - all included in your subscription

Advance your career with an online degree

Earn a degree from world-class universities - 100% online

Join over 3,400 global companies that choose Coursera for Business

Upskill your employees to excel in the digital economy

Frequently asked questions