Data Structures and Algorithm Analysis - Virginia Tech

1 data Structures and Algorithm Analysis Edition (Java Version). Clifford A. Shaffer Department of Computer Science Virginia tech Blacksburg, VA 24061. March 28, 2013. Update For a list of changes, see shaffer/ Copyright 2009-2012 by Clifford A. Shaffer. This document is made freely available in PDF form for educational and other non-commercial use. You may make copies of this file and redistribute in electronic form without charge. You may extract portions of this document provided that the front page, including the title, author, and this notice are included. Any commercial use of this document requires the written consent of the author. The author can be reached at If you wish to have a printed version of this document, print copies are published by Dover Publications (see ).

2 Further information about this text is available at shaffer/Book/. Contents Preface xiii I Preliminaries 1. 1 data Structures and Algorithms 3. A Philosophy of data Structures 4. The Need for data Structures 4. Costs and Benefits 6. Abstract data Types and data Structures 8. Design Patterns 12. Flyweight 13. Visitor 13. Composite 14. Strategy 15. Problems, Algorithms, and Programs 16. Further Reading 18. Exercises 20. 2 Mathematical Preliminaries 23. Sets and Relations 23. Miscellaneous Notation 27. Logarithms 29. Summations and Recurrences 30. Recursion 34. Mathematical Proof Techniques 36. iii iv Contents Direct Proof 37. Proof by Contradiction 37. Proof by Mathematical Induction 38. Estimation 44. Further Reading 45. Exercises 46.

3 3 Algorithm Analysis 53. Introduction 53. Best, Worst, and Average Cases 59. A Faster Computer, or a Faster Algorithm ? 60. Asymptotic Analysis 63. Upper Bounds 63. Lower Bounds 65. Notation 66. Simplifying Rules 67. Classifying Functions 68. Calculating the Running Time for a Program 69. Analyzing Problems 74. Common Misunderstandings 75. Multiple Parameters 77. Space Bounds 78. Speeding Up Your Programs 80. Empirical Analysis 83. Further Reading 84. Exercises 85. Projects 89. II Fundamental data Structures 91. 4 Lists, Stacks, and Queues 93. Lists 94. Array-Based List Implementation 97. Linked Lists 100. Comparison of List Implementations 108. Contents v Element Implementations 111. Doubly Linked Lists 112. Stacks 117. Array-Based Stacks 117.

4 Linked Stacks 120. Comparison of Array-Based and Linked Stacks 121. Implementing Recursion 121. Queues 125. Array-Based Queues 125. Linked Queues 128. Comparison of Array-Based and Linked Queues 131. Dictionaries 131. Further Reading 138. Exercises 138. Projects 141. 5 Binary Trees 145. Definitions and Properties 145. The Full Binary Tree Theorem 147. A Binary Tree Node ADT 149. Binary Tree Traversals 149. Binary Tree Node Implementations 154. Pointer-Based Node Implementations 154. Space Requirements 160. Array Implementation for Complete Binary Trees 161. Binary Search Trees 163. Heaps and Priority Queues 170. Huffman Coding Trees 178. Building Huffman Coding Trees 179. Assigning and Using Huffman Codes 185. Search in Huffman Trees 188.

5 Further Reading 188. Exercises 189. Projects 192. 6 Non-Binary Trees 195. vi Contents General Tree Definitions and Terminology 195. An ADT for General Tree Nodes 196. General Tree Traversals 197. The Parent Pointer Implementation 199. General Tree Implementations 206. List of Children 206. The Left-Child/Right-Sibling Implementation 206. Dynamic Node Implementations 207. Dynamic Left-Child/Right-Sibling Implementation 210. K-ary Trees 210. Sequential Tree Implementations 212. Further Reading 215. Exercises 215. Projects 218. III Sorting and Searching 221. 7 Internal Sorting 223. Sorting Terminology and Notation 224. Three (n2 ) Sorting Algorithms 225. Insertion Sort 225. Bubble Sort 227. Selection Sort 229. The Cost of Exchange Sorting 230.

