상세정보

In this adaptation of his successful book, Data Structures and Algorithm Analysis, Mark Allen Weiss provides an innovative approach to algorithms and data structures in C++. He highlights conceptual topics, focusing on ADTs and the analysis of algorithms for efficiency as well as performance and running time. Dr. Weiss also distinguishes Data Structures and Algorithm Analysis in C++ with his clear, friendly writing style, logical organization or topics, and extensive use of figures and examples that show the successive stages of an algorithm. 0805354433B04062001

정보제공 :

CONTENTS
1 Introduction = 1
 1.1 What's the Book About? = 1
 1.2. Mathematics Review = 3
  1.2.1. Exponents = 3
  1.2.2. Logarithms = 3
  1.2.3. Series = 4
  1.2.4. Modular Arithmetic = 5
  1.2.5. The P Word = 6
 1.3. A Brief Introduction to Recursion = 8
 1.4. C++ at a Glance = 12
  1.4.1. A String Class = 14
  1.4.2. A Complex Number Class = 21
 Summary = 25
 Exercises = 25
 References = 26
2 Algorithm Analysis = 29
 2.1. Mathematical Background = 29
 2.2. Model = 32
 2.3. What to Analyze = 32
 2.4. Running Time Calculations = 34
  2.4.1. A Simple Example = 35
  2.4.2. General Example = 36
  2.4.3. Solutions for the Maximum Subsequence Sum Problem = 38
  2.4.4. Logarithms in the Running Time = 43
  2.4.5. Checking Your Analysis = 48
  2.4.6. A Grain of Salt = 48
 Summary = 48
 Exercises = 50
 References = 54
3 Lists, Stacks, and Queues = 57
 3.1. Abstract Data Types (ADTs) = 57
 3.2. The List ADT = 57
  3.2.1. Simple Array Implementation of Lists = 59
  3.2.2. Linked Lists = 59
  3.2.3. Programming Details = 60
  3.2.4. Common Errors = 69
  3.2.5. Doubly and Circularly Linked Lists = 71
  3.2.6. Sorted Linked Lists, Inheritance, and Virtual Functions = 71
  3.2.7. Examples = 73
  3.2.8. Cursor Implementation of Linked Lists = 80
 3.3. The Stack ADT = 88
  3.3.1. Stack Model = 88
  3.3.2. Implementation of Stacks = 89
  3.3.3. Applications = 96
 3.4. The Queue ADT = 104
  3.4.1. Queue Model = 104
  3.4.2. Array Implementation of Queues = 105
  3.4.3. Applications of Queues = 107
 Summary = 110
 Exercises = 111
4 Trees = 115
 4.1. Preliminaries = 115
  4.1.1. Implementation of Trees = 116
  4.1.2. Tree Traversals with an Application = 117
 4.2. Binary Trees = 121
  4.2.1. Implementation = 122
  4.2.2. Expression Trees = 123
 4.3. The Search Tree ADT - Binary Search Trees = 126
  4.3.1. Make_Empty = 129
  4.3.2. Find = 130
  4.3.3. Find_Min and Find_Max = 130
  4.3.4. Insert = 131
  4.3.5. Remove = 133
  4.3.6. Average-Case Analysis = 135
 4.4. AVL Trees = 137
  4.4.1. Single Rotation = 139
  4.4.2. Double Rotation = 141
 4.5. Splay Trees = 150
  4.5.1. A Simple Idea (That Does Not Work) = 150
  4.5.2. Splaying = 153
 4.6. Tree Traversals (Revisited) = 164
 4.7. B-Trees = 165
 Summary = 170
 Exercises = 171
 References = 177
5 Hashing = 181
 5.1. General Idea = 181
 5.2. Hash Function = 182
 5.3. Open Hashing (Separate Chaining) = 184
 5.4. Closed Hashing (Open Addressing) = 189
  5.4.1. Linear Probing = 189
  5.4.2. Quadratic Probing = 191
  5.4.3. Double Hashing = 193
 5.5. Rehashing = 198
 5.6. Extendible Hashing = 200
 Summary = 204
 Exercises = 206
 References = 208
6 Priority Queues (Heaps) = 211
 6.1. Model = 211
 6.2. Simple Implementations = 212
 6.3. Binary Heap = 213
  6.3.1. Structure Property = 213
  6.3.2. Heap Order Property = 215
  6.3.3. Basic Heap Operations = 216
  6.3.4. Other Heap Operations = 220
 6.4. Applications of Priority Queues = 223
  6.4.1. The Selection Problem = 224
  6.4.2. Event Simulation = 225
 6.5. d-Heaps = 226
 6.6. Leftist Heaps = 227
  6.6.1. Leftist Heap Property = 227
  6.6.2. Leftist Heap Operations = 228
 6.7. Skew Heaps = 235
 6.8. Binomial Queues = 237
  6.8.1. Binomial Queue Structure = 237
  6.8.2. Binomial Queue Operations = 237
  6.8.3. Implementation of Binomial Queues = 242
 Summary = 246
 Exercises = 247
 References = 251
