The highlight of the book has to be its concise and readable C functions for all the algorithms presented here, including basics such as linked lists, stacks to trees, graphs and sorting/searching algorithms. The C functions that implement these algorithms are clearly printed and remarkably easy to read. You can use this sample code directly or adapt it into your C/C++ code.
Although mathematical concepts like Big-O notation are discussed, the authors don't get bogged down in the computer science theory surrounding algorithms. Instead, they present the most tried-and-true algorithms available today in an efficient format. Besides introducing each algorithm, they describe how each is used in computing today, along with a short demo application. Some of these samples are quite low-level, such as a virtual memory manager implemented with linked lists. Most examples are more general interest, such as a graphing example that counts network hops.
Each section ends with questions and answers about how the algorithms work, along with references to other algorithms (both in the book and from other sources). The authors concentrate on the most useful algorithms available today and don't try to cover every available variation. Busy readers will appreciate the intelligent selection--and efficient presentation--used here.
There are a number of books on C algorithms, but Master Algorithms With C is one of the most concise and immediately useful. It's a perfect choice for the working C/C++ programmer who's in a hurry to find just the right algorithm for writing real-world code. --Richard Dragan
Topics covered: Algorithm efficiency, pointer basics, arrays, recursion, Big-O Notation, linked lists, stacks, queues, sets, hash tables, trees and B-trees, searching, heaps and priority queues, graphs, sorting and searching algorithms, numerical methods, data compression, Huffman coding, LZ77, data encryption, DES, RSA, graph algorithms, minimum spanning trees, geometric algorithms, convex hulls.
About the Author
Kyle Loudon is a software engineer at Matrix Semiconductor in Santa Clara, California, where he works with file systems and applications for memory chips. Prior to Matrix, Kyle developed platform software for embedded devices, including various wireless phones and the Apple iPod. He also led the graphical user interface group at Jeppesen Dataplan (now a part of Boeing), developed flight planning software, and created system software at IBM in the early 1990s. For the past several years, Kyle has taught object-oriented programming using C++ at the University of California, Santa Cruz Extension, and has worked with C++ since the beginning of its widespread use in 1990. Kyle is the author of Mastering Algorithms with C, also published by O'Reilly and Associates.
Excerpt. © Reprinted by permission. All rights reserved.
Numerical methods are algorithms in numerical analysis. Numerical analysis is the study of problems in which numbers and approximation play an especially significant role. Computers are particularly well-suited to problems in numerical analysis because many such problems, while essentially involving common mathematical operations, require a lot of them. In the early days of computing, scientists monopolized computers with problems like this, which were far too intensive to be carried out by hand. Even today, problems in numerical analysis still occupy a good part of the cycles of some of the largest computers in the world. Hence, numerical analysis is a vast subject, and many numerical methods are as complicated and specific as the mathematical problems they solve. This chapter presents three numerical methods that are relatively simple but applicable to a wide variety of problems.This chapter covers:
A method of approximating values of a function for which values are known at only a few points. Fundamental to this method is the construction of an interpolating polynomial pn(z) of degree = n, where n + 1 is the number of points for which values are known.
A method of determining estimators b1 and b0 for a function y (x) = b1x + b0 so that y (x) is a best-fit line through a set of n points (x0, y0), . . ., (xn - 1, yn - 1). A best-fit line using least-squares estimation minimizes the sum of squared vertical distances between each point (xi , yi) , i = 0, . . ., n - 1, and a corresponding point (xi , y (xi ) ) along y (x).
Solution of equations
The process of finding roots of equations having the form f (x) = 0. Whereas for some equations it is possible to determine exact roots, a great deal of the time a method of approximation must be used.
Some applications of numerical methods are:
Linear regression models
Statistical models in which there is a linear-form relationship between an independent variable x and a variable y that depends on it. Least-squares estimators help to predict values of y for values of x we have not observed experimentally.
The process of fitting a curve to a number of points. If the points for which we have values are located at meaningful places on the curve we are trying to fit, and we know values at enough points, interpolation helps us draw a smooth curve.
Statistical tools that help ascertain the relationship between an independent variable x and a variable y that depends on it. Using least-squares estimators to draw a best-fit line through a linear-form scatter plot helps with this.
The process of determining the value of a function at points for which exact values are not known. This can be done by constructing an interpolating polynomial of the appropriate degree.
Tables containing values of computationally expensive functions or models of complicated physical phenomena. Often it is too costly to compute and store values of a function with the granularity required at some later time. Thus, we store a limited number of points and interpolate between them.
An area in which solving equations is one of the most fundamental problems routinely performed.
Description of Polynomial Interpolation
There are many problems that can be described in terms of a function. However, often this function is not known, and we must infer what we can about it from only a small number of points. To do this, we interpolate between the points. For example, in Figure 13-1, the known points along f (x) are x0, . . ., x8, shown by circular black dots. Interpolation helps us get a good idea of the value of the function at points z0, z1, and z2, shown by white squares. This section presents polynomial interpolation.