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 you take the US currency as an example where we have the denominations (1C, 5C,
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 event (9AM-6PM) with the least number of volunteers. Assume the next volunteer in line can
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 they can not use the telepresence system at the same time. Every day employees who
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 operate at the same time without data loss. Assume the list of stations is represented
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), Nickels (5 cents) and Pennies (1 cent) Solution A greedy approach to solve this problem
