algorithm design techniques on complete graphwhere every pair of vertices is connected (in both directions)this algorithm is almost certain to be faster than |viterations of dijkstra' algorithmbecause the loops are so tight lines to can be executed in parallelas can lines to thusthis algorithm seems to be well suited for parallel computation dynamic programming is powerful algorithm design techniquewhich provides starting point for solution it is essentially the divide-and-conquer paradigm of solving simpler problems firstwith the important difference being that the simpler problems are not clear division of the original because subproblems are repeatedly solvedit is important to record their solutions in table rather than recompute them in some casesthe solution can be improved (although it is certainly not always obvious and frequently difficult)and in other casesthe dynamic programming technique is the best approach known in some senseif you have seen one dynamic programming problemyou have seen them all more examples of dynamic programming can be found in the exercises and references randomized algorithms suppose you are professor who is giving weekly programming assignments you want to make sure that the students are doing their own programs orat the very leastunderstand the code they are submitting one solution is to give quiz on the day that each program is due on the other handthese quizzes take time out of classso it might only be practical to do this for roughly half of the programs your problem is to decide when to give the quizzes of courseif the quizzes are announced in advancethat could be interpreted as an implicit license to cheat for the percent of the programs that will not get quiz one could adopt the unannounced strategy of giving quizzes on alternate programsbut students would figure out the strategy before too long another possibility is to give quizzes on what seem like the important programsbut this would likely lead to similar quiz patterns from semester to semester student grapevines being what they arethis strategy would probably be worthless after semester one method that seems to eliminate these problems is to use coin quiz is made for every program (making quizzes is not nearly as time-consuming as grading them)and at the start of classthe professor will flip coin to decide whether the quiz is to be given this wayit is impossible to know before class whether or not the quiz will occurand these patterns do not repeat from semester to semester thusthe students will have to expect that quiz will occur with percent probabilityregardless of previous quiz patterns the disadvantage is that it is possible that there is no quiz for an entire semester this is not likely occurrenceunless the coin is suspect each semesterthe expected number of quizzes is half the number of programsand with high probabilitythe number of quizzes will not deviate much from this this example illustrates what we call randomized algorithms at least once during the algorithma random number is used to make decision the running time of the algorithm depends not only on the particular inputbut also on the random numbers that occur