A Programmer's Companion to Algorithm Analysis

Until now, no other book examined the gap between the theory of algorithms and the production of software programs. Focusing on practical issues, A Programmer's Companion to Algorithm Analysis carefully details the transition from the design and analysis of an algorithm to the resulting software program.Consisting of two main complementary parts, the book emphasizes the concrete aspects of translating an algorithm into software that should perform based on what the algorithm analysis indicated. In the first part, the author describes the idealized universe that algorithm designers inhabit while the second part outlines how this ideal can be adapted to the real world of programming. The book explores analysis techniques, including crossover points, the influence of the memory hierarchy, implications of programming language aspects, such as recursion, and problems arising from excessively high computational complexities of solution methods. It concludes with four appendices that discuss basic algorithms; memory hierarchy, virtual memory management, optimizing compilers, and garbage collection; NP-completeness and higher complexity classes; and undecidability in practical terms.Applying the theory of algorithms to the production of software, A Programmer's Companion to Algorithm Analysis fulfills the needs of software programmers and developers as well as students by showing that with the correct algorithm, you can achieve a functional software program.

Ernst L. Leiss is a professor in the department of computer science at the University of Houston, Texas, USA

Foreword

xiii

Part 1 The Algorithm Side: Regularity, Predictability, and Asymptotics

1 A Taxonomy of Algorithmic Complexity

3

(34)

1.1 Introduction

3

(2)

1.2 The Time and Space Complexities of an Algorithm

5

(4)

1.3 The Worst-, Average-, and Best-Case Complexities of an Algorithm

9

(3)

1.3.1 Scenario 1

11

(1)

1.3.2 Scenario 2

12

(1)

1.4 Bit versus Word Complexity

12

(3)

1.5 Parallel Complexity

15

(2)

1.6 I/O Complexity

17

(5)

1.6.1 Scenario 1

18

(2)

1.6.2 Scenario 2

20

(2)

1.7 On-Line versus Off-Line Algorithms

22

(2)

1.8 Amortized Analysis

24

(1)

1.9 Lower Bounds and Their Significance

24

(6)

1.10 Conclusion

30

(1)

Bibliographical Notes

30

(1)

Exercises

31

(6)

2 Fundamental Assumptions Underlying Algorithmic Complexity

37

(12)

2.1 Introduction

37

(1)

2.2 Assumptions Inherent in the Determination of Statement Counts

38

(6)

2.3 All Mathematical Identities Hold

44

(1)

2.4 Revisiting the Asymptotic Nature of Complexity Analysis

45

(1)

2.5 Conclusion

46

(1)

Bibliographical Notes

47

(1)

Exercises

47

(2)

3 Examples of Complexity Analysis

49

(54)

3.1 General Techniques for Determining Complexity

49

(4)

3.2 Selected Examples: Determining the Complexity of Standard Algorithms

53

(39)

3.2.1 Multiplying Two m-Bit Numbers

54

(1)

3.2.2 Multiplying Two Square Matrices

55

(2)

3.2.3 Optimally Sequencing Matrix Multiplications

57

(2)

3.2.4 MergeSort

59

(1)

3.2.5 QuickSort

60

(2)

3.2.6 HeapSort

62

(3)

3.2.7 RadixSort

65

(2)

3.2.8 Binary Search

67

(1)

3.2.9 Finding the Kth Largest Element

68

(3)

3.2.10 Search Trees

71

(5)

3.2.10.1 Finding an Element in a Search Tree

72

(1)

3.2.10.2 Inserting an Element into a Search Tree

73

(1)

3.2.10.3 Deleting an Element from a Search Tree

74

(2)

3.2.10.4 Traversing a Search Tree

76

(1)

3.2.11 AVL Trees

76

(8)

3.2.11.1 Finding an Element in an AVL Tree

76

(1)

3.2.11.2 Inserting an Element into an AVL Tree

77

(6)

3.2.11.3 Deleting an Element from an AVL Tree

83

(1)

3.2.12 Hashing

84

(3)

3.2.13 Graph Algorithms

87

(68)

3.2.13.1 Depth-First Search

88

(1)

3.2.13.2 Breadth-First Search

89

(2)

3.2.13.3 Dijkstra's Algorithm

91

(1)

3.3 Conclusion

92

(1)

Bibliographical Notes

92

(1)

Exercises

93

(10)

Part 2 The Software Side: Disappointments and How to Avoid Them

4 Sources of Disappointments

103

(14)

4.1 Incorrect Software

103

(2)

4.2 Performance Discrepancies

105

(4)

4.3 Unpredictability

109

(2)

4.4 Infeasibility and Impossibility

111

(2)

4.5 Conclusion

113

(1)

Bibliographical Notes

