Data Structures and Algorithm Analysis in Java = 数据结构与算法分析 :Java语言描述;数据结构与算法分析 :

✍ Scribed by Weiss, Mark Allen

• Publisher: Pearson; China Machine Press
• Year: 2011;2013
• Tongue: English
• Leaves: 633
• Series: HZ Books hua zhang jiao yu; Jing dian yuan ban shu ku
• Edition: Reprinted ed.
• Category: Library

✦ Synopsis

"Data Structures and Algorithm Analysis in Java "is an "advanced algorithms" book that fits between traditional CS2 and Algorithms Analysis courses. In the old ACM Curriculum Guidelines, this course was known as CS7. This text is for readers who want to learn good programming and algorithm analysis skills simultaneously so that they can develop such programs with the maximum amount of efficiency. Readers should have some knowledge of intermediate programming, including topics as object-based programming and recursion, and some background in discrete math. As the speed and power of computers increases, so does the need for effective programming and algorithm analysis. By approaching these skills in tandem, Mark Allen Weiss teaches readers to develop well-constructed, maximally efficient programs in Java. Weiss clearly explains topics from binary heaps to sorting to "NP"-completeness, and dedicates a full chapter to amortized analysis and advanced data structures and their implementation. Figures and examples illustrating successive stages of algorithms contribute to Weiss' careful, rigorous and in-depth analysis of each type of algorithm. A logical organization of topics and full access to source code complement the text's coverage.

✦ Table of Contents

