Computer Algorithms Introduction to Design and Analysis,9780201612448

Computer Algorithms Introduction to Design and Analysis

by ;
Edition: 3rd
ISBN13: 9780201612448
ISBN10: 0201612445
Format: Paperback
Pub. Date: 1999-11-05
Publisher(s): Pearson
  • Free Shipping Icon

    This Item Qualifies for Free Shipping!*

    *Excludes marketplace orders.

List Price: $230.98

Buy New

In stock
$219.98
Add to Cart

Buy Used

Arriving Soon. Will ship when available.
$164.99
Add to Cart

Rent Textbook

Select for Price
Add to Cart
There was a problem. Please try again later.

eTextbook

We're Sorry
Not Available

Buy from our Marketplace starting at $13.74

How Marketplace Works:

  • This item is offered by an independent seller and not shipped from our warehouse
  • Item details like edition and cover design may differ from our description; see seller's comments before ordering.
  • Sellers much confirm and ship within two business days; otherwise, the order will be cancelled and refunded.
  • Marketplace purchases cannot be returned to eCampus.com. Contact the seller directly for inquiries; if no response within two days, contact customer service.
  • Additional shipping costs apply to Marketplace purchases. Review shipping costs at checkout.

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

An electronic version of this book is available through VitalSource.

This book is viewable on PC, Mac, iPhone, iPad, iPod Touch, and most smartphones.

By purchasing, you will be able to view this book online, as well as download it, for the chosen number of days.

Digital License

You are licensing a digital product for a set duration. Durations are set forth in the product description, with "Lifetime" typically meaning five (5) years of online access and permanent download to a supported device. All licenses are non-transferable.

More details can be found here.

A downloadable version of this book is available through the eCampus Reader or compatible Adobe readers.

Applications are available on iOS, Android, PC, Mac, and Windows Mobile platforms.

Please view the compatibility matrix prior to purchase.