Practical Algorithms for Programmers

There are numerous well written books on algorithms. Those by Sedgewick and Knuth come to mind, for example. But some students find these too hard. Binstock and Rex aimed their work at this need. This book has very little in the way of fancy maths. It emphasises examples with complete code listings. Not unlike "Numerical Recipes". Hence, you can also treat the text as a cookbook for your needs. The code is in C. If you are using another language, you can get some practise in seeing how well and accurately you understand the book's code. Algorithms for Programmers......Page 1 Contents......Page 2 Some Important Remarks......Page 7 List of Important Symbols......Page 8 1.1 Discrete Fourier Transform......Page 9 1.2 Symmetries of Fourier transform......Page 10 1.3.2 Decimation in time (DIT) FFT......Page 11 1.3.3 Decimation in frequency (DIF) FFT......Page 14 1.4 Saving Trigonometric Computations......Page 16 1.4.2 Recursive generation of the sin=cos-values......Page 17 1.5.2 Decimation in time......Page 18 1.5.3 Decimation in frequency......Page 19 1.5.4 Implementation of radix r = px DIF/DIT FFTs......Page 20 1.6 Split Radix Fourier Transforms (SRFT)......Page 23 1.7 Inverse FFT for Free......Page 24 1.8 Real Valued Fourier Transforms......Page 25 1.8.1 Real valued FT via wrapper routines......Page 26 1.8.2 Real valued split radix Fourier transforms......Page 28 1.9.2 The row column algorithm......Page 32 1.10 Matrix Fourier Algorithm (MFA)......Page 33 1.11 Automatic Generation of FFT Codes......Page 34 2.1 Definition & Computation via FFT......Page 37 2.2 Mass Storage Convolution using MFA......Page 41 2.3 Weighted Fourier Transforms......Page 43 2.5 Convolution using MFA......Page 45 2.5.2 The case R = 3......Page 46 2.7 Convolution without Transposition using MFA......Page 47 2.8.1 Definition of the ZT......Page 48 2.8.4 Fractional Fourier transform by ZT......Page 49 3.2.1 Decimation in time (DIT) FHT......Page 50 3.2.2 Decimation in frequency (DIF) FHT......Page 53 3.3 Complex FT by HT......Page 56 3.4 Complex FT by Complex HT & Vice Versa......Page 57 3.5 Real FT by HT & Vice Versa......Page 58 3.6 Discrete Cosine Transform (DCT) by HT......Page 59 3.7 Discrete Sine Transform (DST) by DCT......Page 60 3.8 Convolution via FHT......Page 61 3.9 Negacyclic Convolution via FHT......Page 63 4.1 Prime Modulus: Z/pZ = Fp......Page 64 4.2 Composite Modulus: Z/mZ......Page 65 4.3.1 Radix 2 DIT NTT......Page 68 4.3.2 Radix 2 DIF NTT......Page 69 4.5 Chinese Remainder Theorem (CRT)......Page 70 4.6 A Modular Multiplication Technique......Page 72 4.7 Number-Theoretic Hartley Transform......Page 73 Ch5 Walsh Transforms......Page 74 5.1 Basis Functions of Walsh Transforms......Page 78 5.2 Dyadic Convolution......Page 79 5.3 Slant transform......Page 81 Ch6 Haar transform......Page 83 6.1 In-Place Haar Transform......Page 84 6.2 Integer to Integer Haar Transform......Page 87 7.1 Trivia......Page 89 7.2 Operations on Low Bits/Blocks in a Word......Page 90 7.3 Operations on High Bits/Blocks in a Word......Page 92 7.4 Functions Related to Base-2 Logarithm......Page 95 7.5 Counting Bits in a Word......Page 96 7.6 Swapping Bits/Blocks of a Word......Page 97 7.7 Reversing Bits of a Word......Page 99 7.8 Generating Bit Combinations......Page 100 7.10 Bit Set Lookup......Page 102 7.11 Gray Code of a Word......Page 103 7.12 Generating Minimal-Change Bit Combinations......Page 105 7.13 Bitwise Rotation of a Word......Page 107 7.14 Bitwise Zip......Page 109 7.15 Bit Sequency......Page 110 7.16 Misc......Page 111 7.17 Bitarray Class......Page 113 7.18 Manipulation of Colors......Page 114 8.1.1 A naive version......Page 116 8.1.3 How many swaps?......Page 117 8.1.4 A still faster version......Page 118 8.1.5 The real world version......Page 120 8.2 Radix Permutation......Page 121 8.3 In-Place Matrix Transposition......Page 122 8.4.1 Rotate and reverse......Page 123 8.4.2 Zip and unzip......Page 124 8.5 Gray Code Permutation......Page 125 8.6.1 Basic definitions......Page 128 8.6.2 Compositions of permutations......Page 129 8.6.3 Applying permutations to data......Page 132 8.7.1 Lexicographic order......Page 133 8.7.2 Minimal-change order......Page 135 8.7.3 Derangement order......Page 137 8.7.4 Star-transposition order......Page 138 8.7.5 Yet another order......Page 139 9.1 Sorting......Page 141 9.2 Searching......Page 143 9.3 Index Sorting......Page 144 9.4 Pointer Sorting......Page 145 9.5 Sorting by Supplied Comparison Function......Page 146 9.6 Unique......Page 147 9.7 Misc......Page 149 10.1 Offline Functions: funcemu......Page 153 10.2 Combinations in Lexicographic Order......Page 156 10.3 Combinations in Co-Lexicographic Order......Page 158 10.4 Combinations in Minimal-Change Order......Page 159 10.5 Combinations in Alternative Minimal-Change Order......Page 161 10.6 Subsets in Lexicographic Order......Page 162 10.7 Subsets in Minimal-Change Order......Page 164 10.8 Subsets Ordered by Number of Elements......Page 166 10.9 Subsets Ordered with Shift Register Sequences......Page 167 10.10 Partitions......Page 168 11.2 Multiplication of Large Numbers......Page 171 11.2.2 Fast Multiplication via FFT......Page 172 11.2.3 Radix/Precision Considerations with FFT Multiplication......Page 174 11.3.1 Division......Page 175 11.3.2 Square root extraction......Page 176 11.4 Square Root Extraction for Rationals......Page 177 11.5 General Procedure for Inverse n-th Root......Page 179 11.6 Re-Orthogonalization of Matrices......Page 181 11.7 n-th Root by Goldschmidt's Algorithm......Page 182 11.8 Iterations for Inversion of Function......Page 183 11.8.1 Householder's formula......Page 184 11.8.2 Schroeder's formula......Page 185 11.8.3 Dealing with multiple roots......Page 186 11.8.4 A general scheme......Page 187 11.8.5 Improvements by the delta squared process......Page 189 11.9.1 AGM......Page 190 11.9.2 log......Page 192 11.9.3 exp......Page 193 11.9.6 Elliptic E......Page 194 11.10 Computation of pi/log(q)......Page 195 11.11 Iterations for High Precison Computations of pi......Page 196 11.12 Binary Splitting Algorithm for Rational Series......Page 201 11.13 Magic Sumalt Algorithm......Page 203 11.14 Continued Fractions......Page 205 App A Summary of Definitions of FTs......Page 207 AppB Pseudo Language Sprache......Page 209 AppC Optimization Considerations for Fast Transforms......Page 212 AppD Properties of ZT......Page 213 AppE Eigenvectors of Fourier Transform......Page 215 Bibliography......Page 216 Index......Page 219

