“I’d rather be a failure at something I love than a success at something I hate.” — George Burns
“You live and you learn — at any rate, you live.” — Douglas Adams
“A problem worthy of attack proves its worth by fighting back.” — Paul Erdos
HomeAboutContact
~
HomeAboutContact

4. When Greedy Doesn't Work

Getting Started with Competitive Programming

(an NPTEL course)

Home ⸱ Quick Links ⸱ Grading Policy ⸱ References ⸱ FAQ ⸱ Feedback ⸱ Connect ⸱ Credits

Module 4. When Greedy Doesn't Work

Go back to Week 3

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:

Combinatorics of the Change-Making Problem (PDF)

How many ways can you make change: Some Easy Proofs (PDF)

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>