Implementing Useful Algorithms in C++

Description

TC ~ 4 X /( +6}~ 3.142 return x; Contents Preface 1 Background 1.1 Introduction 1.2 Algorithm Desiderata 1.3 Logics of Reasoning 1.4 Proving Basic Correctness 1.5 Asymptotic Notation 1.6 Machine Models 1.7 Randomized Algorithms 1.8 Measuring Efficiency 1.9 Data Types 1.10 Algorithm Experiments 1.11 Memory Management 1.12 Code Optimization 1.13 Recursion 1.14 Computation Strategies 1.15 Choosing among Several Algorithms 1.16 Making Algorithms Parallel 1.17 How to Implement an Algorithm 1.18 Recommended Classes for Computer Science Students 1.19 Some Study Strategies 1.20 Projects for the Whole Book 1.21 References 2 Software Engineering Essentials 2.1 Introduction 2.2 Overview of the Development Cycle 2.3 Requirements 2.4 Design of Component Structure 2.5 Design of Individual Components and Coding 2.6 Patterns 2.7 Error Management 2.8 Testing 2.9 Code Reviews 2.10 Release 2.11 Maintenance 2.12 Estimation 2.13 Following a Formal Process 2.14 Managing User Data 2.15 References 3 Career Advice and Interviews 3.1 Introduction 3.2 Applying for Jobs 3.3 The Resume 3.4 Behavioral Questions and Interviews 3.5 Technical Interviews 3.6 More Difficult Questions 3.7 System Design Interviews 3.8 Offer Negotiation 3.9 How to Leave Your Current Job Nicely 3.10 Fight Complacency 3.11 Projects 3.12 References 4 Introduction to Computer Law 4.1 Introduction 4.2 Intellectual Property 4.3 Patents 4.4 Trade Secrets 4.5 Copyrights 4.6 Trademarks 4.7 Intellectual Property Management 4.8 Contracts 4.9 Licenses 4.10 Employment Agreements 4.11 Privacy 4.12 Computer Crime 4.13 Serving as an Expert Witness 4.14 Projects 4.15 References 5 Fundamental Data Structures 5.1 Introduction 5.2 Utility Functions 5.3 Vector 5.5 Linked List 5.6 Garbage-collecting Free List Root 5.8 Queue back front 5.9 Trees 5.10 Bit Algorithms 5.11 Bit Set tBitO Used bits Unused bits 111001101110101001101000110|10101010| Corresponding Logical Number 101101100010|10010101110110011 J 5.12 Union-find 5.13 Implementation Notes 5.14 Comments 5.15 Projects 5.16 References 6 Random Number Generation 6.1 Introduction 6.2 A Quick Review of Probability 6.3 Pseudorandom Number Generation OutputQ Outpirt Output2 Output3 6.4 Xorshift 6.5 Mersenne Twister 6.6 MRG32k3a 6.7 RC4 6.8 Picking a Generator 6.9 Using a Generator 6.10 Generating Samples from Distributions 6.11 Generating Samples from Bounded-range Discrete Distributions 6 = 1 + 2 + 3, so the root's value = 3 6.12 Generating Samples from Specific Distributions 6.13 Generating Random Objects 1 1 I 22 6.14 Generating Samples from Multidimensional Distributions 6.15 The Monte Carlo Method 2 6.16 Implementation Notes 6.17 Comments 6.18 Projects 6 .19 References 7 Sorting 7.1 Introduction 7.2 Insertion Sort 7.3 Quicksort »• 7.4 Mergesort 7.5 Integer Sorting 7.6 Vector Sorting 7.7 Permutation Sort 7.8 Selection 7.9 Multiple Selection J 7.10 Searching 7.11 Implementation Notes 7.12 Comments 7.13 Projects 7.14 References 8 Dynamic Sorted Sequences 8.1 Introduction 8.2 Requirements 8.3 Skip List 8.4 Treap 8.5 Tree Iterators 8.6 Augmentations and API Variants 8.7 Vector Keys 8.8 LCP Augmentation for Trees J 8.9 Tries 8.11 Performance Comparisons 8.12 Implementation Notes 8.13 Comments 8.14 Projects 8.15 References 9 Hashing 9.1 Introduction 9.2 Hash Functions 9.3 Universal Hash Functions 9.4 Nonuniversal Hash Functions 9.5 Rolling Hash Functions 9.6 Collection of Hash Functions 9.7 Hash Tables 9.8 Chaining Hash Table 9.9 Linear Probing Hash Table 9.10 Timings 9.11 Bloom Filter 9.12 Implementation Notes 9.13 Comments 9.14 Projects 9.15 References 10 Priority Queues 10.1 Introduction 10.2 The API 10.3 Binary Heap Vector: abicdjkefghlmno 10.4 Indexed Heaps 10.5 Implementation Notes 10.6 Comments 10.7 References 11 Graph Algorithms 11.1 Introduction 11.2 Basics 11.3 Graph Representation 11.4 Search 11.5 Some Applications of Search 11.6 Minimum Spanning Tree 2,5 11.7 Shortest Paths 11.8 Flow Algorithms Let edge capacities be 2 for (5,3) to (9,1) and 1 for Let edge capacities be 1 and costs distances for all 11.9 Bipartite Matching 11.10 Stable Matching 11.11 Assignment Problem Let edges cost 1 if straight and 0 if diagonal 11.12 Generating Random Graphs 2 ! 11.13 Implementations Notes 11.14 Comments 11.15 Projects 11.16 References 12 Miscellaneous Algorithms and Techniques 12.1 Introduction 12.2 Making Static Data Structures Dynamic 12.3 Making Data Structures Persistent 12.4 Maintaining a Cache 12.5 k-bit-word Vector 12.6 Set Union on Intervals 12.7 Generating the First N Primes 12.8 Generating All Permutations 12.9 Generating All Combinations 12.10 Generating All Subsets 12.11 Generating All Partitions 12.12 Generating All Constrained Objects 12.13 Implementation Notes 12.14 Comments 12.15 Projects 12.16 References 13 External Memory Algorithms 13.1 Introduction 13.2 Disks and Files 13.3 File Layout 13.4 Working with CSV Files 13.5 The I/O Model 13.6 External Memory Vector 13.7 Sorting Vector Pointers Chunks Buffers 13.8 Vector-based Data Structures 13.9 B+ Tree 13.10 Comments 13.11 Projects 13.12 References 14 String Algorithms 14.1 Introduction 14.2 Single-pattern Search J 14.3 Multiple Patterns 14.4 Regular Expressions 2 14.5 Extended Patterns 14.6 String Distance Algorithms 14,7 Inverted Index 14.8 Suffix Index 2 I 14.9 Syntax Tree 14.10 Introduction to Succinct Data Structures 14.11 Implementation Notes 14.12 Comments 14.13 Projects 14.14 References 15 Compression 15.1 Introduction 15.2 Fundamental Limits 15.3 Entropy 15.4 Bit Stream 15.5 Codes 15.6 Static Codes 1 2 2 15.8 Dictionary Compression 15.9 Run-length Encoding j 2 15.10 Move-to-front Transform 15.11 Burrows-Wheeler Transform 15.12 Implementation Notes 15.13 Comments 15.14 Projects 15.15 References 16 Combinatorial Optimization 16.1 Introduction 16.2 Complexity Theory 16.3 Typical Hard Problems 16.4 Approximation Algorithms 16.5 Greedy Construction Heuristics 16.6 Branch and Bound 16.7 State Space Shortest Path Search with Lower Bounds 16.8 Local Search J 16.9 Applying Local Search to Some Problems 16.10 Simulated Annealing 16.11 Iterated Local Search 2 16.12 Genetic Algorithms 2 1 6.13 Some Performance Results 16.14 Problem-specific Preprocessing 16.15 Multiobjective Optimization 16.16 Constraint Processing 16.17 Stochastic Problems 16.18 General Advice 16.19 Implementation Notes 16.20 Comments 16.21 Projects 16.22 References 17 Large Numbers 17. 1 Introduction 17. 2 Representation 17. 3 Addition and Subtraction a 048 b 057 carry 0110 17.4 Shifts 17.5 Multiplication 17.6 Division 17.7 Conversion to Decimal 17.8 Exponentiation 17.9 Lg 17.10 Integer Square Root 17.11 Greatest Common Divisor 17.12 Modular Inverse J 17.13 Primality Testing 17.14 Rationals J J 17.15 Implementation Notes 17.16 Comments 17.17 Projects 17.18 References 18 Computational Geometry 18.1 Introduction 18.2 Distances 2; 18.3 VP Tree 18.4 к-d Tree 18.5 Problems in High Dimensions 18.6 Data Structures for Geometric Objects 18.7 Points 18.8 Geometric Primitives 18.9 Convex Hull 18.10 Plane Sweep 2 18.11 Comments 18.12 Projects 18.13 References 19 Error Detection and Correction 19.1 Introduction 19.2 Binary Polynomials 19.3 Polynomials Over Finite Fields 19.4 Error Detection 19.5 Channels and Codes 19.6 Finite Field Computation 19.7 Polynomials over Galois Field Elements 19.8 Reed-Solomon Codes 19.9 Bounds on Fixed-alphabet Minimum-distance Codes 19.10 Boolean Matrices 19.11 Low-density Parity-check Codes 19.12 Implementation Notes 19.13 Comments 19.14 Projects 19.15 References 20 Cryptography 20.1 Introduction 20.2 File Encryption 20.3 Key Length 20.4 Key Storage 20.5 Cryptographic Hashing 20.6 Key Exchange 20.7 Other Protocols 20.8 Implementations Notes 20.9 Comments 20.10 Projects 20.11 References 21 Computational Statistics 21.1 Introduction 21.2 Estimands 21.3 Estimators 21.4 Finding Most Efficient Estimators 21.5 Some Peculiarities of Asymptotics 21.6 Evaluating the Normal CDF 21.7 Evaluating the Т-Distribution CDF 21.8 More on Confidence Intervals 21.9 Finite-sample Bounds for the Mean 21.10 Confidence Intervals for Common Location Measures 21.11 Outliers and Robust Inference 21.12 Functions of Estimates 21.13 Measuring Algorithm Runtime 21.14 Correlation Analysis 21.15 The Bootstrap 21.16 When Does Bootstrap Work? 21.17 Hypothesis Tests 21.18 Comparing Tests 21.19 Using Tests Effectively 21.20 Validation of Studies 21.21 Comparing Matched Pairs 21.22 Multiple Comparisons 21.23 Comparing Matched Tuples 2 j 21.24 Comparing Independent Samples 21.25 Permutation Tests 21.26 Comparing Many Alternatives on Multiple Domains 21.27 Working with Count Data 21.28 Testing Distribution Differences 21.29 Comparing Data to a Distribution 21.30 Comparing Distributions of Two Samples 21.31 Sensitivity Analysis 21.32 Sobol Sequence 21.33 Design of Experiments—Main Ideas 21.34 Markov Chain Monte Carlo 21.35 Bayesian Methods 21.36 Finding Best Alternative via Simulation 21.37 Sample Size Calculations 21.38 Time Series Analysis 21.39 Using Statistics in Practice 21.40 Analysis of Decisions 21.41 Implementation Notes 21.42 Comments 21.43 Projects 21.44 References 22 Numerical Algorithms—Introduction and Matrix Algebra 22.1 Introduction 22.2 Floating Point Arithmetic 22.3 Errors from Using Floating Point Arithmetic 22.4 Approximation Error 22.5 Stability and Condition Numbers 22.6 Optimization Error 22.7 Other Common Themes 22.8 Developing Robust Numerical Software 22.9 Matrix Algebra 22.10 Matrix Norms 22.11 LUP Decomposition 1и II Ik II IpII 22.12 Cholesky Decomposition 22.13 Band Matrices 22.14 Solving Tridiagonal Matrix Equations 22.15 Orthogonal Transformations 22.16 QR Decomposition { I 22.17 Symmetric Matrix Eigenvalues and Eigenvectors 22.18 Singular Value Decomposition 22.19 Asymmetric Matrix Eigenvalues and Eigenvectors 22.20 Sparse Matrices 22.21 Iterative Methods for Sparse Matrices 22.22 Iterative Methods for Eigenvalues 22.23 Introduction to Interval Arithmetic 22.24 Implementation Notes 22.25 Comments 22.2 6 Projects 22.2 7 References 23 Numerical Algorithms—Working with Functions 23.1 Introduction 23.2 Fast Fourier Transform 23.3 Interpolation—General Ideas 23.4 Polynomial Interpolation from Existing Data 23.5 Chebyshev Polynomials J И I 23.7 Splines—For Existing Data Eval Points 23.8 Comparison of Interpolation Methods 23.9 Integration 23.10 Multidimensional Integration 23.11 Function Evaluation 23.12 Estimating Derivatives 2 2 j 23.13 Solving Nonlinear Equations and Systems IM IM 23.14 Finding All Roots in 1D 2 23.15 Ordinary Differential Equations 2