Chapter 6: Divide, Combine, and Conquer. When problems can be decomposed into independent subproblems,
you can recursively solve these subproblems and usually get efficient, correct algorithms as a result. This principle has
several applications, not all of which are entirely obvious, and it is a mental tool well worth acquiring.
Chapter 7: Greed is Good? Prove It! Greedy algorithms are usually easy to construct. It is even possible to formulate
a general scheme that most, if not all, greedy algorithms follow, yielding a plug-and-play solution. Not only are they
easy to construct, but they are usually very efficient. The problem is, it can be hard to show that they are correct
(and often they aren’t). This chapter deals with some well-known examples and some more general methods for
constructing correctness proofs.
Do'stlaringiz bilan baham: |