An edition of Data structures & algorithm analysis in Java (1999)

Data structures & algorithm analysis in Java

2nd ed.

by

  • 6 Want to read
  • 1 Currently reading
Cover of: Data structures & algorithm analysis in Java by Mark Allen Weiss, Mark Allen Weiss
Preview Only

My Reading Lists:

Create a new list
Notes
  • 6 Want to read
  • 1 Currently reading
Notes

Check nearby libraries

Buy this book

Last edited by MARC Bot
July 15, 2024 | History
Edit
An edition of Data structures & algorithm analysis in Java (1999)

Data structures & algorithm analysis in Java

2nd ed.

by

  • 6 Want to read
  • 1 Currently reading

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

Publish Date
Publisher
Addison-Wesley, Peason Addison-Wesley
Language
English
Pages
555

Check nearby libraries

Buy this book

Previews available in: English

Subjects

Computer algorithms, Data structures (Computer science), Java (Computer program language), Algorithmes, Algorithms, Java (Langage de programmation), Structures de données (Informatique), JAVA (programspråk), Datastrukturer, Datoralgoritmer, Structures de donnees (Informatique), Computers & the internet, Database management
Edition Availability
Cover of: Data Structures and Algorithm Analysis in Java
Data Structures and Algorithm Analysis in Java
2012, Pearson Education, Limited, Pearson Education
in English
Cover of: Data structures and algorithm analysis in Java
Data structures and algorithm analysis in Java
2007, Dorling Kindersley
in English - 2nd ed.
Cover of: Data structures & algorithm analysis in Java
Data structures & algorithm analysis in Java
2006, Addison-Wesley, Peason Addison-Wesley
in English - 2nd ed.
Cover of: Data Structures and Algorithm Analysis in Java
Data Structures and Algorithm Analysis in Java
2005, Pearson Education, Limited
in English
Cover of: Data structures & algorithm analysis in Java
Data structures & algorithm analysis in Java
1999, Addison-Wesley
in English

Add another edition?

Book Details

Table of Contents

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

Edition Notes

Includes bibliographical references and index.

Published in
Boston
Other Titles
Data structures and algorithm analysis in Java

Classifications

Dewey Decimal Class
005.13/3
Library of Congress
QA76.73.J38 W448 2006, QA76.73.J38 W448 2007, QA76.73.J38W448 2006

The Physical Object

Pagination
p. cm.
Number of pages
555

Edition Identifiers

Open Library
OL3415678M
ISBN 10
0321370139
LCCN
2005031890
OCLC/WorldCat
62281925
LibraryThing
9163593
Goodreads
27845

Work Identifiers

Work ID
OL1958936W

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
July 15, 2024 Edited by MARC Bot import existing book
December 19, 2023 Edited by ImportBot import existing book
March 8, 2023 Edited by MARC Bot import existing book
October 4, 2021 Edited by ImportBot import existing book
December 9, 2009 Created by WorkBot add works page