Tag Archives: Greedy

Making change problem dynamic programming example

Dynamic programming making change algorithm Today we are going to discuss a new problem that can be solved using Dynamic Programming technique. We will talk about the well known problem of making change using a minimum number of coins. If …

Read more »

Greedy algorithm event scheduling

Greedy algorithm interval scheduling problem An event starts at 9AM and finishes at 6PM. Several volunteers have signed to the event each providing a time period during which they can help. We need to cover the entire time of the …

Read more »

Greedy algorithm activity selection problem

Activity selection problem greedy algorithm Assume that you are an administrator who is in charge of a conference room equipped with some expensive telepresence system. Different employees or groups of employees need to have access to the conference room but …

Read more »

Maximal independent set algorithm

Maximal independent set problem You have a set of radio stations all having the same transmission frequency. Signals from adjacent stations interfere with each other which causes data loss. We need to choose the largest set of stations that can …

Read more »

Make Change Algorithm

Problem Given an amount of money in US currency. Give an algorithm to make change of the given amount using the smallest possible number of coins. Recall that US coins are Dollars (100 cents), Quarters (25 cents), Dimes (10 cents), …

Read more »