No label defined (Q4023850)

This book is intended to survey the most important computer algorithms in use today. The book contains forty-five chapters grouped into the following eight major parts. Fundamentals. In this part some tools and methods used throughout the later chapters are presented. A short discussion of the programming language C++ is included, followed by an introduction to basic data structures, including arrays, linked lists, stacks, queues and trees. The author explains recursion and basic approach towards analyzing and implementing algorithms. Sorting algorithms. A variety of methods for rearranging files are described and compared in this part. The focus is on Quicksort, the sorting algorithm which is probably more widely used than any other. Searching algorithms. The author discusses basic and advanced methods for searching using trees and digital key transformations, including binary search tree, balanced trees, hashing, digital search trees and tries, and methods appropriate for very large files. Similarities to sorting methods are pointed out. String processing. String processing algorithms include a range of methods for dealing with sequences of characters. String searching leads to pattern matching which leads to parsing. File compression techniques and cryptology are also considered. Geometric algorithms. Algorithms for finding the convex hull of a set of points, for finding intersections among geometric objects, for solving closest-point problems and for multidimensional searching are presented in this part. Graph algorithms. Graph algorithms are important for a variety of difficult optimization problems. A general strategy for searching in graphs is described and applied to connectivity problems, including shortest path, minimum spanning tree, network flow and matching. A unified treatment of these algorithms depends on a basic data structure developed earlier. Mathematical algorithms. This part includes a sample of fundamental methods from arithmetic and numerical analysis: polynomial arithmetic, matrix arithmetic, solution of systems of linear equations, curve fitting and integration. Advanced topics. Parallel algorithms, fast Fourier transform, dynamical programming, linear programming, branch-and-bound method and NP- completeness are briefly surveyed from an elementary viewpoint for the purpose of relating the material of the book to several other advanced fields. Each chapter of the book is followed by a list of exercises (without results) and each part is concluded by corresponding bibliography. The main ideas of the algorithms are clearly described without mathematical details and proofs. The simplest reasonable versions of the algorithms are presented so that the corresponding codes in programming language C++ have largely at most 20 lines. The reader cannot leave unnoticed excellent figures which have been prepared with the aid of computer. Readers of this book are expected to have an elementary acquaintance in programming, machine organization and elementary calculus. No specific knowledge about C++ is assumed -- the treatment of the book is self- contained. Overall, this nice book can be recommended as a textbook or as a reference for those engaged in the development of computer systems or application programs.