Data structures & algorithm analysis in Java
By: Mark Allen Weiss.
Edition: 2nd ed.
Publisher: Addison-Wesley; Peason Addison-Wesley
Published: 2006
Place of publication: Boston
Language: eng
Number of pages: 555
Subjects: Java (Computer program language); Data structures (Computer science); Computer algorithms.
Other titles: Data structures and algorithm analysis in Java
Notes: Includes bibliographical references and index.
Table of contents: title: Preface
pagenum: XV; label: Chapter 1
title: Introduction
pagenum: 1; label: 1.1
title: What's the Book About?
pagenum: 1; label: 1.2
title: Mathematics Review
pagenum: 2; label: 1.2.1
title: Exponents
pagenum: 3; label: 1.2.2
title: Logarithms
pagenum: 3; label: 1.2.3
title: Series
pagenum: 4; label: 1.2.4
title: Modular Arithmetic
pagenum: 5; label: 1.2.5
title: The P Word
pagenum: 6; label: 1.3
title: A Brief Introduction to Recursion
pagenum: 7; label: 1.4
title: Implementing Generic Components Pre Java 5
pagenum: 11; label: 1.4.1
title: Using Object for Genericity
pagenum: 12; label: 1.4.2
title: Wrappers for Primitive Types
pagenum: 12; label: 1.4.3
title: Using Interface Types for Genericity
pagenum: 13; label: 1.4.4
title: Compatibility of Array Types
pagenum: 15; label: 1.5
title: Implementing Generic Components Using Java 5 Generics
pagenum: 16; label: 1.5.1
title: Simple Generic Classes and Interfaces
pagenum: 16; label: 1.5.2
title: Autoboxing/Unboxing
pagenum: 17; label: 1.5.3
title: Wildcards with Bounds
pagenum: 18; label: 1.5.4
title: Generic Static Methods
pagenum: 19; label: 1.5.5
title: Type Bounds
pagenum: 20; label: 1.5.6
title: Type Erasure
pagenum: 21; label: 1.5.7
title: Restrictions on Generics
pagenum: 22; label: 1.6
title: Function Objects
pagenum: 23; title: Summary
pagenum: 25; title: Exercises
pagenum: 25; title: References
pagenum: 26; label: Chapter 2
title: Algorithm Analysis
pagenum: 29; label: 2.1
title: Mathematical Background
pagenum: 29; label: 2.2
title: Model
pagenum: 32; label: 2.3
title: What to Analyze
pagenum: 32; label: 2.4
title: Running Time Calculations
pagenum: 35; label: 2.4.1
title: A Simple Example
pagenum: 35; label: 2.4.2
title: General Rules
pagenum: 36; label: 2.4.3
title: Solutions for the Maximum Subsequence Sum Problem
pagenum: 38; label: 2.4.4
title: Logarithms in the Running Time
pagenum: 44; label: 2.4.5
title: Checking Your Analysis
pagenum: 48; label: 2.4.6
title: A Grain of Salt
pagenum: 48; title: Summary
pagenum: 50; title: Exercises
pagenum: 50; title: References
pagenum: 55; label: Chapter 3
title: Lists, Stacks, and Queues
pagenum: 57; label: 3.1
title: Abstract Data Types (ADTs)
pagenum: 57; label: 3.2
title: The List ADT
pagenum: 58; label: 3.2.1
title: Simple Array Implementation of Lists
pagenum: 58; label: 3.2.2
title: Simple Linked Lists
pagenum: 59; label: 3.3
title: Lists in the Java Collections API
pagenum: 60; label: 3.3.1
title: Collection Interface
pagenum: 61; label: 3.3.2
title: Iterators
pagenum: 62; label: 3.3.3
title: The List Interface, ArrayList, and LinkedList
pagenum: 63; label: 3.3.4
title: Example: Using remove on a LinkedList
pagenum: 65; label: 3.3.5
title: ListIterators
pagenum: 66; label: 3.4
title: Implementation of ArrayList
pagenum: 67; label: 3.4.1
title: The Basic Class
pagenum: 68; label: 3.4.2
title: The Iterator and Java Nested and Inner Classes
pagenum: 68; label: 3.5
title: Implementation of LinkedList
pagenum: 75; label: 3.6
title: The Stack ADT
pagenum: 82; label: 3.6.1
title: Stack Model
pagenum: 82; label: 3.6.2
title: Implementation of Stacks
pagenum: 83; label: 3.6.3
title: Applications
pagenum: 83; label: 3.7
title: The Queue ADT
pagenum: 91; label: 3.7.1
title: Queue Model
pagenum: 91; label: 3.7.2
title: Array Implementation of Queues
pagenum: 91; label: 3.7.3
title: Applications of Queues
pagenum: 94; title: Summary
pagenum: 95; title: Exercises
pagenum: 95; label: Chapter 4
title: Trees
pagenum: 101; label: 4.1
title: Preliminaries
pagenum: 101; label: 4.1.1
title: Implementation of Trees
pagenum: 102; label: 4.1.2
title: Tree Traversals with an Application
pagenum: 103; label: 4.2
title: Binary Trees
pagenum: 107; label: 4.2.1
title: Implementation
pagenum: 108; label: 4.2.2
title: An Example: Expression Trees
pagenum: 109; label: 4.3
title: The Search Tree ADT - Binary Search Trees
pagenum: 112; label: 4.3.1
title: contains
pagenum: 113; label: 4.3.2
title: findMin and findMax
pagenum: 115; label: 4.3.3
title: insert
pagenum: 115; label: 4.3.4
title: remove
pagenum: 117; label: 4.3.5
title: Average-Case Analysis
pagenum: 120; label: 4.4
title: AVL Trees
pagenum: 123; label: 4.4.1
title: Single Rotation
pagenum: 125; label: 4.4.2
title: Double Rotation
pagenum: 128; label: 4.5
title: Splay Trees
pagenum: 135; label: 4.5.1
title: A Simple Idea (That Does Not Work)
pagenum: 135; label: 4.5.2
title: Splaying
pagenum: 137; label: 4.6
title: Tree Traversals (Revisited)
pagenum: 143; label: 4.7
title: B-Trees
pagenum: 145; label: 4.8
title: Sets and Maps in the Standard Library
pagenum: 150; label: 4.8.1
title: Sets
pagenum: 151; label: 4.8.2
title: Maps
pagenum: 151; label: 4.8.3
title: Implementation of TreeSet and TreeMap
pagenum: 152; label: 4.8.4
title: An Example That Uses Several Maps
pagenum: 152; title: Summary
pagenum: 157; title: Exercises
pagenum: 159; title: References
pagenum: 165; label: Chapter 5
title: Hashing
pagenum: 169; label: 5.1
title: General Idea
pagenum: 169; label: 5.2
title: Hash Function
pagenum: 170; label: 5.3
title: Separate Chaining
pagenum: 172; label: 5.4
title: Hash Tables Without Linked Lists
pagenum: 177; label: 5.4.1
title: Linear Probing
pagenum: 177; label: 5.4.2
title: Quadratic Probing
pagenum: 179; label: 5.4.3
title: Double Hashing
pagenum: 181; label: 5.5
title: Rehashing
pagenum: 186; label: 5.6
title: Hash Tables in the Standard Library
pagenum: 187; label: 5.7
title: Extendible Hashing
pagenum: 190; title: Summary
pagenum: 193; title: Exercises
pagenum: 194; title: References
pagenum: 198; label: Chapter 6
title: Priority Queues (Heaps)
pagenum: 201; label: 6.1
title: Model
pagenum: 201; label: 6.2
title: Simple Implementations
pagenum: 202; label: 6.3
title: Binary Heap
pagenum: 202; label: 6.3.1
title: Structure Property
pagenum: 203; label: 6.3.2
title: Heap Order Property
pagenum: 205; label: 6.3.3
title: Basic Heap Operations
pagenum: 205; label: 6.3.4
title: Other Heap Operations
pagenum: 210; label: 6.4
title: Applications of Priority Queues
pagenum: 214; label: 6.4.1
title: The Selection Problem
pagenum: 214; label: 6.4.2
title: Event Simulation
pagenum: 215; label: 6.5
title: d-Heaps
pagenum: 216; label: 6.6
title: Leftist Heaps
pagenum: 217; label: 6.6.1
title: Leftist Heap Property
pagenum: 217; label: 6.6.2
title: Leftist Heap Operations
pagenum: 218; label: 6.7
title: Skew Heaps
pagenum: 225; label: 6.8
title: Binomial Queues
pagenum: 227; label: 6.8.1
title: Binomial Queue Structure
pagenum: 228; label: 6.8.2
title: Binomial Queue Operations
pagenum: 229; label: 6.8.3
title: Implementation of Binomial Queues
pagenum: 232; label: 6.9
title: Priority Queues in the Standard Library
pagenum: 237; title: Summary
pagenum: 237; title: Exercises
pagenum: 239; title: References
pagenum: 243; label: Chapter 7
title: Sorting
pagenum: 247; label: 7.1
title: Preliminaries
pagenum: 247; label: 7.2
title: Insertion Sort
pagenum: 248; label: 7.2.1
title: The Algorithm
pagenum: 248; label: 7.2.2
title: Analysis of Insertion Sort
pagenum: 248; label: 7.3
title: A Lower Bound for Simple Sorting Algorithms
pagenum: 249; label: 7.4
title: Shellsort
pagenum: 250; label: 7.4.1
title: Worst-Case Analysis of Shellsort
pagenum: 252; label: 7.5
title: Heapsort
pagenum: 254; label: 7.5.1
title: Analysis of Heapsort
pagenum: 256; label: 7.6
title: Mergesort
pagenum: 258; label: 7.6.1
title: Analysis of Mergesort
pagenum: 260; label: 7.7
title: Quicksort
pagenum: 264; label: 7.7.1
title: Picking the Pivot
pagenum: 264; label: 7.7.2
title: Partitioning Strategy
pagenum: 266; label: 7.7.3
title: Small Arrays
pagenum: 268; label: 7.7.4
title: Actual Quicksort Routines
pagenum: 268; label: 7.7.5
title: Analysis of Quicksort
pagenum: 271; label: 7.7.6
title: A Linear-Expected-Time Algorithm for Selection
pagenum: 274; label: 7.8
title: A General Lower Bound for Sorting
pagenum: 276; label: 7.8.1
title: Decision Trees
pagenum: 276; label: 7.9
title: Bucket Sort
pagenum: 278; label: 7.10
title: External Sorting
pagenum: 279; label: 7.10.1
title: Why We Need New Algorithms
pagenum: 279; label: 7.10.2
title: Model for External Sorting
pagenum: 279; label: 7.10.3
title: The Simple Algorithm
pagenum: 279; label: 7.10.4
title: Multiway Merge
pagenum: 281; label: 7.10.5
title: Polyphase Merge
pagenum: 282; label: 7.10.6
title: Replacement Selection
pagenum: 283; title: Summary
pagenum: 284; title: Exercises
pagenum: 285; title: References
pagenum: 290; label: Chapter 8
title: The Disjoint Set Class
pagenum: 293; label: 8.1
title: Equivalence Relations
pagenum: 293; label: 8.2
title: The Dynamic Equivalence Problem
pagenum: 294; label: 8.3
title: Basic Data Structure
pagenum: 295; label: 8.4
title: Smart Union Algorithms
pagenum: 299; label: 8.5
title: Path Compression
pagenum: 301; label: 8.6
title: Worst Case for Union-by-Rank and Path Compression
pagenum: 303; label: 8.6.1
title: Analysis of the Union/Find Algorithm
pagenum: 304; label: 8.7
title: An Application
pagenum: 309; title: Summary
pagenum: 312; title: Exercises
pagenum: 312; title: References
pagenum: 314; label: Chapter 9
title: Graph Algorithms
pagenum: 317; label: 9.1
title: Definitions
pagenum: 317; label: 9.1.1
title: Representation of Graphs
pagenum: 318; label: 9.2
title: Topological Sort
pagenum: 320; label: 9.3
title: Shortest-Path Algorithms
pagenum: 323; label: 9.3.1
title: Unweighted Shortest Paths
pagenum: 325; label: 9.3.2
title: Dijkstra's Algorithm
pagenum: 329; label: 9.3.3
title: Graphs with Negative Edge Costs
pagenum: 338; label: 9.3.4
title: Acyclic Graphs
pagenum: 338; label: 9.3.5
title: All-Pairs Shortest Path
pagenum: 342; label: 9.3.6
title: Shortest-Path Example
pagenum: 342; label: 9.4
title: Network Flow Problems
pagenum: 344; label: 9.4.1
title: A Simple Maximum-Flow Algorithm
pagenum: 344; label: 9.5
title: Minimum Spanning Tree
pagenum: 349; label: 9.5.1
title: Prim's Algorithm
pagenum: 351; label: 9.5.2
title: Kruskal's Algorithm
pagenum: 353; label: 9.6
title: Applications of Depth-First Search
pagenum: 355; label: 9.6.1
title: Undirected Graphs
pagenum: 357; label: 9.6.2
title: Biconnectivity
pagenum: 358; label: 9.6.3
title: Euler Circuits
pagenum: 361; label: 9.6.4
title: Directed Graphs
pagenum: 366; label: 9.6.5
title: Finding Strong Components
pagenum: 367; label: 9.7
title: Introduction to NP-Completeness
pagenum: 369; label: 9.7.1
title: Easy vs. Hard
pagenum: 369; label: 9.7.2
title: The Class NP
pagenum: 370; label: 9.7.3
title: NP-Complete Problems
pagenum: 371; title: Summary
pagenum: 373; title: Exercises
pagenum: 373; title: References
pagenum: 381; label: Chapter 10
title: Algorithm Design Techniques
pagenum: 385; label: 10.1
title: Greedy Algorithms
pagenum: 385; label: 10.1.1
title: A Simple Scheduling Problem
pagenum: 386; label: 10.1.2
title: Huffman Codes
pagenum: 389; label: 10.1.3
title: Approximate Bin Packing
pagenum: 395; label: 10.2
title: Divide and Conquer
pagenum: 403; label: 10.2.1
title: Running Time of Divide and Conquer Algorithms
pagenum: 404; label: 10.2.2
title: Closest-Points Problem
pagenum: 406; label: 10.2.3
title: The Selection Problem
pagenum: 411; label: 10.2.4
title: Theoretical Improvements for Arithmetic Problems
pagenum: 414; label: 10.3
title: Dynamic Programming
pagenum: 418; label: 10.3.1
title: Using a Table Instead of Recursion
pagenum: 418; label: 10.3.2
title: Ordering Matrix Multiplications
pagenum: 421; label: 10.3.3
title: Optimal Binary Search Tree
pagenum: 424; label: 10.3.4
title: All-Pairs Shortest Path
pagenum: 426; label: 10.4
title: Randomized Algorithms
pagenum: 429; label: 10.4.1
title: Random Number Generators
pagenum: 431; label: 10.4.2
title: Skip Lists
pagenum: 435; label: 10.4.3
title: Primality Testing
pagenum: 437; label: 10.5
title: Backtracking Algorithms
pagenum: 440; label: 10.5.1
title: The Turnpike Reconstruction Problem
pagenum: 440; label: 10.5.2
title: Games
pagenum: 445; title: Summary
pagenum: 452; title: Exercises
pagenum: 452; title: References
pagenum: 461; label: Chapter 11
title: Amortized Analysis
pagenum: 465; label: 11.1
title: An Unrelated Puzzle
pagenum: 466; label: 11.2
title: Binomial Queues
pagenum: 466; label: 11.3
title: Skew Heaps
pagenum: 471; label: 11.4
title: Fibonacci Heaps
pagenum: 473; label: 11.4.1
title: Cutting Nodes in Leftist Heaps
pagenum: 474; label: 11.4.2
title: Lazy Merging for Binomial Queues
pagenum: 476; label: 11.4.3
title: The Fibonacci Heap Operations
pagenum: 480; label: 11.4.4
title: Proof of the Time Bound
pagenum: 480; label: 11.5
title: Splay Trees
pagenum: 483; title: Summary
pagenum: 487; title: Exercises
pagenum: 487; title: References
pagenum: 489; label: Chapter 12
title: Advanced Data Structures and Implementation
pagenum: 491; label: 12.1
title: Top-Down Splay Trees
pagenum: 491; label: 12.2
title: Red-Black Trees
pagenum: 497; label: 12.2.1
title: Bottom-Up Insertion
pagenum: 499; label: 12.2.2
title: Top-Down Red-Black Trees
pagenum: 501; label: 12.2.3
title: Top-Down Deletion
pagenum: 506; label: 12.3
title: Deterministic Skip Lists
pagenum: 508; label: 12.4
title: AA-Trees
pagenum: 513; label: 12.5
title: Treaps
pagenum: 521; label: 12.6
title: k-d Trees
pagenum: 523; label: 12.7
title: Pairing Heaps
pagenum: 527; title: Summary
pagenum: 532; title: Exercises
pagenum: 534; title: References
pagenum: 538; title: Index