Data Structures and Algorithms in Java
Publisher: Wiley
Published: Jan 28, 2014
Number of pages: 720
ISBN-13: 9781118771334
Table of contents: label: 1
title: Java Primer
pagenum: 1; label: 1.1
title: Getting Started
pagenum: 2; label: 1.1.1
title: Base Types
pagenum: 4; label: 1.2
title: Classes and Objects
pagenum: 5; label: 1.2.1
title: Creating and Using Objects
pagenum: 6; label: 1.2.2
title: Defining a Class
pagenum: 9; label: 1.3
title: Strings, Wrappers, Arrays, and Enum Types
pagenum: 17; label: 1.4
title: Expressions
pagenum: 23; label: 1.4.1
title: Literals
pagenum: 23; label: 1.4.2
title: Operators
pagenum: 24; label: 1.4.3
title: Type Conversions
pagenum: 28; label: 1.5
title: Control Flow
pagenum: 30; label: 1.5.1
title: The If and Switch Statements
pagenum: 30; label: 1.5.2
title: Loops
pagenum: 33; label: 1.5.3
title: Explicit Control-Flow Statements
pagenum: 37; label: 1.6
title: Simple Input and Output
pagenum: 38; label: 1.7
title: An Example Program
pagenum: 41; label: 1.8
title: Packages and Imports
pagenum: 44; label: 1.9
title: Software Development
pagenum: 46; label: 1.9.1
title: Design
pagenum: 46; label: 1.9.2
title: Pseudocode
pagenum: 48; label: 1.9.3
title: Coding
pagenum: 49; label: 1.9.4
title: Documentation and Style
pagenum: 50; label: 1.9.5
title: Testing and Debugging
pagenum: 53; label: 1.10
title: Exercises
pagenum: 55; label: 2
title: Object-Oriented Design
pagenum: 59; label: 2.1
title: Goals, Principles, and Patterns
pagenum: 60; label: 2.1.1
title: Object-Oriented Design Goals
pagenum: 60; label: 2.1.2
title: Object-Oriented Design Principles
pagenum: 61; label: 2.1.3
title: Design Patterns
pagenum: 63; label: 2.2
title: Inheritance
pagenum: 64; label: 2.2.1
title: Extending the CreditCard Class
pagenum: 65; label: 2.2.2
title: Polymorphism and Dynamic Dispatch
pagenum: 68; label: 2.2.3
title: Inheritance Hierarchies
pagenum: 69; label: 2.3
title: Interfaces and Abstract Classes
pagenum: 76; label: 2.3.1
title: Interfaces in Java
pagenum: 76; label: 2.3.2
title: Multiple Inheritance for Interfaces
pagenum: 79; label: 2.3.3
title: Abstract Classes
pagenum: 80; label: 2.4
title: Exceptions
pagenum: 82; label: 2.4.1
title: Catching Exceptions
pagenum: 82; label: 2.4.2
title: Throwing Exceptions
pagenum: 85; label: 2.4.3
title: Java's Exception Hierarchy
pagenum: 86; label: 2.5
title: Casting and Generics
pagenum: 88; label: 2.5.1
title: Casting
pagenum: 88; label: 2.5.2
title: Generics
pagenum: 91; label: 2.6
title: Nested Classes
pagenum: 96; label: 2.7
title: Exercises
pagenum: 97; label: 3
title: Fundamental Data Structures
pagenum: 103; label: 3.1
title: Using Arrays
pagenum: 104; label: 3.1.1
title: Storing Game Entries in an Array
pagenum: 104; label: 3.1.2
title: Sorting an Array
pagenum: 110; label: 3.1.3
title: java.util Methods for Arrays and Random Numbers
pagenum: 112; label: 3.1.4
title: Simple Cryptography with Character Arrays
pagenum: 115; label: 3.1.5
title: Two-Dimensional Arrays and Positional Games
pagenum: 118; label: 3.2
title: Singly Linked Lists
pagenum: 122; label: 3.2.1
title: Implementing a Singly Linked List Class
pagenum: 126; label: 3.3
title: Circularly Linked Lists
pagenum: 128; label: 3.3.1
title: Round-Robin Scheduling
pagenum: 128; label: 3.3.2
title: Designing and Implementing a Circularly Linked List
pagenum: 129; label: 3.4
title: Doubly Linked Lists
pagenum: 132; label: 3.4.1
title: Implementing a Doubly Linked List Class
pagenum: 135; label: 3.5
title: Equivalence Testing
pagenum: 138; label: 3.5.1
title: Equivalence Testing with Arrays
pagenum: 139; label: 3.5.2
title: Equivalence Testing with Linked Lists
pagenum: 140; label: 3.6
title: Cloning Data Structures
pagenum: 141; label: 3.6.1
title: Cloning Arrays
pagenum: 142; label: 3.6.2
title: Cloning Linked Lists
pagenum: 144; label: 3.7
title: Exercises
pagenum: 145; label: 4
title: Algorithm Analysis
pagenum: 149; label: 4.1
title: Experimental Studies
pagenum: 151; label: 4.1.1
title: Moving Beyond Experimental Analysis
pagenum: 154; label: 4.2
title: The Seven Functions Used in This Book
pagenum: 156; label: 4.2.1
title: Comparing Growth Rates
pagenum: 163; label: 4.3
title: Asymptotic Analysis
pagenum: 164; label: 4.3.1
title: The "Big-Oh" Notation
pagenum: 164; label: 4.3.2
title: Comparative Analysis
pagenum: 168; label: 4.3.3
title: Examples of Algorithm Analysis
pagenum: 170; label: 4.4
title: Simple Justification Techniques
pagenum: 178; label: 4.4.1
title: By Example
pagenum: 178; label: 4.4.2
title: The "Contra" Attack
pagenum: 178; label: 4.4.3
title: Induction and Loop Invariants
pagenum: 179; label: 4.5
title: Exercises
pagenum: 182; label: 5
title: Recursion
pagenum: 189; label: 5.1
title: Illustrative Examples
pagenum: 191; label: 5.1.1
title: The Factorial Function
pagenum: 191; label: 5.1.2
title: Drawing an English Ruler
pagenum: 193; label: 5.1.3
title: Binary Search
pagenum: 196; label: 5.1.4
title: File Systems
pagenum: 198; label: 5.2
title: Analyzing Recursive Algorithms
pagenum: 202; label: 5.3
title: Further Examples of Recursion
pagenum: 206; label: 5.3.1
title: Linear Recursion
pagenum: 206; label: 5.3.2
title: Binary Recursion
pagenum: 211; label: 5.3.3
title: Multiple Recursion
pagenum: 212; label: 5.4
title: Designing Recursive Algorithms
pagenum: 214; label: 5.5
title: Recursion Run Amok
pagenum: 215; label: 5.5.1
title: Maximum Recursive Depth in Java
pagenum: 218; label: 5.6
title: Eliminating Tail Recursion
pagenum: 219; label: 5.7
title: Exercises
pagenum: 221; label: 6
title: Stacks, Queues, and Deques
pagenum: 225; label: 6.1
title: Stacks
pagenum: 226; label: 6.1.1
title: The Stack Abstract Data Type
pagenum: 227; label: 6.1.2
title: A Simple Array-Based Stack Implementation
pagenum: 230; label: 6.1.3
title: Implementing a Stack with a Singly Linked List
pagenum: 233; label: 6.1.4
title: Reversing an Array Using a Stack
pagenum: 234; label: 6.1.5
title: Matching Parentheses and HTML Tags
pagenum: 235; label: 6.2
title: Queues
pagenum: 238; label: 6.2.1
title: The Queue Abstract Data Type
pagenum: 239; label: 6.2.2
title: Array-Based Queue Implementation
pagenum: 241; label: 6.2.3
title: Implementing a Queue with a Singly Linked List
pagenum: 245; label: 6.2.4
title: A Circular Queue
pagenum: 246; label: 6.3
title: Double-Ended Queues
pagenum: 248; label: 6.3.1
title: The Deque Abstract Data Type
pagenum: 248; label: 6.3.2
title: Implementing a Deque
pagenum: 250; label: 6.3.3
title: Deques in the Java Collections Framework
pagenum: 251; label: 6.4
title: Exercises
pagenum: 252; label: 7
title: List and Iterator ADTs
pagenum: 257; label: 7.1
title: The List ADT
pagenum: 258; label: 7.2
title: Array Lists
pagenum: 260; label: 7.2.1
title: Dynamic Arrays
pagenum: 263; label: 7.2.2
title: Implementing a Dynamic Array
pagenum: 264; label: 7.2.3
title: Amortized Analysis of Dynamic Arrays
pagenum: 265; label: 7.2.4
title: Java's StringBuilder Class
pagenum: 269; label: 7.3
title: Positional Lists
pagenum: 270; label: 7.3.1
title: Positions
pagenum: 272; label: 7.3.2
title: The Positional List Abstract Data Type
pagenum: 272; label: 7.3.3
title: Doubly Linked List Implementation
pagenum: 276; label: 7.4
title: Iterators
pagenum: 282; label: 7.4.1
title: The Iterable Interface and Java's For-Each Loop
pagenum: 283; label: 7.4.2
title: Implementing Iterators
pagenum: 284; label: 7.5
title: The Java Collections Framework
pagenum: 288; label: 7.5.1
title: List Iterators in Java
pagenum: 289; label: 7.5.2
title: Comparison to Our Positional List ADT
pagenum: 290; label: 7.5.3
title: List-Based Algorithms in the Java Collections Framework
pagenum: 291; label: 7.6
title: Sorting a Positional List
pagenum: 293; label: 7.7
title: Case Study: Maintaining Access Frequencies
pagenum: 294; label: 7.7.1
title: Using a Sorted List
pagenum: 294; label: 7.7.2
title: Using a List with the Move-to-Front Heuristic
pagenum: 297; label: 7.8
title: Exercises
pagenum: 300; label: 8
title: Trees
pagenum: 307; label: 8.1
title: General Trees
pagenum: 308; label: 8.1.1
title: Tree Definitions and Properties
pagenum: 309; label: 8.1.2
title: The Tree Abstract Data Type
pagenum: 312; label: 8.1.3
title: Computing Depth and Height
pagenum: 314; label: 8.2
title: Binary Trees
pagenum: 317; label: 8.2.1
title: The Binary Tree Abstract Data Type
pagenum: 319; label: 8.2.2
title: Properties of Binary Trees
pagenum: 321; label: 8.3
title: Implementing Trees
pagenum: 323; label: 8.3.1
title: Linked Structure for Binary Trees
pagenum: 323; label: 8.3.2
title: Array-Based Representation of a Binary Tree
pagenum: 331; label: 8.3.3
title: Linked Structure for General Trees
pagenum: 333; label: 8.4
title: Tree Traversal Algorithms
pagenum: 334; label: 8.4.1
title: Preorder and Postorder Traversals of General Trees
pagenum: 334; label: 8.4.2
title: Breadth-First Tree Traversal
pagenum: 336; label: 8.4.3
title: Inorder Traversal of a Binary Tree
pagenum: 337; label: 8.4.4
title: Implementing Tree Traversals in Java
pagenum: 339; label: 8.4.5
title: Applications of Tree Traversals
pagenum: 343; label: 8.4.6
title: Euler Tours
pagenum: 348; label: 8.5
title: Exercises
pagenum: 350; label: 9
title: Priority Queues
pagenum: 359; label: 9.1
title: The Priority Queue Abstract Data Type
pagenum: 360; label: 9.1.1
title: Priorities
pagenum: 360; label: 9.1.2
title: The Priority Queue ADT
pagenum: 361; label: 9.2
title: Implementing a Priority Queue
pagenum: 362; label: 9.2.1
title: The Entry Composite
pagenum: 362; label: 9.2.2
title: Comparing Keys with Total Orders
pagenum: 363; label: 9.2.3
title: The AbstractPriorityQueue Base Class
pagenum: 364; label: 9.2.4
title: Implementing a Priority Queue with an Unsorted List
pagenum: 366; label: 9.2.5
title: Implementing a Priority Queue with a Sorted List
pagenum: 368; label: 9.3
title: Heaps
pagenum: 370; label: 9.3.1
title: The Heap Data Structure
pagenum: 370; label: 9.3.2
title: Implementing a Priority Queue with a Heap
pagenum: 372; label: 9.3.3
title: Analysis of a Heap-Based Priority Queue
pagenum: 379; label: 9.3.4
title: Bottom-Up Heap Construction
pagenum: 380; label: 9.3.5
title: Using the java.util.PriorityQueue Class
pagenum: 384; label: 9.4
title: Sorting with a Priority Queue
pagenum: 385; label: 9.4.1
title: Selection-Sort and Insertion-Sort
pagenum: 386; label: 9.4.2
title: Heap-Sort
pagenum: 388; label: 9.5
title: Adaptable Priority Queues
pagenum: 390; label: 9.5.1
title: Location-Aware Entries
pagenum: 391; label: 9.5.2
title: Implementing an Adaptable Priority Queue
pagenum: 392; label: 9.6
title: Exercises
pagenum: 395; label: 10
title: Maps, Hash Tables, and Skip Lists
pagenum: 401; label: 10.1
title: Maps
pagenum: 402; label: 10.1.1
title: The Map ADT
pagenum: 403; label: 10.1.2
title: Application: Counting Word Frequencies
pagenum: 405; label: 10.1.3
title: An AbstractMap Base Class
pagenum: 406; label: 10.1.4
title: A Simple Unsorted Map Implementation
pagenum: 408; label: 10.2
title: Hash Tables
pagenum: 410; label: 10.2.1
title: Hash Functions
pagenum: 411; label: 10.2.2
title: Collision-Handling Schemes
pagenum: 417; label: 10.2.3
title: Load Factors, Rehashing, and Efficiency
pagenum: 420; label: 10.2.4
title: Java Hash Table Implementation
pagenum: 422; label: 10.3
title: Sorted Maps
pagenum: 428; label: 10.3.1
title: Sorted Search Tables
pagenum: 429; label: 10.3.2
title: Two Applications of Sorted Maps
pagenum: 433; label: 10.4
title: Skip Lists
pagenum: 436; label: 10.4.1
title: Search and Update Operations in a Skip List
pagenum: 438; label: 10.4.2
title: Probabilistic Analysis of Skip Lists
pagenum: 442; label: 10.5
title: Sets, Multisets, and Multimaps
pagenum: 445; label: 10.5.1
title: The Set ADT
pagenum: 445; label: 10.5.2
title: The Multiset ADT
pagenum: 447; label: 10.5.3
title: The Multimap ADT
pagenum: 448; label: 10.6
title: Exercises
pagenum: 451; label: 11
title: Search Trees
pagenum: 459; label: 11.1
title: Binary Search Trees
pagenum: 460; label: 11.1.1
title: Searching Within a Binary Search Tree
pagenum: 461; label: 11.1.2
title: Insertions and Deletions
pagenum: 463; label: 11.1.3
title: Java Implementation
pagenum: 466; label: 11.1.4
title: Performance of a Binary Search Tree
pagenum: 470; label: 11.2
title: Balanced Search Trees
pagenum: 472; label: 11.2.1
title: Java Framework for Balancing Search Trees
pagenum: 475; label: 11.3
title: AVL Trees
pagenum: 479; label: 11.3.1
title: Update Operations
pagenum: 481; label: 11.3.2
title: Java Implementation
pagenum: 486; label: 11.4
title: Splay Trees
pagenum: 488; label: 11.4.1
title: Splaying
pagenum: 488; label: 11.4.2
title: When to Splay
pagenum: 492; label: 11.4.3
title: Java Implementation
pagenum: 494; label: 11.4.4
title: Amortized Analysis of Splaying
pagenum: 495; label: 11.5
title: (2,4) Trees
pagenum: 500; label: 11.5.1
title: Multiway Search Trees
pagenum: 500; label: 11.5.2
title: (2,4)-Tree Operations
pagenum: 503; label: 11.6
title: Red-Black Trees
pagenum: 510; label: 11.6.1
title: Red-Black Tree Operations
pagenum: 512; label: 11.6.2
title: Java Implementation
pagenum: 522; label: 11.7
title: Exercises
pagenum: 525; label: 12
title: Sorting and Selection
pagenum: 531; label: 12.1
title: Merge-Sort
pagenum: 532; label: 12.1.1
title: Divide-and-Conquer
pagenum: 532; label: 12.1.2
title: Array-Based Implementation of Merge-Sort
pagenum: 537; label: 12.1.3
title: The Running Time of Merge-Sort
pagenum: 538; label: 12.1.4
title: Merge-Sort and Recurrence Equations
pagenum: 540; label: 12.1.5
title: Alternative Implementations of Merge-Sort
pagenum: 541; label: 12.2
title: Quick-Sort
pagenum: 544; label: 12.2.1
title: Randomized Quick-Sort
pagenum: 551; label: 12.2.2
title: Additional Optimizations for Quick-Sort
pagenum: 553; label: 12.3
title: Studying Sorting through an Algorithmic Lens
pagenum: 556; label: 12.3.1
title: Lower Bound for Sorting
pagenum: 556; label: 12.3.2
title: Linear-Time Sorting: Bucket-Sort and Radix-Sort
pagenum: 558; label: 12.4
title: Comparing Sorting Algorithms
pagenum: 561; label: 12.5
title: Selection
pagenum: 563; label: 12.5.1
title: Prune-and-Search
pagenum: 563; label: 12.5.2
title: Randomized Quick-Select
pagenum: 564; label: 12.5.3
title: Analyzing Randomized Quick-Select
pagenum: 565; label: 12.6
title: Exercises
pagenum: 566; label: 13
title: Text Processing
pagenum: 573; label: 13.1
title: Abundance of Digitized Text
pagenum: 574; label: 13.1.1
title: Notations for Character Strings
pagenum: 575; label: 13.2
title: Pattern-Matching Algorithms
pagenum: 576; label: 13.2.1
title: Brute Force
pagenum: 576; label: 13.2.2
title: The Boyer-Moore Algorithm
pagenum: 578; label: 13.2.3
title: The Knuth-Morris-Pratt Algorithm
pagenum: 582; label: 13.3
title: Tries
pagenum: 586; label: 13.3.1
title: Standard Tries
pagenum: 586; label: 13.3.2
title: Compressed Tries
pagenum: 590; label: 13.3.3
title: Suffix Tries
pagenum: 592; label: 13.3.4
title: Search Engine Indexing
pagenum: 594; label: 13.4
title: Text Compression and the Greedy Method
pagenum: 595; label: 13.4.1
title: The Huffman Coding Algorithm
pagenum: 596; label: 13.4.2
title: The Greedy Method
pagenum: 597; label: 13.5
title: Dynamic Programming
pagenum: 598; label: 13.5.1
title: Matrix Chain-Product
pagenum: 598; label: 13.5.2
title: DNA and Text Sequence Alignment
pagenum: 601; label: 13.6
title: Exercises
pagenum: 605; label: 14
title: Graph Algorithms
pagenum: 611; label: 14.1
title: Graphs
pagenum: 612; label: 14.1.1
title: The Graph ADT
pagenum: 618; label: 14.2
title: Data Structures for Graphs
pagenum: 619; label: 14.2.1
title: Edge List Structure
pagenum: 620; label: 14.2.2
title: Adjacency List Structure
pagenum: 622; label: 14.2.3
title: Adjacency Map Structure
pagenum: 624; label: 14.2.4
title: Adjacency Matrix Structure
pagenum: 625; label: 14.2.5
title: Java Implementation
pagenum: 626; label: 14.3
title: Graph Traversals
pagenum: 630; label: 14.3.1
title: Depth-First Search
pagenum: 631; label: 14.3.2
title: DFS Implementation and Extensions
pagenum: 636; label: 14.3.3
title: Breadth-First Search
pagenum: 640; label: 14.4
title: Transitive Closure
pagenum: 643; label: 14.5
title: Directed Acyclic Graphs
pagenum: 647; label: 14.5.1
title: Topological Ordering
pagenum: 647; label: 14.6
title: Shortest Paths
pagenum: 651; label: 14.6.1
title: Weighted Graphs
pagenum: 651; label: 14.6.2
title: Dijkstra's Algorithm
pagenum: 653; label: 14.7
title: Minimum Spanning Trees
pagenum: 662; label: 14.7.1
title: Prim-Jarník Algorithm
pagenum: 664; label: 14.7.2
title: Kruskal's Algorithm
pagenum: 667; label: 14.7.3
title: Disjoint Partitions and Union-Find Structures
pagenum: 672; label: 14.8
title: Exercises
pagenum: 677; label: 15
title: Memory Management and B-Trees
pagenum: 687; label: 15.1
title: Memory Management
pagenum: 688; label: 15.1.1
title: Stacks in the Java Virtual Machine
pagenum: 688; label: 15.1.2
title: Allocating Space in the Memory Heap
pagenum: 691; label: 15.1.3
title: Garbage Collection
pagenum: 693; label: 15.2
title: Memory Hierarchies and Caching
pagenum: 695; label: 15.2.1
title: Memory Systems
pagenum: 695; label: 15.2.2
title: Caching Strategies
pagenum: 696; label: 15.3
title: External Searching and B-Trees
pagenum: 701; label: 15.3.1
title: (a,b) Trees
pagenum: 702; label: 15.3.2
title: B-Trees
pagenum: 704; label: 15.4
title: External-Memory Sorting
pagenum: 705; label: 15.4.1
title: Multiway Merging
pagenum: 706; label: 15.5
title: Exercises
pagenum: 707; title: Bibliography
pagenum: 710; title: Index
pagenum: 714