A Programmer's Companion to Algorithm Analysis

A Programmer’s Companion to Algorithm Analysis......Page 2
Preface......Page 4
Contents......Page 6
Foreword......Page 11
Part 1. The Algorithm Side: Regularity, Predictability, and Asymptotics......Page 15
1.1 Introduction......Page 17
1.2 The Time and Space Complexities of an Algorithm......Page 19
1.3 The Worst-, Average-, and Best- Case Complexities of an Algorithm......Page 23
1.3.1 Scenario 1......Page 25
1.4 Bit versus Word Complexity......Page 26
1.5 Parallel Complexity......Page 29
1.6 I/ O Complexity......Page 31
1.6.1 Scenario 1......Page 32
1.6.2 Scenario 2......Page 34
1.7 On- Line versus Off- Line Algorithms......Page 36
1.9 Lower Bounds and Their Significance......Page 38
Bibliographical Notes......Page 44
Exercise 1......Page 45
Exercise 4......Page 46
Exercise 6......Page 47
Exercise 8......Page 48
Exercise 11......Page 49
Bibliography......Page 0
2.1 Introduction......Page 50
2.2 Assumptions Inherent in the Determination of Statement Counts......Page 51
2.3 All Mathematical Identities Hold......Page 57
2.4 Revisiting the Asymptotic Nature of Complexity Analysis......Page 58
2.5 Conclusion......Page 59
Exercise 1......Page 60
Exercise 3......Page 61
3.1 General Techniques for Determining Complexity......Page 62
3.2 Selected Examples: Determining the Complexity of Standard Algorithms......Page 66
3.2.1 Multiplying Two......Page 67
3.2.2 Multiplying Two Square Matrices......Page 68
3.2.3 Optimally Sequencing Matrix Multiplications......Page 70
3.2.4 MergeSort......Page 72
3.2.5 QuickSort......Page 73
3.2.6 HeapSort......Page 75
3.2.7 RadixSort......Page 78
3.2.8 Binary Search......Page 80
3.2.9 Finding the......Page 81
3.2.10 Search Trees......Page 84
3.2.10.1 Finding an Element in a Search Tree......Page 85
3.2.10.2 Inserting an Element into a Search Tree......Page 86
3.2.10.3 Deleting an Element from a Search Tree......Page 87
3.2.11.1 Finding an Element in an AVL Tree......Page 89
3.2.11.2 Inserting an Element into an AVL Tree......Page 90
3.2.11.3 Deleting an Element from an AVL Tree......Page 96
3.2.12 Hashing......Page 97
3.2.13 Graph Algorithms......Page 100
3.2.13.1 Depth- First Search......Page 101
3.2.13.2 Breadth- First Search......Page 102
3.2.13.3 DijkstraÌs Algorithm......Page 104
Bibliographical Notes......Page 105
Exercise 2......Page 106
Exercise 5......Page 107
Exercise 8......Page 108
Exercise 11......Page 109
Exercise 12......Page 110
Part 2. The Software Side: Disappointments and How to Avoid Them......Page 111
4.1 Incorrect Software......Page 115
4.2 Performance Discrepancies......Page 117
4.3 Unpredictability......Page 121
4.4 Infeasibility and Impossibility......Page 123
4.5 Conclusion......Page 125
Bibliographical Notes......Page 126
Exercise 3......Page 127
Exercise 6......Page 128
About This Chapter......Page 129
5.1 The Influence of Virtual Memory Management......Page 130
5.2 The Case of Caches......Page 135
5.3 Testing and Profiling......Page 136
5.4 What to Do about It......Page 137
Bibliographical Notes......Page 148
Exercise 1......Page 149
Exercise 4......Page 150
6.1 Introduction......Page 152
6.2 Recursion and Space Complexity......Page 153
6.3 Dynamic Structures and Garbage Collection......Page 156
6.4 Parameter- Passing Mechanisms......Page 161
6.5 Memory Mappings......Page 165
6.6.1 Initialization......Page 166
6.6.2 Packed Data Structures......Page 168
6.6.3 Overspecification of Execution Order......Page 169
6.7.1 Interference with Specific Statements......Page 170
6.7.2 Lazy Evaluation......Page 171
6.9 What to Do about It......Page 173
Bibliographical Notes......Page 174
Exercise 2......Page 175
Exercise 3......Page 176
7.1 Handling Exceptional Situations......Page 177
7.1.1 Exception Handling......Page 178
7.1.2 Initializing Function Calls......Page 179
7.2 Testing for Fundamental Requirements......Page 181
Bibliographical Notes......Page 184
Exercise 3......Page 185
8.1 Bit and Word Complexity Revisited......Page 186
8.2 Testing for Equality......Page 189
8.3 Mathematical Properties......Page 192
8.4 Convergence......Page 194
Bibliographical Notes......Page 195
Exercise 4......Page 196
9.1 Introduction......Page 198
9.2 The Importance of Hidden Constants......Page 199
9.3 Crossover Points......Page 202
9.4 Practical Considerations for Efficient Software: What Matters and What Does Not......Page 205
Bibliographical Notes......Page 206
Exercise 2......Page 207
10.1 Introduction......Page 208
10.2 Undecidability......Page 210
10.3 Infeasibility......Page 212
10.4 NP- Completeness......Page 216
10.5 Practical Considerations......Page 217
Bibliographical Notes......Page 218
Exercise 2......Page 219
Exercise 3......Page 220
Part 3. Conclusion......Page 221
Appendix I: Algorithms Every Programmer Should Know......Page 224
Bibliographical Notes......Page 230
II. 2 The Memory Hierarchy......Page 231
II. 3 Virtual Memory Management......Page 233
II. 4 Optimizing Compilers......Page 234
II. 4.2 Data Flow Analysis......Page 235
II. 4.4 Data Dependence Analysis......Page 236
II. 4.6 I/ O Issues......Page 237
II. 5 Garbage Collection......Page 238
Bibliographical Notes......Page 240
III. 2 NP- Completeness......Page 242
III. 3 Higher Complexity Classes......Page 245
Bibliographical Notes......Page 246
IV. 2 The Halting Problem for Turing Machines......Page 247
IV. 3 PostÌs Correspondence Problem......Page 249
Bibliographical Note......Page 250
Bibliography......Page 251