Coverart for item
The Resource Data structures & algorithm analysis in Java, Clifford A. Shaffer

Data structures & algorithm analysis in Java, Clifford A. Shaffer

Label
Data structures & algorithm analysis in Java
Title
Data structures & algorithm analysis in Java
Statement of responsibility
Clifford A. Shaffer
Title variation
Data structures and algorithm analysis in Java
Creator
Contributor
Subject
Language
eng
Summary
" A comprehensive treatment that focuses on how to create efficient data structures and algorithms, this text helps readers understand how to select or design the data structure that will best solve a specific problem. Utilizing Java as the programming language, this edition is suitable for second-year data structure courses and computer science courses in algorithmic analysis"--Provided by publisher
Cataloging source
DLC
http://library.link/vocab/creatorName
Shaffer, Clifford A
Illustrations
illustrations
Index
index present
Literary form
non fiction
Nature of contents
bibliography
http://library.link/vocab/relatedWorkOrContributorName
Shaffer, Clifford A
http://library.link/vocab/subjectName
  • Data structures (Computer science)
  • Computer algorithms
  • Java (Computer program language)
Label
Data structures & algorithm analysis in Java, Clifford A. Shaffer
Instantiates
Publication
Note
Rev. ed. of: A practical introduction to data structures and algorithm analysis / Clifford A. Shaffer. Java ed. 1998
Bibliography note
Includes bibliographical references and index
Contents
I. Preliminaries -- 1. Data Structures and Algorithms -- 1.1. A Philosophy of Data Structures -- 1.1.1. The Need for Data Structures -- 1.1.2. Costs and Benefits -- 1.2. Abstract Data Types and Data Structures -- 1.3. Design Patterns -- 1.3.1. Flyweight -- 1.3.2. Visitor -- 1.3.3. Composite -- 1.3.4. Strategy -- 1.4. Problems, Algorithms, and Programs -- 1.5. Further Reading -- 1.6. Exercises -- 2. Mathematical Preliminaries -- 2.1. Sets and Relations -- 2.2. Miscellaneous Notation -- 2.3. Logarithms -- 2.4. Summations and Recurrences -- 2.5. Recursion -- 2.6. Mathematical Proof Techniques -- 2.6.1. Direct Proof -- 2.6.2. Proof by Contradiction -- 2.6.3. Proof by Mathematical Induction -- 2.7. Estimation -- 2.8. Further Reading -- 2.9. Exercises -- 3. Algorithm Analysis -- 3.1. Introduction -- 3.2. Best, Worst, and Average Cases -- 3.3. A Faster Computer, or a Faster Algorithm? -- 3.4. Asymptotic Analysis -- 3.4.1. Upper Bounds -- 3.4.2. Lower Bounds -- 3.4.3. O Notation -- 3.4.4. Simplifying Rules -- 3.4.5. Classifying Functions -- 3.5. Calculating the Running Time for a Program -- 3.6. Analyzing Problems -- 3.7. Common Misunderstandings -- 3.8. Multiple Parameters -- 3.9. Space Bounds -- 3.10. Speeding Up Your Programs -- 3.11. Empirical Analysis -- 3.12. Further Reading -- 3.13. Exercises -- 3.14. Projects -- II. Fundamental Data Structures -- 4. Lists, Stacks, and Queues -- 4.1. Lists -- 4.1.1. Array-B ased List Implementation -- 4.1.2. Linked Lists -- 4.1.3. Comparison of List Implementations -- 4.1.4. Element Implementations -- 4.1.5. Doubly Linked Lists -- 4.2. Stacks -- 4.2.1. Array-Based Stacks -- 4.2.2. Linked Stacks -- 4.2.3. Comparison of Array-Based and Linked Stacks -- 4.2.4. Implementing Recursion -- 4.3. Queues -- 4.3.1. Array-Based Queues -- 4.3.2. Linked Queues -- 4.3.3. Comparison of Array-Based and Linked Queues -- 4.4. Dictionaries -- 4.5. Further Reading -- 4.6. Exercises -- 4.7. Projects -- 5. Binary Trees -- 5.1. Definitions and Properties -- 5.1.1. The Full Binary Tree Theorem -- 5.1.2. A Binary Tree Node ADT -- 5.2. Binary Tree Traversals -- 5.3. Binary Tree Node Implementations -- 5.3.1. Pointer-Based Node Implementations -- 5.3.2. Space Requirements -- 5.3.3. Array Implementation for Complete Binary Trees -- 5.4. Binary Search Trees -- 5.5. Heaps and Priority Queues -- 5.6. Huffman Coding Trees -- 5.6.1. Building Huffman Coding Trees -- 5.6.2. Assigning and Using Huffman Codes -- 5.6.3. Search in Huffman Trees -- 5.7. Further Reading -- 5.8. Exercises -- 5.9. Projects -- 6. Non-Binary Trees -- 6.1. General Tree Definitions and Terminology -- 6.1.1. An ADT for General Tree Nodes -- 6.1.2. General Tree Traversals -- 6.2. The Parent Pointer Implementation -- 6.3. General Tree Implementations -- 6.3.1. List of Children -- 6.3.2. The Left-Child/Right-Sibling Implementation -- 6.3.3. Dynamic Node Implementations -- 6.3.4. Dynamic "Left-Child/Right-Sibling" Implementation -- 6.4. K-ary Trees -- 6.5. Sequential Tree Implementations -- 6.6. Further Reading -- 6.7. Exercises -- 6.8. Projects -- III. Sorting and Searching -- 7. Internal Sorting -- 7.1. Sorting Terminology and Notation -- 7.2. Three o(n2) Sorting Algorithms -- 7.2.1. Insertion Sort -- 7.2.2. Bubble Sort -- 7.2.3. Selection Sort -- 7.2.4. The Cost of Exchange Sorting -- 7.3. Shellsort -- 7.4. Mergesort -- 7.5. Quicksort -- 7.6. Heapsort -- 7.7. Binsort and Radix Sort -- 7.8. An Empirical Comparison of Sorting Algorithms -- 7.9. Lower Bounds for Sorting -- 7.10. Further Reading -- 7.11. Exercises -- 7.12. Projects -- 8. File Processing and External Sorting -- 8.1. Primary versus Secondary Storage -- 8.2. Disk Drives -- 8.2.1. Disk Drive Architecture -- 8.2.2. Disk Access Costs -- 8.3. Buffers and Buffer Pools -- 8.4. The Programmer's View of Files -- 8.5. External Sorting -- 8.5.1. Simple Approaches to External Sorting -- 8.5.2. Replacement Selection -- 8.5.3. Multiway Merging -- 8.6. Further Reading -- 8.7. Exercises -- 8.8. Projects -- 9. Searching -- 9.1. Searching Unsorted and Sorted Arrays -- 9.2. Self-Organizing Lists -- 9.3. Bit Vectors for Representing Sets -- 9.4. Hashing -- 9.4.1. Hash Functions -- 9.4.2. Open Hashing -- 9.4.3. Closed Hashing -- 9.4.4. Analysis of Closed Hashing -- 9.4.5. Deletion -- 9.5. Further Reading -- 9.6. Exercises -- 9.7. Projects -- 10. Indexing -- 10.1. Linear Indexing -- 10.2. ISAM -- 10.3. Tree-based Indexing -- 10.4. 2-3 Trees -- 10.5. B-Trees -- 10.5.1. B+-Trees -- 10.5.2. B-Tree Analysis -- 10.6. Further Reading -- 10.7. Exercises -- 10.8. Projects -- IV. Advanced Data Structures -- 11. Graphs -- 11.1. Terminology and Representations -- 11.2. Graph Implementations -- 11.3. Graph Traversals -- 11.3.1. Depth-First Search -- 11.3.2. Breadth-First Search -- 11.3.3. Topological Sort -- 11.4. Shortest-Paths Problems -- 11.4.1. Single-Source Shortest Paths -- 11.5. Minimum-Cost Spanning Trees -- 11.5.1. Prim's Algorithm -- 11.5.2. Kruskal's Algorithm -- 11.6. Further Reading -- 11.7. Exercises -- 11.8. Projects -- 12. Lists and Arrays Revisited -- 12.1. Multilists -- 12.2. Matrix Representations -- 12.3. Memory Management -- 12.3.1. Dynamic Storage Allocation -- 12.3.2. Failure Policies and Garbage Collection -- 12.4. Further Reading -- 12.5. Exercises -- 12.6. Projects -- 13. Advanced Tree Structures -- 13.1. Tries -- 13.2. Balanced Trees -- 13.2.1. The AVL Tree -- 13.2.2. The Splay Tree -- 13.3. Spatial Data Structures -- 13.3.1. The K-D Tree -- 13.3.2. The PR quadtree -- 13.3.3. Other Point Data Structures -- 13.3.4. Other Spatial Data Structures -- 13.4. Further Reading -- 13.5. Exercises -- 13.6. Projects -- V. Theory of Algorithms -- 14. Analysis Techniques -- 14.1. Summation Techniques -- 14.2. Recurrence Relations -- 14.2.1. Estimating Upper and Lower Bounds -- 14.2.2. Expanding Recurrences -- 14.2.3. Divide and Conquer Recurrences -- 14.2.4. Average-Case Analysis of Quicksort -- 14.3. Amortized Analysis -- 14.4. Further Reading -- 14.5. Exercises -- 14.6. Projects -- 15. Lower Bounds -- 15.1. Introduction to Lower Bounds Proofs -- 15.2. Lower Bounds on Searching Lists -- 15.2.1. Searching in Unsorted Lists -- 15.2.2. Searching in Sorted Lists -- 15.3. Finding the Maximum Value -- 15.4. Adversarial Lower Bounds Proofs -- 15.5. State Space Lower Bounds Proofs -- 15.6. Finding the zth Best Element -- 15.7. Optimal Sorting -- 15.8. Further Reading -- 15.9. Exercises -- 15.10. Projects -- 16. Patterns of Algorithms -- 16.1. Dynamic Programming -- 16.1.1. The Knapsack Problem -- 16.1.2. All-Pairs Shortest Paths -- 16.2. Randomized Algorithms -- 16.2.1. Randomized algorithms for finding large values -- 16.2.2. Skip Lists -- 16.3. Numerical Algorithms -- 16.3.1. Exponentiation -- 16.3.2. Largest Common Factor -- 16.3.3. Matrix Multiplication -- 16.3.4. Random Numbers -- 16.3.5. The Fast Fourier Transform -- 16.4. Further Reading -- 16.5. Exercises -- 16.6. Projects -- 17. Limits to Computation -- 17.1. Reductions -- 17.2. Hard Problems -- 17.2.1. The Theory of NP-Completeness -- 17.2.2. NP-Completeness Proofs -- 17.2.3. Coping with NP-Complete Problems -- 17.3. Impossible Problems -- 17.3.1. Uncountability -- 17.3.2. The Halting Problem Is Unsolvable -- 17.4. Further Reading -- 17.5. Exercises -- 17.6. Projects
Control code
ocn721884651
Dimensions
26 cm
Edition
3rd ed., Dover ed
Extent
xix, 582 p.
Isbn
9780486485812
Isbn Type
(pbk.)
Lccn
2011020237
Other physical details
ill.
System control number
(OCoLC)721884651
Label
Data structures & algorithm analysis in Java, Clifford A. Shaffer
Publication
Note
Rev. ed. of: A practical introduction to data structures and algorithm analysis / Clifford A. Shaffer. Java ed. 1998
Bibliography note
Includes bibliographical references and index
Contents
I. Preliminaries -- 1. Data Structures and Algorithms -- 1.1. A Philosophy of Data Structures -- 1.1.1. The Need for Data Structures -- 1.1.2. Costs and Benefits -- 1.2. Abstract Data Types and Data Structures -- 1.3. Design Patterns -- 1.3.1. Flyweight -- 1.3.2. Visitor -- 1.3.3. Composite -- 1.3.4. Strategy -- 1.4. Problems, Algorithms, and Programs -- 1.5. Further Reading -- 1.6. Exercises -- 2. Mathematical Preliminaries -- 2.1. Sets and Relations -- 2.2. Miscellaneous Notation -- 2.3. Logarithms -- 2.4. Summations and Recurrences -- 2.5. Recursion -- 2.6. Mathematical Proof Techniques -- 2.6.1. Direct Proof -- 2.6.2. Proof by Contradiction -- 2.6.3. Proof by Mathematical Induction -- 2.7. Estimation -- 2.8. Further Reading -- 2.9. Exercises -- 3. Algorithm Analysis -- 3.1. Introduction -- 3.2. Best, Worst, and Average Cases -- 3.3. A Faster Computer, or a Faster Algorithm? -- 3.4. Asymptotic Analysis -- 3.4.1. Upper Bounds -- 3.4.2. Lower Bounds -- 3.4.3. O Notation -- 3.4.4. Simplifying Rules -- 3.4.5. Classifying Functions -- 3.5. Calculating the Running Time for a Program -- 3.6. Analyzing Problems -- 3.7. Common Misunderstandings -- 3.8. Multiple Parameters -- 3.9. Space Bounds -- 3.10. Speeding Up Your Programs -- 3.11. Empirical Analysis -- 3.12. Further Reading -- 3.13. Exercises -- 3.14. Projects -- II. Fundamental Data Structures -- 4. Lists, Stacks, and Queues -- 4.1. Lists -- 4.1.1. Array-B ased List Implementation -- 4.1.2. Linked Lists -- 4.1.3. Comparison of List Implementations -- 4.1.4. Element Implementations -- 4.1.5. Doubly Linked Lists -- 4.2. Stacks -- 4.2.1. Array-Based Stacks -- 4.2.2. Linked Stacks -- 4.2.3. Comparison of Array-Based and Linked Stacks -- 4.2.4. Implementing Recursion -- 4.3. Queues -- 4.3.1. Array-Based Queues -- 4.3.2. Linked Queues -- 4.3.3. Comparison of Array-Based and Linked Queues -- 4.4. Dictionaries -- 4.5. Further Reading -- 4.6. Exercises -- 4.7. Projects -- 5. Binary Trees -- 5.1. Definitions and Properties -- 5.1.1. The Full Binary Tree Theorem -- 5.1.2. A Binary Tree Node ADT -- 5.2. Binary Tree Traversals -- 5.3. Binary Tree Node Implementations -- 5.3.1. Pointer-Based Node Implementations -- 5.3.2. Space Requirements -- 5.3.3. Array Implementation for Complete Binary Trees -- 5.4. Binary Search Trees -- 5.5. Heaps and Priority Queues -- 5.6. Huffman Coding Trees -- 5.6.1. Building Huffman Coding Trees -- 5.6.2. Assigning and Using Huffman Codes -- 5.6.3. Search in Huffman Trees -- 5.7. Further Reading -- 5.8. Exercises -- 5.9. Projects -- 6. Non-Binary Trees -- 6.1. General Tree Definitions and Terminology -- 6.1.1. An ADT for General Tree Nodes -- 6.1.2. General Tree Traversals -- 6.2. The Parent Pointer Implementation -- 6.3. General Tree Implementations -- 6.3.1. List of Children -- 6.3.2. The Left-Child/Right-Sibling Implementation -- 6.3.3. Dynamic Node Implementations -- 6.3.4. Dynamic "Left-Child/Right-Sibling" Implementation -- 6.4. K-ary Trees -- 6.5. Sequential Tree Implementations -- 6.6. Further Reading -- 6.7. Exercises -- 6.8. Projects -- III. Sorting and Searching -- 7. Internal Sorting -- 7.1. Sorting Terminology and Notation -- 7.2. Three o(n2) Sorting Algorithms -- 7.2.1. Insertion Sort -- 7.2.2. Bubble Sort -- 7.2.3. Selection Sort -- 7.2.4. The Cost of Exchange Sorting -- 7.3. Shellsort -- 7.4. Mergesort -- 7.5. Quicksort -- 7.6. Heapsort -- 7.7. Binsort and Radix Sort -- 7.8. An Empirical Comparison of Sorting Algorithms -- 7.9. Lower Bounds for Sorting -- 7.10. Further Reading -- 7.11. Exercises -- 7.12. Projects -- 8. File Processing and External Sorting -- 8.1. Primary versus Secondary Storage -- 8.2. Disk Drives -- 8.2.1. Disk Drive Architecture -- 8.2.2. Disk Access Costs -- 8.3. Buffers and Buffer Pools -- 8.4. The Programmer's View of Files -- 8.5. External Sorting -- 8.5.1. Simple Approaches to External Sorting -- 8.5.2. Replacement Selection -- 8.5.3. Multiway Merging -- 8.6. Further Reading -- 8.7. Exercises -- 8.8. Projects -- 9. Searching -- 9.1. Searching Unsorted and Sorted Arrays -- 9.2. Self-Organizing Lists -- 9.3. Bit Vectors for Representing Sets -- 9.4. Hashing -- 9.4.1. Hash Functions -- 9.4.2. Open Hashing -- 9.4.3. Closed Hashing -- 9.4.4. Analysis of Closed Hashing -- 9.4.5. Deletion -- 9.5. Further Reading -- 9.6. Exercises -- 9.7. Projects -- 10. Indexing -- 10.1. Linear Indexing -- 10.2. ISAM -- 10.3. Tree-based Indexing -- 10.4. 2-3 Trees -- 10.5. B-Trees -- 10.5.1. B+-Trees -- 10.5.2. B-Tree Analysis -- 10.6. Further Reading -- 10.7. Exercises -- 10.8. Projects -- IV. Advanced Data Structures -- 11. Graphs -- 11.1. Terminology and Representations -- 11.2. Graph Implementations -- 11.3. Graph Traversals -- 11.3.1. Depth-First Search -- 11.3.2. Breadth-First Search -- 11.3.3. Topological Sort -- 11.4. Shortest-Paths Problems -- 11.4.1. Single-Source Shortest Paths -- 11.5. Minimum-Cost Spanning Trees -- 11.5.1. Prim's Algorithm -- 11.5.2. Kruskal's Algorithm -- 11.6. Further Reading -- 11.7. Exercises -- 11.8. Projects -- 12. Lists and Arrays Revisited -- 12.1. Multilists -- 12.2. Matrix Representations -- 12.3. Memory Management -- 12.3.1. Dynamic Storage Allocation -- 12.3.2. Failure Policies and Garbage Collection -- 12.4. Further Reading -- 12.5. Exercises -- 12.6. Projects -- 13. Advanced Tree Structures -- 13.1. Tries -- 13.2. Balanced Trees -- 13.2.1. The AVL Tree -- 13.2.2. The Splay Tree -- 13.3. Spatial Data Structures -- 13.3.1. The K-D Tree -- 13.3.2. The PR quadtree -- 13.3.3. Other Point Data Structures -- 13.3.4. Other Spatial Data Structures -- 13.4. Further Reading -- 13.5. Exercises -- 13.6. Projects -- V. Theory of Algorithms -- 14. Analysis Techniques -- 14.1. Summation Techniques -- 14.2. Recurrence Relations -- 14.2.1. Estimating Upper and Lower Bounds -- 14.2.2. Expanding Recurrences -- 14.2.3. Divide and Conquer Recurrences -- 14.2.4. Average-Case Analysis of Quicksort -- 14.3. Amortized Analysis -- 14.4. Further Reading -- 14.5. Exercises -- 14.6. Projects -- 15. Lower Bounds -- 15.1. Introduction to Lower Bounds Proofs -- 15.2. Lower Bounds on Searching Lists -- 15.2.1. Searching in Unsorted Lists -- 15.2.2. Searching in Sorted Lists -- 15.3. Finding the Maximum Value -- 15.4. Adversarial Lower Bounds Proofs -- 15.5. State Space Lower Bounds Proofs -- 15.6. Finding the zth Best Element -- 15.7. Optimal Sorting -- 15.8. Further Reading -- 15.9. Exercises -- 15.10. Projects -- 16. Patterns of Algorithms -- 16.1. Dynamic Programming -- 16.1.1. The Knapsack Problem -- 16.1.2. All-Pairs Shortest Paths -- 16.2. Randomized Algorithms -- 16.2.1. Randomized algorithms for finding large values -- 16.2.2. Skip Lists -- 16.3. Numerical Algorithms -- 16.3.1. Exponentiation -- 16.3.2. Largest Common Factor -- 16.3.3. Matrix Multiplication -- 16.3.4. Random Numbers -- 16.3.5. The Fast Fourier Transform -- 16.4. Further Reading -- 16.5. Exercises -- 16.6. Projects -- 17. Limits to Computation -- 17.1. Reductions -- 17.2. Hard Problems -- 17.2.1. The Theory of NP-Completeness -- 17.2.2. NP-Completeness Proofs -- 17.2.3. Coping with NP-Complete Problems -- 17.3. Impossible Problems -- 17.3.1. Uncountability -- 17.3.2. The Halting Problem Is Unsolvable -- 17.4. Further Reading -- 17.5. Exercises -- 17.6. Projects
Control code
ocn721884651
Dimensions
26 cm
Edition
3rd ed., Dover ed
Extent
xix, 582 p.
Isbn
9780486485812
Isbn Type
(pbk.)
Lccn
2011020237
Other physical details
ill.
System control number
(OCoLC)721884651

Library Locations

    • Wellington LibraryBorrow it
      Wellington- Massey University Library, Block 5, 63 Wallace Street, Wellington, 6021, NZ
      -40.385395 175.617407
Processing Feedback ...