Computer Algorithms : Introduction to Design and Analysis

by Sara Baase

• ISBN13: 9780201060355
• ISBN10: 0201060353
• Edition: 2nd
• Format: Hardcover
• Copyright: 1988-01-01
• Publisher: Addison-Wesley

Summary

Drawing upon combined decades of teaching experience, Sara Baase and Allen Van Gelder have extensively revised this best seller to make it the most current and accessible choice for anyone interested in gaining a solid understanding of computer algorithm analysis and design. This edition features the addition of new topics such as computing with DNA, the accelerated version of heapsort, and dynamic sets, as well as an increased emphasis on algorithm design techniques such as divide-and-conquer and greedy algorithms. It continues the tradition of solid mathematical analysis and clear writing style that made it so popular in previous editions. This edition features implementations in a Java-like pseudocode, and includes an appendix with Java examples.

Author Biography

Sara Baase is a Professor of Computer Science at San Diego State University and has been teaching CS for 25 years. Dr. Baase is a three-time recipient of the San Diego State University Alumni Association's Outstanding Faculty Award, and she has written a number of textbooks in the areas of algorithms, assembly language, and social and ethical issues related to computing. She earned her doctorate at the University of California, Berkeley. Allen Van Gelder is a Professor of Computer Science at the University of California at Santa Cruz, where he has been teaching CS for 12 years. He received his Ph.D. in Computer Science at Stanford University and is a past recipient of the Presidential Young Investigator Award.

Table of Contents

Preface	p. vii
Analyzing Algorithms and Problems: Principles and Examples	p. 1
Introduction	p. 2
Java as an Algorithm Language	p. 3
Mathematical Background	p. 11
Analyzing Algorithms and Problems	p. 30
Classifying Functions by Their Asymptotic Growth Rates	p. 43
Searching an Ordered Array	p. 53
Exercises	p. 61
Notes and References	p. 67
Data Abstraction and Basic Data Structures	p. 69
Introduction	p. 70
ADT Specification and Design Techniques	p. 71
Elementary ADTs--Lists and Trees	p. 73
Stacks and Queues	p. 86
ADTs for Dynamic Sets	p. 89
Exercises	p. 95
Notes and References	p. 100
Recursion and Induction	p. 101
Introduction	p. 102
Recursive Procedures	p. 102
What Is a Proof?	p. 108
Induction Proofs	p. 111
Proving Correctness of Procedures	p. 118
Recurrence Equations	p. 130
Recursion Trees	p. 134
Exercises	p. 141
Notes and References	p. 146
Sorting	p. 149
Introduction	p. 150
Insertion Sort	p. 151
Divide and Conquer	p. 157
Quicksort	p. 159
Merging Sorted Sequences	p. 171
Mergesort	p. 174
Lower Bounds for Sorting by Comparison of Keys	p. 178
Heapsort	p. 182
Comparison of Four Sorting Algorithms	p. 197
Shellsort	p. 197
Radix Sorting	p. 201
Exercises	p. 206
Programs	p. 221
Notes and References	p. 221
Selection and Adversary Arguments	p. 223
Introduction	p. 224
Finding max and min	p. 226
Finding the Second-Largest Key	p. 229
The Selection Problem	p. 233
A Lower Bound for Finding the Median	p. 238
Designing Against an Adversary	p. 240
Exercises	p. 242
Notes and References	p. 246
Dynamic Sets and Searching	p. 249
Introduction	p. 250
Array Doubling	p. 250
Amortized Time Analysis	p. 251
Red-Black Trees	p. 253
Hashing	p. 275
Dynamic Equivalence Relations and Union-Find Programs	p. 283
Priority Queues with a Decrease Key Operation	p. 295
Exercises	p. 302
Programs	p. 309
Notes and References	p. 309
Graphs and Graph Traversals	p. 313
Introduction	p. 314
Definitions and Representations	p. 314
Traversing Graphs	p. 328
Depth-First Search on Directed Graphs	p. 336
Strongly Connected Components of a Directed Graph	p. 357
Depth-First Search on Undirected Graphs	p. 364
Biconnected Components of an Undirected Graph	p. 366
Exercises	p. 375
Programs	p. 384
Notes and References	p. 385
Graph Optimization Problems and Greedy Algorithms	p. 387
Introduction	p. 388
Prim's Minimum Spanning Tree Algorithm	p. 388
Single-Source Shortest Paths	p. 403
Kruskal's Minimum Spanning Tree Algorithm	p. 412
Exercises	p. 416
Programs	p. 421
Notes and References	p. 422
Transitive Closure, All-Pairs Shortest Paths	p. 425
Introduction	p. 426
The Transitive Closure of a Binary Relation	p. 426
Warshall's Algorithm for Transitive Closure	p. 430
All-Pairs Shortest Paths in Graphs	p. 433
Computing Transitive Closure by Matrix Operations	p. 436
Multiplying Bit Matrices--Kronrod's Algorithm	p. 439
Exercises	p. 446
Programs	p. 449
Notes and References	p. 449
Dynamic Programming	p. 451
Introduction	p. 452
Subproblem Graphs and Their Traversal	p. 453
Multiplying a Sequence of Matrices	p. 457
Constructing Optimal Binary Search Trees	p. 466
Separating Sequences of Words into Lines	p. 471
Developing a Dynamic Programming Algorithm	p. 474
Exercises	p. 475
Programs	p. 481
Notes and References	p. 482
String Matching	p. 483
Introduction	p. 484
A Straightforward Solution	p. 485
The Knuth-Morris-Pratt Algorithm	p. 487
The Boyer-Moore Algorithm	p. 495
Approximate String Matching	p. 504
Exercises	p. 508
Programs	p. 512
Notes and References	p. 512
Polynomials and Matrices	p. 515
Introduction	p. 516
Evaluating Polynomial Functions	p. 516
Vector and Matrix Multiplication	p. 522
The Fast Fourier Transform and Convolution	p. 528
Exercises	p. 542
Programs	p. 546
Notes and References	p. 546
NP-Complete Problems	p. 547
Introduction	p. 548
P and NP	p. 548
NP-Complete Problems	p. 559
Approximation Algorithms	p. 570
Bin Packing	p. 572
The Knapsack and Subset Sum Problems	p. 577
Graph Coloring	p. 581
The Traveling Salesperson Problem	p. 589
Computing with DNA	p. 592
Exercises	p. 600
Notes and References	p. 608
Parallel Algorithms	p. 611
Introduction	p. 612
Parallelism, the PRAM, and Other Models	p. 612
Some Simple PRAM Algorithms	p. 616
Handling Write Conflicts	p. 622
Merging and Sorting	p. 624
Finding Connected Components	p. 628
A Lower Bound for Adding n Integers	p. 641
Exercises	p. 643
Notes and References	p. 647
Java Examples and Techniques	p. 649
Introduction	p. 650
A Java Main Program	p. 651
A Simple Input Library	p. 656
Documenting Java Classes	p. 658
Generic Order and the "Comparable" Interface	p. 659
Subclasses Extend the Capability of Their Superclass	p. 663
Copy via the "Cloneable" Interface	p. 667
Bibliography	p. 669
Index	p. 679
Table of Contents provided by Syndetics. All Rights Reserved.