Computer Algorithms: Introduction to Design and Analysis

by Baase, Sara; Van Gelder, Allen

• ISBN13: 9780201612448
• ISBN10: 0201612445
• Additional ISBN(s): 9780201060355, 9780321486813
• Edition: 3rd
• Format: Paperback
• Copyright: 1999-11-05
• Publisher: Pearson
• More Book Details

Summary

Drawing upon combined decades of teaching experience, Professors Sara Baase and Allen Van Gelder have extensively revised this best seller to make it the most current and accessible choice for any algorithms course. The new Third Edition features the addition of new topics and exercises and 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.

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