7 Sorting = 253
 7.1. Preliminaries = 253
 7.2. Insertion Sort = 254
  7.2.1. The Algorithm = 254
  7.2.2. Analysis of Insertion Sort = 254
 7.3. A Lower Bound for Simple Sorting Algorithms = 255
 7.4. Shellsort = 256
  7.4.1. Worst-Case Analysis of Shellsort = 258
 7.5. Heapsort = 260
 7.6. Mergesort = 262
  7.6.1. Analysis of Mergesort = 265
 7.7. Quicksort = 267
  7.7.1. Picking the Pivot = 268
  7.7.2. Partitioning Strategy = 270
  7.7.3. Small Files = 272
  7.7.4. Actual Quicksort Routines = 272
  7.7.5. Analysis of Quicksort = 275
  7.7.6. A Linear-Expected-Time Algorithm for Selection = 278
 7.8 Sorting Large Objects = 280
 7.9. A General Lower Bound for Sorting = 280
  7.9.1. Decision Trees = 280
 7.10. Bucket Sort = 283
 7.11. External Sorting = 283
  7.11.1. Why We Need New Algorithms = 284
  7.11.2. Model for External Sorting = 284
  7.11.3. The Simple Algorithm = 284
  7.11.4. Multiway Merge = 286
  7.11.5. Polyphase Merge = 287
  7.11.6. Replacement Selection = 288
 Summary = 289
 Exercises = 290
 References = 293
8 The Disjoint Set ADT = 297
 8.1. Equivalence Relations = 297
 8.2. The Dynamic Equivalence Problem = 298
 8.3. Basic Data Structure = 299
 8.4. Smart Union Algorithms = 303
 8.5. Path Compression = 306
 8.6. Worst Case for Union-by-Rank and Path Compression = 307
  8.6.1. Analysis of the Union / Find Algorithm = 308
 8.7. An Applications = 314
 Summary = 314
 Exercises = 315
 References = 316
9 Graph Algorithms = 319
 9.1. Definitions = 319
  9.1.1. Representation of Graphs = 320
 9.2. Topological Sort = 332
 9.3. Shortest-Path Algorithms = 326
  9.3.1. Unweighted Shortest Paths = 327
  9.3.2. Dijkstra's Algorithm = 333
  9.3.3. Graphs with Negative Edge Costs = 340
  9.3.4. Acyclic Graphs = 341
  9.3.5. All-Pairs Shortest Path = 344
 9.4. Network Flow Problems = 345
  9.4.1. A Simple Maximum-Flow Algorithm = 345
 9.5. Minimum Spanning Tree = 350
 9.6. Applications of Depth-First Search = 356
  9.6.1. Undirected Graphs = 357
  9.6.2. Biconnectivity = 359
  9.6.3. Euler Circuits = 363
  9.6.4. Directed Graphs = 366
  9.6.5. Finding Strong components = 368
 9.7. Introduction to NP-Completeness = 369
  9.7.1. Easy vs, Hard = 370
  9.7.2. The Class NP = 371
  9.7.3. NP-Complete Problems = 372
 Summary = 374
 Exercises = 374
 References = 380
10 Algorithm Design Techniques = 383
 10.1. Greedy Algorithms = 383
  10.1.1. A Simple Scheduling Problem = 384
  10.1.2. Huffman Codes = 387
  10.1.3. Approximate Bin Packing = 393
 10.2. Divide and Conquer = 401
  10.2.1. Running Time of Divide and Conquer Algorithms = 402
  10.2.2. closest-Points Problem = 404
  10.2.3. The Selection Problem = 409
  10.2.4. Theoretical Improvements for Arithmetic problems = 412
 10.3. Dynamic Programming = 416
  10.3.1. Using a Table Instead of Recursion = 416
  10.3.2. Ordering Matrix Multiplications = 419
  10.3.3. Optimal Binary Search Tree = 422
  10.3.4. All-Pairs Shortest Path = 425
 10.4. Randomized Algorithms = 428
  10.4.1. Random Number Generators = 429
  10.4.2. Skip Lists = 433
  10.4.3. Primality Testing = 436
 10.5. Backtracking Algorithms = 438
  10.5.1. The Turnpike Reconstruction Problem = 439
  10.5.2. Games = 444
 Summary = 450
 Exercises = 451
 References = 458
11 Amortized Analysis = 463
 11.1. An Unrelated Puzzle = 464
 11.2. Binomial Queues = 464
 11.3. Skew heaps = 469
 11.4. Fibonacci Heaps = 471
  11.4.1. Cutting Nodes in Leftist heaps = 472
  11.4.2. Lazy Merging for Binomial Queues = 474
  11.4.3. The Fibonacci Heap Operations = 478
  11.4.4. Proof of the Time Bound = 479
 11.5. Splay Trees = 481
 Summary = 485
 Exercises = 486
 References = 487
Index = 489