Algorithms. Design techniques and analysis (Q5890565)

The book presents a comprehensive overview of the modern view of the analysis of algorithms and computational complexity. It is a valuable compendium of the knowledge in the theory of algorithms gathered in the previous century expressed in a language that is accessible to readers who want to be initiated in the field. Note that few books were published at such level in the last decade.NEWLINENEWLINEThe material starts with a well-written introduction to the basic concepts like time and space complexity, data structures and heaps. Then the focus is put on the well-known recursive techniques, including dynamic programming. In addition, first-cut techniques are discussed with an accent on the greedy approach and graph traversals. The complexity of the problems that were presented shortly in the first part is studied deeper in the case of NP-complete problems. Naturally, as current solutions to such problems, randomized and approximation algorithms are reviewed. Special attention is paid to complex problems like network flow, matching, geometric sweeping and Voronoi diagrams.NEWLINENEWLINEThe book is well organized in a mathematical style with a multitude of theorems, lemmas, proofs as well as numerous exercises, all of them challenging the reader. Consequently, it is proper material to be presented to undergraduate students in exact sciences. The deepness of the study for many algorithms is also proper for an advanced lecture in algorithm complexity.