Computer Algorithms Introduction to Design and Analysis

Name: Computer Algorithms Introduction to Design and Analysis
Price: 4.73 USD
Availability: InStock
ISBN: 9780201612448

ISBN-10: 0201612445

ISBN-13: 9780201612448

Edition: 3rd 2000 (Revised)

Authors: Sara Baase, Allen Van Gelder

List price: $193.32

This item qualifies for FREE shipping.

30 day, 100% satisfaction guarantee!

Buy new: $174.39

Marketplace

4 new & used from $4.73

what's this?

Rush Rewards U
Members Receive:

You have reached 400 XP and carrot coins. That is the daily max!

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.

Book details

List price: $193.32
Edition: 3rd
Copyright year: 2000
Publisher: Pearson Education
Publication date: 11/5/1999
Binding: Paperback
Pages: 720
Size: 7.30" wide x 9.10" long x 1.50" tall
Weight: 2.904
Language: English

"Sara Baase" is Professor Emeritus with the Department of Computer Science, San Diego State University, where she won awards for outstanding teaching. Her textbooks in computer science have been translated into several languages. Dr. Baase received her doctoral degree from the University of California, Berkeley.



Preface



Analyzing Algorithms and Problems: Principles and Examples



Introduction



Java as an Algorithm Language



Mathematical Background



Analyzing Algorithms and Problems



Classifying Functions by Their Asymptotic Growth Rates



Searching an Ordered Array


Exercises


Notes and References



Data Abstraction and Basic Data Structures



Introduction



ADT Specification and Design Techniques



Elementary ADTs--Lists and Trees



Stacks and Queues



ADTs for Dynamic Sets


Exercises


Notes and References



Recursion and Induction



Introduction



Recursive Procedures



What Is a Proof?



Induction Proofs



Proving Correctness of Procedures



Recurrence Equations



Recursion Trees


Exercises


Notes and References



Sorting



Introduction



Insertion Sort



Divide and Conquer



Quicksort



Merging Sorted Sequences



Mergesort



Lower Bounds for Sorting by Comparison of Keys



Heapsort



Comparison of Four Sorting Algorithms



Shellsort



Radix Sorting


Exercises


Programs


Notes and References



Selection and Adversary Arguments



Introduction



Finding max and min



Finding the Second-Largest Key



The Selection Problem



A Lower Bound for Finding the Median



Designing Against an Adversary


Exercises


Notes and References



Dynamic Sets and Searching



Introduction



Array Doubling



Amortized Time Analysis



Red-Black Trees



Hashing



Dynamic Equivalence Relations and Union-Find Programs



Priority Queues with a Decrease Key Operation


Exercises


Programs


Notes and References



Graphs and Graph Traversals



Introduction



Definitions and Representations



Traversing Graphs



Depth-First Search on Directed Graphs



Strongly Connected Components of a Directed Graph



Depth-First Search on Undirected Graphs



Biconnected Components of an Undirected Graph


Exercises


Programs


Notes and References



Graph Optimization Problems and Greedy Algorithms



Introduction



Prim's Minimum Spanning Tree Algorithm



Single-Source Shortest Paths



Kruskal's Minimum Spanning Tree Algorithm


Exercises


Programs


Notes and References



Transitive Closure, All-Pairs Shortest Paths



Introduction



The Transitive Closure of a Binary Relation



Warshall's Algorithm for Transitive Closure



All-Pairs Shortest Paths in Graphs



Computing Transitive Closure by Matrix Operations



Multiplying Bit Matrices--Kronrod's Algorithm


Exercises


Programs


Notes and References



Dynamic Programming



Introduction



Subproblem Graphs and Their Traversal



Multiplying a Sequence of Matrices



Constructing Optimal Binary Search Trees



Separating Sequences of Words into Lines



Developing a Dynamic Programming Algorithm


Exercises


Programs


Notes and References



String Matching



Introduction



A Straightforward Solution



The Knuth-Morris-Pratt Algorithm



The Boyer-Moore Algorithm



Approximate String Matching


Exercises


Programs


Notes and References



Polynomials and Matrices



Introduction



Evaluating Polynomial Functions



Vector and Matrix Multiplication



The Fast Fourier Transform and Convolution


Exercises


Programs


Notes and References



NP-Complete Problems



Introduction



P and NP



NP-Complete Problems



Approximation Algorithms



Bin Packing



The Knapsack and Subset Sum Problems



Graph Coloring



The Traveling Salesperson Problem



Computing with DNA


Exercises


Notes and References



Parallel Algorithms



Introduction



Parallelism, the PRAM, and Other Models



Some Simple PRAM Algorithms



Handling Write Conflicts



Merging and Sorting



Finding Connected Components



A Lower Bound for Adding n Integers


Exercises


Notes and References



Java Examples and Techniques



Introduction



A Java Main Program



A Simple Input Library



Documenting Java Classes



Generic Order and the "Comparable" Interface



Subclasses Extend the Capability of Their Superclass



Copy via the "Cloneable" Interface


Bibliography


Index