Computer Algorithms: Introduction to Design and Analysis, 3/E
Sara Baase, San Diego State University
Allen Van Gelder, University of California at Santa Cruz

ISBN-10: 0201612445
ISBN-13: 9780201612448

Publisher: Addison-Wesley
Copyright: 2000
Format: Paper; 688 pp
Published: 11/05/1999

Suggested retail price: $95.00
Buy from myPearsonStore

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.

  • NEW - <F75BS>NEW! Material on accelerated version of Heapsort, section on computing with DNA, chapter on Dynamic Sets. Pg.___
  • NEW - <F75BS>NEW! Expanded treatment of recursion with a clear, student-friendly review of how it works, and why it is a valuable programming technique. Pg.___
  • NEW - <F75BS>NEW! Expanded mathematical background emphasizes practical techniques, including solutions to recurrence equations. Pg.___
  • NEW - <F75BS>NEW! Review of abstract data types, with Java class definitions for several commonly used ADTs such as list, tree, stack, and priority queue. Pg.___
  • NEW - <F75BS>NEW! Pseudocode updated from Pascal-like to Java-like; includes an appendix with Java examples. Pg.___
  • More than 100 new exercises. Pg.___



1. Analyzing Algorithms and Problems: Principles and Examples.

Introduction.

Java as an Algorithm Language.

A Usable Subset of Java.

Organizer Classes.

Java-Based Pseudocode Conventions.

Mathematical Background.

Sets, Tuples, and Relations.

Algebra and Calculus Tools.

Elements of Logic.

Analyzing Algorithms and Problems.

Correctness.

Amount of Work Done.

Average and Worst-Case Analysis.

Space Usage.

Simplicity.

Optimality.

Lower Bounds and the Complexity of Problems.

Implementation and Programming.

Classifying Functions by their Asymptotic Growth Rates.

Definitions and Notation.

How Important Is Asymptotic Order?

Properties of O, Theta, and Omega.

The Asymptotic Order of Commonly Occuring Sums.

Searching an Ordered Array.

Some Solutions.

Worst-Case Analysis of Binary Search.

Average-Behavior Analysis.

Optimality.



2. Data Abstraction and Basic Data Structures.

Introduction.

ADT Specifications and Design Techniques.

ADT Specifications.

ADT Design Techniques.

Elementary ADTs — Lists and Trees.

Recursive ADTs.

The List ADT.

Binary Tree ADT.

The Tree ADT.

In-Tree ADT.

Stacks and Queues.

Stack ADT.

Queue ADT.

ADTs for Dynamic Sets.

Priority Queue ADT.

Union-Find ADT for Disjoint Sets.

Dictionary ADT.



3. Recursion and Induction.

Introduction.

Recursive Procedures.

Activation Frames and Recursive Procedure Calls.

Hints for Recursion — Method 99.

Wrappers for Recursive Procedures.

What is a Proof?

Induction Proofs.

Induction Proof Schema.

Induction Proof on a Recursive Procedure.

Proving Correctness of Procedures.

Definitions and Terminology.

Elementary Control Structures.

The Single-Assignment Paradigm.

Procedures with Loops.

Correctness Proofs as a Debugging Tool.

Termination of Recursive Procedures.

Correctness of Binary Search.

Recurrence Equations.

Recursion Trees.

Divide-and-Conquer, General Case.

Chip and Conquer, or be Conquered.

Why Recursion Trees Work (*).



4. Sorting.

Introduction.

Insertion Sort.

The Strategy.

The Algorithm and Analysis.

Lower Bounds on the Behavior of Certain Sorting Algorithms.

Divide and Conquer.

Quicksort.

The Quicksort Strategy.

The Partition Subroutine.

Analysis of Quicksort.

Improvements on the Basic Quicksort Algorithm.

Merging Sorted Sequences.

Worst Case.

Optimality of Merge.

Space Usage.

Mergesort.

Lower Bounds for Sorting by Comparison of Keys.

Decision Trees for Sorting Algorithms.

Lower Bound for Worst Case.

Lower Bound for Average Behavior.

Heapsort.

Heaps.

The Heapsort Strategy.

FixHeap.

Heap Construction.

Implementation of a Heap and the Heapsort Algorithm.

Accelerated Heapsort.

Comparison of Four Sorting Methods.

Shellsort.

The Algorithm.

Analysis and Remarks.

Radix Sorting.

Using Properties of the Keys.

Radix Sort.



5. Selection and Adversary Arguments.

Introduction.

The Selection Problem.

Lower Bounds.

Adversary Arguments.

Tournaments.

Finding max and min.

Finding the Second-Largest Key.

Introduction.

The Tournament Method.

An Adversary Lower-Bound Argument.

Implementation of the Tournament Method for Finding max and secondLargest.

