An edition of Data Structures and Algorithms in Java (2014)

Data Structures and Algorithms in Java

by , , and

  • 10 Want to read
Cover of: Data Structures and Algorithms in Java by Michael T. Goodrich, Roberto Tamassia, Michael H Goldwasser, Michael T. Goodrich, Roberto Tamassia, Michael H Goldwasser
Preview Only

My Reading Lists:

Create a new list
Notes
  • 10 Want to read
Notes

Check nearby libraries

Buy this book

Last edited by MARC Bot
August 13, 2024 | History
Edit
An edition of Data Structures and Algorithms in Java (2014)

Data Structures and Algorithms in Java

by , , and

  • 10 Want to read

This work doesn't have a description yet. Can you add one?

Publish Date
Publisher
Wiley
Pages
720

Check nearby libraries

Buy this book

Subjects

Java (computer program language), Data structures (computer science), Computer algorithms
Edition Availability
Cover of: Data Structures and Algorithms in Java
Data Structures and Algorithms in Java
Jan 28, 2014, Wiley
Cover of: Data Structures and Algorithms in Java
Data Structures and Algorithms in Java
Jun 16, 2014, Wiley
paperback

Add another edition?

Book Details

Table of Contents

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

Classifications

Library of Congress
QA76.73.J38 G66 2014, QA76.73.J38

Edition Identifiers

Open Library
OL26837958M
ISBN 10
1118771338
ISBN 13
9781118771334
LCCN
2014412891
OCLC/WorldCat
847126203, 899243194

Work Identifiers

Work ID
OL19547378W

Source records

Community Reviews (0)

No community reviews have been submitted for this work.

Lists

Loading indicator
Loading carousel
Loading indicator
Loading carousel

History

Download catalog record: RDF / JSON
August 13, 2024 Edited by MARC Bot import existing book
November 14, 2020 Edited by MARC Bot import existing book
August 23, 2020 Edited by ImportBot import existing book
January 9, 2020 Edited by LeadSongDog Edited without comment.
April 5, 2019 Created by ImportBot import new book