Mastering Algorithms With C - Kyle Loudon [146]
Related Topics
Bubble sort
An inefficient O (n 2) sorting algorithm that works by exchanging neighboring elements to propagate one element at a time to its correct position in the sorted set.
Tournament sort
An O (n lg n) algorithm that requires three times the space of the data. It works by pairing up elements to promote a "winner" as the next element to be placed in the sorted set.
Heapsort
An efficient sorting algorithm that uses a heap (see Chapter 10) to build a sorted set. Heapsort runs in O (n lg n) and sorts in place. However, a good implementation of quicksort generally beats it by a small constant factor.
Introsort
A sorting algorithm that behaves like quicksort, but detects when it would be better to switch to heapsort. By doing this, in some cases it gains a slight performance advantage over quicksort.
Bucket sort
A linear-time sorting algorithm on average for data that is uniformly randomly distributed. It works by distributing the data into several buckets and sorting the buckets to produce a sorted set.
Chapter 13. Numerical Methods
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:
Polynomial interpolation
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 p n(z) of degree ≤ n, where n + 1 is the number of points for which values are known.
Least-squares estimation
A method of determining estimators b 1 and b 0 for a function y (x) = b 1 x + b 0 so that y (x) is a best-fit line through a set of n points (x 0, y 0), . . ., (x n - 1, y n - 1). A best-fit line using least-squares estimation minimizes the sum of squared vertical distances between each point (x i , y i) , i = 0, . . ., n - 1, and a corresponding point (x i , y (x i ) ) 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.
Curve fitting
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.
Scatter plots
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.
Approximating functions
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.