Cover......Page 1
Contents......Page 8
Preface......Page 18
1.1 What's the Book About?......Page 22
1.2 Mathematics Review......Page 23
1.2.2 Logarithms......Page 24
1.2.3 Series......Page 25
1.2.4 Modular Arithmetic......Page 26
1.2.5 The P Word......Page 27
1.3 A Brief Introduction to Recursion......Page 29
1.4 Implementing Generic Components Pre-Java 5......Page 33
1.4.1 Using Object for Genericity......Page 34
1.4.3 Using Interface Types for Genericity......Page 35
1.5 Implementing Generic Components Using Java 5 Generics......Page 37
1.5.1 Simple Generic Classes and Interfaces......Page 38
1.5.3 The Diamond Operator......Page 39
1.5.4 Wildcards with Bounds......Page 40
1.5.5 Generic Static Methods......Page 41
1.5.6 Type Bounds......Page 42
1.5.7 Type Erasure......Page 43
1.5.8 Restrictions on Generics......Page 44
1.6 Function Objects......Page 45
Exercises......Page 47
References......Page 49
2.1 Mathematical Background......Page 50
2.2 Model......Page 53
2.3 What to Analyze......Page 54
2.4 Running Time Calculations......Page 56
2.4.2 General Rules......Page 57
2.4.3 Solutions for the Maximum Subsequence Sum Problem......Page 60
2.4.4 Logarithms in the Running Time......Page 66
Summary......Page 70
Exercises......Page 71
References......Page 76
3.1 Abstract Data Types (ADTs)......Page 78
3.2.1 Simple Array Implementation of Lists......Page 79
3.2.2 Simple Linked Lists......Page 80
3.3.2 Iterators......Page 82
3.3.3 The List Interface, ArrayList, and LinkedList......Page 84
3.3.4 Example: Using remove on a LinkedList......Page 86
3.4 Implementation of ArrayList......Page 88
3.4.1 The Basic Class......Page 89
3.4.2 The Iterator and Java Nested and Inner Classes......Page 92
3.5 Implementation of LinkedList......Page 96
3.6.1 Stack Model......Page 103
3.6.2 Implementation of Stacks......Page 104
3.6.3 Applications......Page 105
3.7.2 Array Implementation of Queues......Page 113
3.7.3 Applications of Queues......Page 116
Exercises......Page 117
4.1 Preliminaries......Page 122
4.1.1 Implementation of Trees......Page 123
4.1.2 Tree Traversals with an Application......Page 124
4.2 Binary Trees......Page 128
4.2.1 Implementation......Page 129
4.2.2 An Example: Expression Trees......Page 130
4.3 The Search Tree ADT—Binary Search Trees......Page 133
4.3.1 contains......Page 134
4.3.2 findMin and findMax......Page 136
4.3.3 insert......Page 137
4.3.4 remove......Page 139
4.3.5 Average-Case Analysis......Page 141
4.4 AVL Trees......Page 144
4.4.1 Single Rotation......Page 146
4.4.2 Double Rotation......Page 149
4.5.1 A Simple Idea (That Does Not Work)......Page 158
4.5.2 Splaying......Page 160
4.6 Tree Traversals (Revisited)......Page 166
4.7 B-Trees......Page 168
4.8.1 Sets......Page 173
4.8.3 Implementation of TreeSet and TreeMap......Page 174
4.8.4 An Example That Uses Several Maps......Page 175
Exercises......Page 181
References......Page 188
5.1 General Idea......Page 192
5.2 Hash Function......Page 193
5.3 Separate Chaining......Page 195
5.4.1 Linear Probing......Page 200
5.4.2 Quadratic Probing......Page 202
5.4.3 Double Hashing......Page 204
5.5 Rehashing......Page 209
5.6 Hash Tables in the Standard Library......Page 210
5.7 Hash Tables with Worst-Case O(1) Access......Page 213
5.7.1 Perfect Hashing......Page 214
5.7.2 Cuckoo Hashing......Page 216
5.7.3 Hopscotch Hashing......Page 226
5.8 Universal Hashing......Page 232
5.9 Extendible Hashing......Page 235
Summary......Page 238
Exercises......Page 239
References......Page 243
6.1 Model......Page 246
6.3 Binary Heap......Page 247
6.3.1 Structure Property......Page 248
6.3.3 Basic Heap Operations......Page 250
6.3.4 Other Heap Operations......Page 255
6.4.1 The Selection Problem......Page 259
6.4.2 Event Simulation......Page 260
6.5 d-Heaps......Page 261
6.6.1 Leftist Heap Property......Page 262
6.6.2 Leftist Heap Operations......Page 263
6.7 Skew Heaps......Page 270
6.8.1 Binomial Queue Structure......Page 273
6.8.2 Binomial Queue Operations......Page 274
6.8.3 Implementation of Binomial Queues......Page 277
Summary......Page 282
Exercises......Page 284
References......Page 288
7.1 Preliminaries......Page 292
7.2.2 Analysis of Insertion Sort......Page 293
7.3 A Lower Bound for Simple Sorting Algorithms......Page 294
7.4 Shellsort......Page 295
7.4.1 Worst-Case Analysis of Shellsort......Page 297
7.5 Heapsort......Page 299
7.5.1 Analysis of Heapsort......Page 300
7.6 Mergesort......Page 303
7.6.1 Analysis of Mergesort......Page 305
7.7 Quicksort......Page 309
7.7.1 Picking the Pivot......Page 311
7.7.2 Partitioning Strategy......Page 313
7.7.4 Actual Quicksort Routines......Page 315
7.7.5 Analysis of Quicksort......Page 318
7.7.6 A Linear-Expected-Time Algorithm for Selection......Page 321
7.8.1 Decision Trees......Page 323
7.9 Decision-Tree Lower Bounds for Selection Problems......Page 325
7.10 Adversary Lower Bounds......Page 328
7.11 Linear-Time Sorts: Bucket Sort and Radix Sort......Page 331
7.12 External Sorting......Page 336
7.12.3 The Simple Algorithm......Page 337
7.12.4 Multiway Merge......Page 338
7.12.5 Polyphase Merge......Page 339
7.12.6 Replacement Selection......Page 340
Exercises......Page 342
References......Page 348
8.1 Equivalence Relations......Page 352
8.2 The Dynamic Equivalence Problem......Page 353
8.3 Basic Data Structure......Page 354
8.4 Smart Union Algorithms......Page 358
8.5 Path Compression......Page 361
8.6 Worst Case for Union-by-Rank and Path Compression......Page 362
8.6.1 Slowly Growing Functions......Page 363
8.6.2 An Analysis By Recursive Decomposition......Page 364
8.6.4 An O( M α(M, N) ) Bound......Page 371
8.7 An Application......Page 373
Exercises......Page 376
References......Page 378
9.1 Definitions......Page 380
9.1.1 Representation of Graphs......Page 381
9.2 Topological Sort......Page 383
9.3 Shortest-Path Algorithms......Page 387
9.3.1 Unweighted Shortest Paths......Page 388
9.3.2 Dijkstra's Algorithm......Page 393
9.3.4 Acyclic Graphs......Page 401
9.3.6 Shortest-Path Example......Page 405
9.4 Network Flow Problems......Page 407
9.4.1 A Simple Maximum-Flow Algorithm......Page 409
9.5 Minimum Spanning Tree......Page 414
9.5.1 Prim's Algorithm......Page 415
9.5.2 Kruskal's Algorithm......Page 418
9.6 Applications of Depth-First Search......Page 420
9.6.1 Undirected Graphs......Page 421
9.6.2 Biconnectivity......Page 423
9.6.3 Euler Circuits......Page 426
9.6.4 Directed Graphs......Page 430
9.6.5 Finding Strong Components......Page 432
9.7 Introduction to NP-Completeness......Page 433
9.7.1 Easy vs. Hard......Page 434
9.7.2 The Class NP......Page 435
9.7.3 NP-Complete Problems......Page 436
Exercises......Page 438
References......Page 446
10.1 Greedy Algorithms......Page 450
10.1.1 A Simple Scheduling Problem......Page 451
10.1.2 Huffman Codes......Page 454
10.1.3 Approximate Bin Packing......Page 460
10.2 Divide and Conquer......Page 469
10.2.1 Running Time of Divide-and-Conquer Algorithms......Page 470
10.2.2 Closest-Points Problem......Page 472
10.2.3 The Selection Problem......Page 476
10.2.4 Theoretical Improvements for Arithmetic Problems......Page 479
10.3 Dynamic Programming......Page 483
10.3.1 Using a Table Instead of Recursion......Page 484
10.3.2 Ordering Matrix Multiplications......Page 487
10.3.3 Optimal Binary Search Tree......Page 490
10.3.4 All-Pairs Shortest Path......Page 493
10.4 Randomized Algorithms......Page 495
10.4.1 Random Number Generators......Page 497
10.4.2 Skip Lists......Page 501
10.4.3 Primality Testing......Page 504
10.5 Backtracking Algorithms......Page 507
10.5.1 The Turnpike Reconstruction Problem......Page 508
10.5.2 Games......Page 511
Exercises......Page 520
References......Page 529
Chapter 11 Amortized Analysis......Page 534
11.2 Binomial Queues......Page 535
11.3 Skew Heaps......Page 540
11.4.1 Cutting Nodes in Leftist Heaps......Page 543
11.4.2 Lazy Merging for Binomial Queues......Page 546
11.4.3 The Fibonacci Heap Operations......Page 549
11.4.4 Proof of the Time Bound......Page 550
11.5 Splay Trees......Page 552
Exercises......Page 557
References......Page 559
12.1 Top-Down Splay Trees......Page 562
12.2.1 Bottom-Up Insertion......Page 570
12.2.2 Top-Down Red-Black Trees......Page 572
12.2.3 Top-Down Deletion......Page 577
12.3 Treaps......Page 579
12.4 Suffix Arrays and Suffix Trees......Page 581
12.4.1 Suffix Arrays......Page 582
12.4.2 Suffix Trees......Page 585
12.4.3 Linear-Time Construction of Suffix Arrays and Suffix Trees......Page 588
12.5 k-d Trees......Page 599
12.6 Pairing Heaps......Page 604
Summary......Page 609
Exercises......Page 611
References......Page 615
A......Page 618
B......Page 619
C......Page 620
D......Page 621
F......Page 622
G......Page 623
I......Page 624
L......Page 625
M......Page 626
O......Page 627
P......Page 628
R......Page 629
S......Page 630
T......Page 631
V......Page 632
Z......Page 633

✦ Subjects

Science;Computer Science;Reference;Textbooks;Programming;Technology;Academic;School;Computers