The Selection Problem.

A Divide-and-Conquer Approach.

A Linear-Time Selection Algorithm (*).

Analysis of the Selection Algorithm (*).

A Lower Bound for Finding the Median.

Designing Against an Adversary.



6. Dynamic Sets and Searching.

Introduction.

Array Doubling.

Amortized Time Analysis.

Red-Black Trees.

Binary Search Trees.

Binary Tree Rotations.

Red-Black Tree Definitions.

Size and Depth of Red-Black Trees.

Insertion into a Red-Black Tree.

Deletion from a Red-Black Tree.

Hashing.

Closed Address Hashing.

Open Address Hashing.

Hash Functions.

Dynamic Equivalence Relations and Union-Find Programs.

Dynamic Equivalence Relations.

Some Obvious Implementations.

Union-Find Programs.

Weighted Union.

Path Compression.

Analysis of wUnion and cFind (*).

Applications.

Priority Queues with a Decrease Key Operation.

The Decrease Key Operation.

Pairing Forests.



7. Graphs and Graph Traversals.

Definitions and Representations.

Some Examples.

Elementary Graph Definitions.

Graph Representations and Data Structures.

Traversing Graphs.

Overview of Depth-First Search.

Overview of Breadth-First Search.

Comparison of Depth-First and Breadth-First Searches.

Depth-First Search and Recursion.

Finding Connected Components with Depth-First Search.

Depth-First Search Trees.

A Generalized Depth-First Search Skeleton.

Structure of Depth-First Search.

Directed Acyclic Graphs and Topological Sort.

Strongly Connected Components of a Directed Graph.

Definitions.

A Strong Component Algorithm.

Analysis.

Biconnected Components of an Undirected Graph.

Articulation Points and Biconnected Components.

The Bicomponent Algorithm.

Analysis.

Generalizations.



8. Graph Optimization Problems and Greedy Algorithms.

Introduction.

Prim’s Minimum Spanning Tree Algorithm.

Definition and Examples of Minimum Spanning Trees.

An Overview of the Algorithm.

Properties of Minimum Spanning Trees.

Correctness of Prim’s MST Algorithm.

Managing the Fringe Efficiently with a Priority Queue.

Implementation.

Analysis (Time and Space).

Lower Bound.

Single-Source Shortest Paths.

Background.

Properties of Shortest Paths.

Dijkstra’s Shortest-Path Algorithm.

Implementation.

Kruskal’s Minimum Spanning Tree Algorithm.

Analysis.



9. Transitive Closure, All-Pairs Shortest Paths.

The Transitive Closure of a Binary Relation.

Definitions and Background.

Finding the Reachability Matrix by Depth-First Search.

Transitive Closure by Short Cuts.

Warshall—s Algorithm for Transitive Closure.

The Basic Algorithm.

Warshall—s Algorithm for Bit Matrices.

Distances in Graphs.

Computing Transitive Closure by Matrix Operations.

Multiplying Bit Matrices — Kronrod’s Algorithm.

Introduction.

Kronrod—s Algorithm.

Lower Bound (*).



10. Dynamic Programming.

Introduction.

Multiplying a Sequence of Matrices.

Constructing Optimal Binary Search Trees.

Separating Words into Lines.

Some Comments on Developing a Dynamic Programming Algorithm.



11. String Matching.

A Straightforward Solution.

The Knuth-Morris-Pratt Algorithm.

Pattern Matching with Finite Automata.

The Knuth-Morris-Pratt Flowchart.

Construction of the KMP Flowchart.

Analysis of the Flowchart Construction.

The Knuth-Morris-Pratt Scan Algorithm.

The Boyer-Moore Algorithm.

The New Idea.

And the “Old” Idea.

The Boyer-Moore Scan Algorithm.

Remarks.

Approximate String Matching.

Exercises.



12. Polynomials and Matrices.

Introductory Comments.

Evaluating Polynomial Functions.

Algorithms.

Lower Bounds for Polynomial Evaluation.

Preprocessing of Coefficients.

Vector and Matrix Multiplication.

Review of Standard Algorithms.

Winograd’s Matrix Multiplication.

Lower Bounds for Matrix Multiplication.

Strassen’s Matrix Multiplication.

The Fast Fourier Transform and Convolution (*).

Introduction.

The Fast Fourier Transform.

Convolution.

Appendix: Complex Numbers and Roots of Unity.



13. NP-Complete Problems.

P and NP.

Decision Problems.

Some Sample Problems.

The Class P.

The Class NP.

The Size of the Input.

NP-Complete Problems.

Polynomial Reductions.

Some Known NP-Complete Problems.

What Makes a Problem Hard?

Optimization Problems and Decision Problems.

Approximation Algorithms.

Bin Packing.

