Monthly Subscription Starting at AED 99 + VAT

Delivery Problem
  • Level Foundation
  • Duration 13 hours
  • Course by University of California San Diego
  • Offered by

About

In this online course we’ll implement (in Python) together efficient programs for a problem needed by delivery companies all over the world millions times per day — the travelling salesman problem. The goal in this problem is to visit all the given places as quickly as possible. How to find an optimal solution to this problem quickly? We still don’t have provably efficient algorithms for this difficult computational problem and this is the essence of the P versus NP problem, the most important open question in Computer Science. Still, we’ll implement several solutions for real world instances of the travelling salesman problem. While designing these solutions, we will rely heavily on the material learned in the courses of the specialization: proof techniques, combinatorics, probability, graph theory. We’ll see several examples of using discrete mathematics ideas to get more and more efficient solutions.

Modules

Problem Statement and Applications

    • 2 Videos
    • 1 Readings
    • 2 Assignment
Show info about module content

2 Assignment

  • Puzzle: Delivery Problem
  • Cycle Weight

2 Videos

  • Delivery Problem
  • Shortest Common Superstring Problem

1 Readings

  • Additional Materials

Algorithms: First Steps

    • 2 Videos
    • 3 Assignment
Show info about module content

3 Assignment

  • Brute Force Algorithm
  • Average Weight
  • Nearest Neighbors

2 Videos

  • Brute Force Search
  • Nearest Neighbor

Visualizing Cycles

    • 2 Lab
Show info about module content

2 Labs

  • Draw Hamiltonian cycles
  • Average Weight: Examples

Exact Algorithms: Branch and Bound

    • 1 Videos
    • 1 Assignment
Show info about module content

1 Assignment

  • Branch and Bound

1 Videos

  • Branch and Bound

Exact Algorithms: Dynamic Programming (Optional)

    • 3 Videos
    • 1 Assignment
Show info about module content

1 Assignment

  • Dynamic Programming

3 Videos

  • Dynamic Programming: Main Ideas
  • Dynamic Programming: Representing Subsets
  • Dynamic Programming: Code

Exact Solution Based on Integer Linear Programming (Optional)

    • 1 Lab
Show info about module content

1 Labs

  • Integer Linear Programming (Optional)

Approximation Algorithms

    • 2 Videos
    • 1 Lab
    • 1 Assignment
Show info about module content

1 Assignment

  • 2-Approximation

1 Labs

  • 2-Approximation. Examples.

2 Videos

  • Approximation Algorithms
  • Local Search

Auto Summary

Explore the fundamental challenge of the travelling salesman problem in this engaging Data Science & AI course by Coursera. Over 780 minutes, you'll implement efficient Python programs to tackle this critical issue faced by delivery companies worldwide. Dive deep into combinatorics, probability, and graph theory to devise practical solutions, all while understanding the essence of the P versus NP problem. Ideal for foundation-level learners, the course offers both Starter and Professional subscription options. Join now to enhance your problem-solving skills and apply discrete mathematics in real-world scenarios.

Alexander S. Kulikov
Instructors

Alexander S. Kulikov

Владимир Подольский
Instructors

Владимир Подольский