algorithm design techniques so farwe have been concerned with the efficient implementation of algorithms we have seen that when an algorithm is giventhe actual data structures need not be specified it is up to the programmer to choose the appropriate data structure in order to make the running time as small as possible in this we switch our attention from the implementation of algorithms to the design of algorithms most of the algorithms that we have seen so far are straightforward and simple contains some algorithms that are much more subtleand some require an argument (in some cases lengthyto show that they are indeed correct in this we will focus on five of the common types of algorithms used to solve problems for many problemsit is quite likely that at least one of these methods will work specificallyfor each type of algorithm we will see the general approach look at several examples (the exercises at the end of the provide many more examplesr discussin general termsthe time and space complexitywhere appropriate greedy algorithms the first type of algorithm we will examine is the greedy algorithm we have already seen three greedy algorithms in dijkstra'sprim'sand kruskal' algorithms greedy algorithms work in phases in each phasea decision is made that appears to be goodwithout regard for future consequences generallythis means that some local optimum is chosen this "take what you can get nowstrategy is the source of the name for this class of algorithms when the algorithm terminateswe hope that the local optimum is equal to the global optimum if this is the casethen the algorithm is correctotherwisethe algorithm has produced suboptimal solution if the absolute best answer is not requiredthen simple greedy algorithms are sometimes used to generate approximate answersrather than using the more complicated algorithms generally required to generate an exact answer there are several real-life examples of greedy algorithms the most obvious is the coinchanging problem to make change in currencywe repeatedly dispense the largest