The First Fit Decreasing Strategy.

Other Heuristics.

The Knapsack and Subset-Sum Problems.

Graph Coloring.

Some Basic Techniques.

Approximate Graph Coloring Is Hard.

Wigderson’s Graph Coloring Algorithm.

The Traveling Salesperson Problem.

Greedy Strategies.

The Nearest Neighbor Strategy.

The Shortest Link Strategy.

How Good Are the TSP Approximation Algorithms?

Computing with DNA.

The Problem and an Overview of the Algorithm.

DNA Background.

Adleman’s Directed Graph and the DNA Algorithm.

Analysis and Evaluation.



14. Parallel Algorithms.

Parallelism, the PRAM, and Other Models.

Introduction.

The PRAM.

Other Models.

Some PRAM Algorithms.

The Binary Fan-In Technique.

Some Easily Parallelizable Algorithms.

Handling Write Conflicts.

Boolean or on n Bits.

An Algorithm for Finding Maximum in Constant Time.

Merging and Sorting.

Introduction.

Merging.

Sorting.

Finding Connected Components.

Strategy and Techniques.

The Algorithm.

PRAM Implementation of the Algorithm.

Analysis.

A Lower Bound for Computing a Function on n Bits.



A: Java Examples and Techniques.

A Java “Main Program.”

Library IntListLib Examples.

Generic Order and the “Comparable” Interface.

Copy via the “Clone” Interface.

Subclasses Extend the Capability of Their Superclass. 0201612445T04062001

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.

0201612445AB04062001

Drawing upon combined decades of teaching experience, Professors Sara Baase and Allen Van Gelder have extensively revised this best seller on algorithm design and analysis to make it the most current and accessible book available. This edition features an increased emphasis on algorithm design techniques such as divide-and-conquer and greedy algorithms, along with the addition of new topics and exercises. It continues the tradition of solid mathematical analysis and clear writing style that made it so popular in previous editions.

Highlights
  • Emphasizes the development of algorithms through a step-by-step process rather than merely presenting the end result
  • Stresses the importance of the algorithm analysis process—continuously re-evaluating, modifying, and perhaps rejecting algorithms until a satisfactory solution is attained
  • Provides extensive treatment of recursion with a clear, student-friendly review of how it works and why it is a valuable programming technique
  • Uses a Java-like pseudocode; includes an appendix with Java examples


0201612445B04062001

View a Sample Chapter PDF:

  • Additional Content, 3/E
    Baase & Van Gelder
    © 2000 | Addison-Wesley | On-line Supplement | Instock
    ISBN-10: 0321342011 | ISBN-13: 9780321342010


  • Additional Figures, 3/E
    Baase & Van Gelder
    © 2000 | Addison-Wesley | Unknown / Other | Estimated Availability: 01/13/2005
    ISBN-10: 032134202X | ISBN-13: 9780321342027

    Additional Figures, 3/E
    Baase & Van Gelder
    © 2000 | Addison-Wesley | Unknown / Other | Estimated Availability: 01/13/2005
    ISBN-10: 032134202X | ISBN-13: 9780321342027

    Downloadable files:

    Help downloading files

    View Downloadable Files

  • Online Solutions Manual, 3/E
    Baase
    © 2000 | Addison-Wesley | On-line Supplement | Estimated Availability: 01/01/2000
    ISBN-10: 0321341910 | ISBN-13: 9780321341914

    Online Solutions Manual, 3/E
    Baase
    © 2000 | Addison-Wesley | On-line Supplement | Estimated Availability: 01/01/2000
    ISBN-10: 0321341910 | ISBN-13: 9780321341914

    Downloadable files:

    • Download PDF (pdf) (.8 MB | pdf file | Type: Manuals/Guides)


    Help downloading files

    View Downloadable Files

  • Source Code, 3/E
    Baase
    © 2000 | Addison-Wesley | On-line Supplement | Estimated Availability: 01/01/2000
    ISBN-10: 0321341945 | ISBN-13: 9780321341945

    Source Code, 3/E
    Baase
    © 2000 | Addison-Wesley | On-line Supplement | Estimated Availability: 01/01/2000
    ISBN-10: 0321341945 | ISBN-13: 9780321341945

    Downloadable files:

    Help downloading files

    View Downloadable Files

Pearson Higher Education offers special pricing when you choose to package your text with other student resources. If you're interested in creating a cost-saving package for your students, contact your Pearson Higher Education representative for pricing and ordering information.

Pearson Higher Education offers special pricing when you choose to package your text with other student resources. If you're interested in creating a cost-saving package for your students, browse our available packages below, or contact your Pearson Higher Education representative to create your own package.



Copyright ©2008 Pearson Education. All rights reserved. Legal Notice | Privacy Policy | Permissions