Data Structures and Algorithm Analysis in C++

by Weiss, Mark A.

• ISBN13: 9780321441461
• ISBN10: 032144146X
• Edition: 3rd
• Format: Hardcover
• Copyright: 2006-02-28
• Publisher: Prentice Hall

Summary

In this text, readers are able to look at specific problems and see how careful implementations can reduce the time constraint for large amounts of data from several years to less than a second.Class templates are used to describe generic data structures and first-class versions of vector and string classes are used. Included is an appendix on a Standard Template Library (STL).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.

Table of Contents

Preface	p. xv
Introduction	p. 1
What's the Book About?	p. 1
Mathematics Review	p. 2
Exponents	p. 3
Logarithms	p. 3
Series	p. 4
Modular Arithmetic	p. 5
The P Word	p. 6
A Brief Introduction to Recursion	p. 7
C++ Classes	p. 11
Basic class Syntax	p. 12
Extra Constructor Syntax and Accessors	p. 12
Separation of Interface and Implementation	p. 15
vector and string	p. 17
C++ Details	p. 19
Pointers	p. 19
Parameter Passing	p. 21
Return Passing	p. 22
Reference Variables	p. 23
The Big Three: Destructor, Copy Constructor, operator=	p. 23
C-style Arrays and Strings	p. 26
Templates	p. 29
Function Templates	p. 29
Class Templates	p. 30
Object, Comparable, and an Example	p. 32
Function Objects	p. 34
Separate Compilation of Class Templates	p. 35
Using Matrices	p. 37
The Data Members, Constructor, and Basic Accessors	p. 37
operator[]	p. 37
Destructor, Copy Assignment, Copy Constructor	p. 39
Summary	p. 39
Exercises	p. 39
References	p. 41
Algorithm Analysis	p. 43
Mathematical Background	p. 43
Model	p. 46
What to Analyze	p. 46
Running Time Calculations	p. 49
A Simple Example	p. 49
General Rules	p. 50
Solutions for the Maximum Subsequence Sum Problem	p. 52
Logarithms in the Running Time	p. 58
Checking Your Analysis	p. 62
A Grain of Salt	p. 63
Summary	p. 63
Exercises	p. 64
References	p. 69
Lists, Stacks, and Queues	p. 71
Abstract Data Types (ADTs)	p. 71
The List ADT	p. 72
Simple Array Implementation of Lists	p. 72
Simple Linked Lists	p. 73
vector and list in the STL	p. 74
Iterators	p. 75
Example: Using erase on a List	p. 77
const_iterators	p. 77
Implementation of vector	p. 79
Implementation of list	p. 83
The Stack ADT	p. 94
Stack Model	p. 94
Implementation of Stacks	p. 95
Applications	p. 96
The Queue ADT	p. 104
Queue Model	p. 104
Array Implementation of Queues	p. 104
Applications of Queues	p. 106
Summary	p. 107
Exercises	p. 108
Trees	p. 113
Preliminaries	p. 113
Implementation of Trees	p. 114
Tree Traversals with an Application	p. 115
Binary Trees	p. 119
Implementation	p. 120
An Example: Expression Trees	p. 121
The Search Tree ADT-Binary Search Trees	p. 124
contains	p. 125
findMin and findMax	p. 125
insert	p. 129
remove	p. 130
Destructor and Copy Assignment Operator	p. 132
Average-Case Analysis	p. 133
AVL Trees	p. 136
Single Rotation	p. 139
Double Rotation	p. 142
Splay Trees	p. 149
A Simple Idea (That Does Not Work)	p. 150
Splaying	p. 152
Tree Traversals (Revisited)	p. 158
B-Trees	p. 159
Sets and Maps in the Standard Library	p. 165
Sets	p. 165
Maps	p. 166
Implementation of set and map	p. 167
An Example That Uses Several Maps	p. 168
Summary	p. 174
Exercises	p. 174
References	p. 181
Hashing	p. 185
General Idea	p. 185
Hash Function	p. 186
Separate Chaining	p. 188
Hash Tables Without Linked Lists	p. 192
Linear Probing	p. 193
Quadratic Probing	p. 195
Double Hashing	p. 199
Rehashing	p. 200
Hash Tables in the Standard Library	p. 204
Extendible Hasing	p. 204
Summary	p. 207
Exercises	p. 208
References	p. 211
Priority Queues (Heaps)	p. 213
Model	p. 213
Simple Implementations	p. 214
Binary Heap	p. 215
Structure Property	p. 215
Heap-Order Property	p. 216
Basic Heap Operations	p. 217
Other Heap Operations	p. 220
Applications of Priority Queues	p. 225
The Selection Problem	p. 226
Event Simulation	p. 227
d-Heaps	p. 228
Leftist Heaps	p. 229
Leftist Heap Property	p. 229
Leftist Heap Operations	p. 230
Skew Heaps	p. 235
Binomial Queues	p. 239
Binomial Queue Structure	p. 240
Binomial Queue Operations	p. 241
Implementation of Binomial Queues	p. 244
Priority Queues in the Standard Library	p. 251
Summary	p. 251
Exercises	p. 251
References	p. 257
Sorting	p. 261
Preliminaries	p. 261
Insertion Sort	p. 262
The Algorithm	p. 262
STL Implementation of Insertion Sort	p. 263
Analysis of Insertion Sort	p. 264
A Lower Bound for Simple Sorting Algorithms	p. 265
Shellsort	p. 266
Worst-Case Analysis of Shellsort	p. 268
Heapsort	p. 270
Analysis of Heapsort	p. 272
Mergesort	p. 274
Analysis of Mergesort	p. 276
Quicksort	p. 279
Picking the Pivot	p. 280
Partitioning Strategy	p. 282
Small Arrays	p. 284
Actual Quicksort Routines	p. 284
Analysis of Quicksort	p. 287
A Linear-Expected-Time Algorithm for Selection	p. 290
Indirect Sorting	p. 292
vector[left angle bracket]Comparable*[right angle bracket] Does Not Work	p. 295
Smart Pointer Class	p. 295
Overloading operator[left angle bracket]	p. 295
Dereferencing a Pointer with *	p. 295
Overloading the Type Conversion Operator	p. 295
Implicit Type Conversions Are Everywhere	p. 296
Dual-Direction Implicit Conversions Can Cause Ambiguities	p. 296
Pointer Subtraction Is Legal	p. 297
A General Lower Bound for Sorting	p. 297
Decision Trees	p. 297
Bucket Sort	p. 299
External Sorting	p. 300
Why We Need New Algorithms	p. 300
Model for External Sorting	p. 300
The Simple Algorithm	p. 301
Multiway Merge	p. 302
Polyphase Merge	p. 303
Replacement Selection	p. 304
Summary	p. 305
Exercises	p. 306
References	p. 311
The Disjoint Set Class	p. 315
Equivalence Relations	p. 315
The Dynamic Equivalence Problem	p. 316
Basic Data Structure	p. 317
Smart Union Algorithms	p. 321
Path Compression	p. 324
Worst Case for Union-by-Rank and Path Compression	p. 325
Analysis of the Union/Find Algorithm	p. 326
An Application	p. 331
Summary	p. 334
Exercises	p. 335
References	p. 336
Graph Algorithms	p. 339
Definitions	p. 339
Representation of Graphs	p. 340
Topological Sort	p. 342
Shortest-Path Algorithms	p. 345
Unweighted Shortest Paths	p. 347
Dijkstra's Algorithm	p. 351
Graphs with Negative Edge Costs	p. 360
Acyclic Graphs	p. 360
All-Pairs Shortest Path	p. 364
Shortest Path Example	p. 365
Network Flow Problems	p. 367
A Simple Maximum-Flow Algorithm	p. 367
Minimum Spanning Tree	p. 372
Prim's Algorithm	p. 373
Kruskal's Algorithm	p. 376
Applications of Depth-First Search	p. 378
Undirected Graphs	p. 379
Biconnectivity	p. 381
Euler Circuits	p. 385
Directed Graphs	p. 388
Finding Strong Components	p. 390
Introduction to NP-Completeness	p. 392
Easy vs. Hard	p. 392
The Class NP	p. 393
NP-Complete Problems	p. 394
Summary	p. 396
Exercises	p. 396
References	p. 404
Algorithm Design Techniques	p. 409
Greedy Algorithms	p. 409
A Simple Scheduling Problem	p. 410
Huffman Codes	p. 413
Approximate Bin Packing	p. 419
Divide and Conquer	p. 427
Running Time of Divide and Conquer Algorithms	p. 428
Closest-Points Problem	p. 430
The Selection Problem	p. 435
Theoretical Improvements for Arithmetic Problems	p. 438
Dynamic Programming	p. 442
Using a Table Instead of Recursion	p. 442
Ordering Matrix Multiplications	p. 444
Optimal Binary Search Tree	p. 447
All-Pairs Shortest Path	p. 451
Randomized Algorithms	p. 454
Random Number Generators	p. 455
Skip Lists	p. 459
Primality Testing	p. 461
Backtracking Algorithms	p. 464
The Turnpike Reconstruction Problem	p. 465
Games	p. 469
Summary	p. 475
Exercises	p. 475
References	p. 485
Amortized Analysis	p. 491
An Unrelated Puzzle	p. 492
Binomial Queues	p. 492
Skew Heaps	p. 497
Fibonacci Heaps	p. 499
Cutting Nodes in Leftist Heaps	p. 500
Lazy Merging for Binomial Queues	p. 502
The Fibonacci Heap Operations	p. 506
Proof of the Time Bound	p. 506
Splay Trees	p. 509
Summary	p. 513
Exercises	p. 513
References	p. 515
Advanced Data Structures and Implementation	p. 517
Top-Down Splay Trees	p. 517
Red-Black Trees	p. 525
Bottom-Up Insertion	p. 526
Top-Down Red-Black Trees	p. 527
Top-Down Deletion	p. 531
Deterministic Skip Lists	p. 535
AA-Trees	p. 540
Treaps	p. 547
k-d Trees	p. 549
Pairing Heaps	p. 553
Summary	p. 558
Exercises	p. 558
References	p. 563
Separate Compilation of Class Templates	p. 567
Everything in the Header	p. 568
Explicit Instantiation	p. 568
The export Directive	p. 570
Index	p. 571
Table of Contents provided by Ingram. All Rights Reserved.