4. When Greedy Doesn't Work

Getting Started with Competitive Programming

(an NPTEL course)

Module 4. When Greedy Doesn't Work

This module is in three parts.

Part 1. Coin Change

In this video we discuss the coin change problem. You can find the codeforces problem referred to in the video at this link. For more on the coin change problem in general, please see the Wikipedia page.

and you can find out even more by taking a look at these papers:

Guarding a Museum

In this video, we talk about the problem of guarding a museum. This is a special case of a more general class of so-called art gallery problems, which you can find out more about here.

(Spoiler alert!) You can find an answer to the last question posed in the video in this discussion.

Traveling Salesman

In this video, we discuss the Traveling Salesman Problem. Here are some of the links mentioned in the video:

  1. The Quanta Article
  2. The Wikipedia page
  3. The paper on when greedy algorithms fail
  4. The XKCD Comic

super-embed:<div id="hyvor-talk-view"></div><script async defer type="text/javascript" src="//talk.hyvor.com/web-api/embed.js"></script>