114

(1)

Exercises

115

(2)

5 Implications of Nonuniform Memory for Software

117

(24)

5.1 The Influence of Virtual Memory Management

118

(5)

5.2 The Case of Caches

123

(1)

5.3 Testing and Profiling

124

(1)

5.4 What to Do about It

125

(11)

Bibliographical Notes

136

(1)

Exercises

137

(4)

6 Implications of Compiler and Systems Issues for Software

141

(26)

6.1 Introduction

141

(1)

6.2 Recursion and Space Complexity

142

(3)

6.3 Dynamic Structures and Garbage Collection

145

(5)

6.4 Parameter-Passing Mechanisms

150

(5)

6.5 Memory Mappings

155

(1)

6.6 The Influence of Language Properties

155

(5)

6.6.1 Initialization

155

(2)

6.6.2 Packed Data Structures

157

(1)

6.6.3 Overspecification of Execution Order

158

(1)

6.6.4 Avoiding Range Checks

159

(1)

6.7 The Influence of Optimization

160

(2)

6.7.1 Interference with Specific Statements

160

(1)

6.7.2 Lazy Evaluation

161

(1)

6.8 Parallel Processes

162

(1)

6.9 What to Do about It

163

(1)

Bibliographical Notes

164

(1)

Exercises

164

(3)

7 Implicit Assumptions

167

(10)

7.1 Handling Exceptional Situations

167

(4)

7.1.1 Exception Handling

168

(1)

7.1.2 Initializing Function Calls

169

(2)

7.2 Testing for Fundamental Requirements

171

(3)

7.3 What to Do about It

174

(1)

Bibliographical Notes

174

(1)

Exercises

175

(2)

8 Implications of the Finiteness of the Representation of Numbers

177

(12)

8.1 Bit and Word Complexity Revisited

177

(3)

8.2 Testing for Equality

180

(3)

8.3 Mathematical Properties

183

(2)

8.4 Convergence

185

(1)

8.5 What to Do about It

186

(1)

Bibliographical Notes

186

(1)

Exercises

187

(2)

9 Asymptotic Complexities and the Selection of Algorithms

189

(10)

9.1 Introduction

189

(1)

9.2 The Importance of Hidden Constants

190

(3)

9.3 Crossover Points

193

(3)

9.4 Practical Considerations for Efficient Software: What Matters and What Does Not

196

(1)

Bibliographical Notes

197

(1)

Exercises

198

(1)

10 Infeasibility and Undecidability: Implications for Software Development

199

(1)

10.1 Introduction

199

(2)

10.2 Undecidability

201

(2)

10.3 Infeasibility

203

(4)

10.4 NP-Completeness

207

(1)

10.5 Practical Considerations

208

(1)

Bibliographical Notes

209

(1)

Exercises

210

(7)

Part 3 Conclusion

Appendix I: Algorithms Every Programmer Should Know

217

(30)

Bibliographical Notes

223

(2)

Appendix II: Overview of Systems Implicated in Program Analysis

225

(1)

II.1 Introduction

225

(1)

II.2 The Memory Hierarchy

225

(2)

II.3 Virtual Memory Management

227

(1)

II.4 Optimizing Compilers

228

(4)

II.4.1 Basic Optimizations

229

(1)

II.4.2 Data Flow Analysis

229

(1)

II.4.3 Interprocedural Optimizations

230

(1)

II.4.4 Data Dependence Analysis

230

(1)

II.4.5 Code Transformations

231

(1)

II.4.6 I/O Issues

231

(1)

II.5 Garbage Collection

232

(2)

Bibliographical Notes

234

(3)

Appendix III: NP-Completeness and Higher Complexity Classes

237

(1)

III.1 Introduction

237

(1)

III.2 NP-Completeness

237

(3)

III.3 Higher Complexity Classes

240

(1)

Bibliographical Notes

241

(2)

Appendix IV: Review of Undecidability

243

(1)

IV.1 Introduction

243

(1)

IV.2 The Halting Problem for Turing Machines

243

(2)

IV.3 Post's Correspondence Problem

245

(1)

Bibliographical Note

246

(1)

Bibliography

247

(4)

Index

251

What is included with this book?

The New copy of this book will include any supplemental materials advertised. Please check the title of the book to determine if it should include any access cards, study guides, lab manuals, CDs, etc.

The Used, Rental and eBook copies of this book are not guaranteed to include any supplemental materials. Typically, only the book itself is included. This is true even if the title states it includes any access cards, study guides, lab manuals, CDs, etc.

FREE SHIPPING

Amazon no longer offers textbook rentals. We do!

A Programmer's Companion to Algorithm Analysis

Summary

Author Biography

Table of Contents

Supplemental Materials