6 Shellsort 231. Mergesort 233. Quicksort 236. Heapsort 243. Binsort and Radix Sort 244. An Empirical Comparison of Sorting Algorithms 251. Lower Bounds for Sorting 253. Further Reading 257. Exercises 257. Projects 261. Contents vii 8 File Processing and External Sorting 265. Primary versus Secondary Storage 265. Disk Drives 268. Disk Drive Architecture 268. Disk Access Costs 272. Buffers and Buffer Pools 274. The Programmer's View of Files 282. External Sorting 283. Simple Approaches to External Sorting 285. Replacement Selection 288. Multiway Merging 290. Further Reading 295. Exercises 295. Projects 299. 9 Searching 301. Searching Unsorted and Sorted Arrays 302. Self-Organizing Lists 307. Bit Vectors for Representing Sets 313.

7 Hashing 314. Hash Functions 315. Open Hashing 320. Closed Hashing 321. Analysis of Closed Hashing 331. Deletion 334. Further Reading 335. Exercises 336. Projects 338. 10 Indexing 341. Linear Indexing 343. ISAM 346. Tree-based Indexing 348. 2-3 Trees 350. B-Trees 355. B+ -Trees 358. viii Contents B-Tree Analysis 364. Further Reading 365. Exercises 365. Projects 367. IV Advanced data Structures 369. 11 Graphs 371. Terminology and Representations 372. Graph Implementations 376. Graph Traversals 380. Depth-First Search 383. Breadth-First Search 384. Topological Sort 384. Shortest-Paths Problems 388. Single-Source Shortest Paths 389. Minimum-Cost Spanning Trees 393. Prim's Algorithm 393. Kruskal's Algorithm 397. Further Reading 399.

8 Exercises 399. Projects 402. 12 Lists and Arrays Revisited 405. Multilists 405. Matrix Representations 408. Memory Management 412. Dynamic Storage Allocation 414. Failure Policies and Garbage Collection 421. Further Reading 425. Exercises 426. Projects 427. 13 Advanced Tree Structures 429. Tries 429. Contents ix Balanced Trees 434. The AVL Tree 435. The Splay Tree 437. Spatial data Structures 440. The K-D Tree 442. The PR quadtree 447. Other Point data Structures 451. Other Spatial data Structures 453. Further Reading 453. Exercises 454. Projects 455. V Theory of Algorithms 459. 14 Analysis Techniques 461. Summation Techniques 462. Recurrence Relations 467. Estimating Upper and Lower Bounds 467. Expanding Recurrences 470. Divide and Conquer Recurrences 472.

9 Average-Case Analysis of Quicksort 474. Amortized Analysis 476. Further Reading 479. Exercises 479. Projects 483. 15 Lower Bounds 485. Introduction to Lower Bounds Proofs 486. Lower Bounds on Searching Lists 488. Searching in Unsorted Lists 488. Searching in Sorted Lists 490. Finding the Maximum Value 491. Adversarial Lower Bounds Proofs 493. State Space Lower Bounds Proofs 496. Finding the ith Best Element 499. x Contents Optimal Sorting 501. Further Reading 504. Exercises 504. 507. 16 Patterns of Algorithms 509. Dynamic Programming 509. The Knapsack Problem 511. All-Pairs Shortest Paths 513. Randomized Algorithms 515. Randomized algorithms for finding large values 515. Skip Lists 516. Numerical Algorithms 522. Exponentiation 523.

10 Largest Common Factor 523. Matrix Multiplication 524. Random Numbers 526. The Fast Fourier Transform 527. Further Reading 532. Exercises 532. Projects 533. 17 Limits to Computation 535. Reductions 536. Hard Problems 541. The Theory of N P-Completeness 543. N P-Completeness Proofs 547. Coping with N P-Complete Problems 552. Impossible Problems 555. Uncountability 556. The Halting Problem Is Unsolvable 559. Further Reading 561. Exercises 562. Projects 564. Bibliography 567. Contents xi Index 573. Preface We study data Structures so that we can learn to write more efficient programs. But why must programs be efficient when new computers are faster every year? The reason is that our ambitions grow with our capabilities. Instead of rendering efficiency needs obsolete, the modern revolution in computing power and storage capability merely raises the efficiency stakes as we attempt more complex tasks.