Most algorithm books today are either academic textbooks or rehashes of the same tired set of algorithms. Practical Algorithms for Programmers is the first book to give complete code implementations of all algorithms useful to developers in their daily work.

This book focuses on practical, immediately usable code with extensive discussion of portability and implementation-specific details. The authors present the useful but rarely discussed algorithms for phonetic searches, date and time routines (to the year AD 1), B-trees and indexed files, data compression, arbitrary precision arithmetic, checksums and data validation, as well as the most comprehensive coverage available of search routines, sort algorithms, and data structures.

Practical Algorithms for Programmers requires only a working knowledge of C and no math beyond basic algebra. The source code is ANSI-compliant and has been tested and run on compilers from Borland, Microsoft, Watcom, and UNIX.

020163208XB04062001

The first book to provide a comprehensive, nonacademic treatment of the algorithms commonly used in advanced application development. The authors provide a wide selection of algorithms fully implemented in C with substantial practical discussion of their best use in a variety of applications.

This book focuses on practical, immediately usable code with extensive discussion of portability and implementation-specific details. The authors present the useful but rarely discussed algorithms for phonetic searches, date and time routines (to the year AD 1), B-trees and indexed files, data compression, arbitrary precision arithmetic, checksums and data validation, as well as the most comprehensive coverage available of search routines, sort algorithms, and data structures. Practical Algorithms for Programmers requires only a working knowledge of C and no math beyond basic algebra. The source code is ANSI-compliant and has been tested and run under UNIX and on compilers from Borland, Microsoft, and Watcom A detailed book on algorithms and data structures fully implemented in C. It goes way beyond the usual coverage of these topics: rather than small snippets of code, each topic is covered in depth. For example, the B-tree includes the full code for a B-tree database. The algorithms cover the usual things: search, sort, hashing etc. But the book also covers algorithms rarely covered by other titles: the various data compression algorithms, complete date and time routines (with all the hinky calendar problems), Soundex (searching for names based on how they sound), arbitrary precision arithmetic, etc. The only downside is that the C code is from 1995, so the code feels a bit dated in parts. Providing a non-academic treatment of algorithms commonly used in advanced application development, this book features a selection of algorithms fully implemented in C with practical discussions of their use in various applications. Theoretical material is presented in an approachable manner. Provides a comprehensive, non-academic treatment of the algorithms commonly used in advanced application development, shows how professional programmers actually use algorithms in their daily work, and requires no previous familiarity with the theory of algorithms. Original. (Advanced).