greedy algorithms and invariants the intended function of programor part of programcan be specified by making general assertions about the values which the relevant variables will take after execution of the program -"an axiomatic basis for computer programming, hoare sometimesthere are multiple greedy algorithms for given problemand only some of them are optimum for exampleconsider cities on linehalf of which are whiteand the other half are black suppose we need to pair white with black cities in one-to-one fashion so that the total length of the road sections required to connect paired cities is minimized multiple pairs of cities may share single section of roade if we have the pairing ( and ( then the section of road between cities and can be used by cities and the most straightforward greedy algorithm for this problem is to scan through the white citiesandfor each white citypair it with the closest unpaired black city this algorithm leads to suboptimum results consider the case where white cities are at and at and black cities are at and at if the white city at is processed firstit will be paired with the black city at forcing the cities at and to pair upleading to road length of in contrastthe pairing of cities at and and and leads to road length of slightly more sophisticated greedy algorithm does lead to optimum resultsiterate through all the cities in left-to-right orderpairing each city with the nearest unpaired city of opposite color note that the pairing for the first city must be optimumsince if it were to be paired with any other citywe could always change its pairing to be with the nearest black city without adding any road this observation can be used in an inductive proof of overall optimality greedy algorithms boot camp for us currencywherein coins take values centsthe greedy algorithm for making change results in the minimum number of coins here is an implementation of this algorithm note that once it selects the number of coins of particular valueit never changes that selectionthis is the hallmark of greedy algorithm def change_making cents )coins [ num_coins for coin in coins num_coins +cents coin cents %coin return num_coins we perform iterationsand each iteration does constant amount of computationso the time complexity is (