algorithm design techniques denomination thusto give out seventeen dollars and sixty-one cents in changewe give out ten-dollar billa five-dollar billtwo one-dollar billstwo quartersone dimeand one penny by doing thiswe are guaranteed to minimize the number of bills and coins this algorithm does not work in all monetary systemsbut fortunatelywe can prove that it does work in the american monetary system indeedit works even if two-dollar bills and fifty-cent pieces are allowed traffic problems provide an example where making locally optimal choices does not always work for exampleduring certain rush hour times in miamiit is best to stay off the prime streets even if they look emptybecause traffic will come to standstill mile down the roadand you will be stuck even more shockingit is better in some cases to make temporary detour in the direction opposite your destination in order to avoid all traffic bottlenecks in the remainder of this sectionwe will look at several applications that use greedy algorithms the first application is simple scheduling problem virtually all scheduling problems are either np-complete (or of similar difficult complexityor are solvable by greedy algorithm the second application deals with file compression and is one of the earliest results in computer science finallywe will look at an example of greedy approximation algorithm simple scheduling problem we are given jobs jn all with known running times tn respectively we have single processor what is the best way to schedule these jobs in order to minimize the average completion timein this entire sectionwe will assume nonpreemptive schedulingonce job is startedit must run to completion as an examplesuppose we have the four jobs and associated running times shown in figure one possible schedule is shown in figure because finishes in job time figure jobs and times figure schedule #