Computer Algorithms

New to the Third Edition:

• New section on recursion with a clear, student-friendly review of how it works, and why it is a valuable programming technique
• New sections on how to prove algorithms are correct, emphasizing the connection between recursion and induction proofs
• New sections on recurrence equations and recursion trees as a tool for solving recurrence equations
• Accelerated version of Heapsort in which the number of key comparisons is cut in half from the previous edition
• New section on computing with DNA
• New chapter on Dynamic Sets covering hashing, red-black trees, priority queues, and union-find sets
• Improved presentations of graph optimization algorithms
• New review of abstract data types, with Java class definitions for several commonly used ADTs such as list, tree, stack, and priority queue
• New section on approximation algorithms (greedy algorithms) for the Traveling Salesperson problem
• Over 100 new exercises
• New Appendices containing Java examples

Table of contents

1: Analyzing Algorithms and Problems: Principles and Examples

1.1: Introduction

1.2: Java as an Algorithm Language

1.3: Mathematical Background

1.4: Analyzing Algorithms and Problems

1.5: Classifying Functions by their Asymptotic Growth Rates

1.6: Searching an Ordered Array

2: Data Abstraction and Basic Data Structures

2.1: Introduction

2.2: ADT Specifications and Design Techniques

2.3: Elementary ADTs --- Lists and Trees

2.4: Stacks and Queues

2.5: ADTs for Dynamic Sets

3: Recursion and Induction

3.1: Introduction

3.2: Recursive Procedures

3.3: What is a Proof?

3.4: Induction Proofs

3.5: Proving Correctness of Procedures

3.6: Recurrence Equations

3.7: Recursion Trees

4: Sorting

4.1: Introduction

4.2: Insertion Sort

4.3: Divide and Conquer

4.4: Quicksort

4.5: Merging Sorted Sequences

4.6: Mergesort

4.7: Lower Bounds for Sorting by Comparison of Keys

4.8: Heapsort

4.9: Comparison of Four Sorting Methods

4.10: Shellsort

4.11: Radix Sorting

5: Selection and Adversary Arguments

5.1: Introduction

5.2: Finding max and min

5.3: Finding the Second-Largest Key

5.4: The Selection Problem

5.5: Designing Against an Adversary

6: Dynamic Sets and Searching

6.1: Introduction

6.2: Array Doubling

6.3: Amortized Time Analysis

6.4: Red-Black Trees

6.5: Hashing

6.6: Dynamic Equivalence Relations and Union-Find Programs

6.7: Priority Queues with a Decrease Key Operation

7 Graphs and Graph Traversals

7.1: Definitions and Representations

7.2: Traversing Graphs

7.3: Strongly Connected Components of a Directed Graph

7.4: Biconnected Components of an Undirected Graph

8: Graph Optimization Problems and Greedy Algorithms

8.1: Introduction

8.2: Prim's Minimum Spanning Tree Algorithm

8.3: Single-Source Shortest Paths

8.4: Kruskal's Minimum Spanning Tree Algorithm

9: Transitive Closure, All-Pairs Shortest Paths

9.1: The Transitive Closure of a Binary Relation

9.2: Warshall's Algorithm for Transitive Closure

9.3: Distances in Graphs

9.4: Computing Transitive Closure by Matrix Operations

9.5: Multiplying Bit Matrices -- Kronrod's Algorithm

10: Dynamic Programming

10.1: Introduction

10.2: Multiplying a Sequence of Matrices

10.3: Constructing Optimal Binary Search Trees

10.4: Separating Words into Lines

10.5: Some Comments on Developing a Dynamic Programming Algorithm

11: String Matching

11.1: A Straightforward Solution

11.2: The Knuth-Morris-Pratt Algorithm

11.3: The Boyer-Moore Algorithm

11.4: Approximate String Matching

11.5: Exercises

12: Polynomials and Matrices

12.1: Introductory Comments

12.2: Evaluating Polynomial Functions

12.3: Vector and Matrix Multiplication

12.4: The Fast Fourier Transform and Convolution (*)

13: NP-Complete Problems

13.1: P and NP

13.2: NP-Complete Problems

13.3: Approximation Algorithms

13.4: Bin Packing

13.5: The Knapsack and Subset-Sum Problems

13.6: Graph Coloring

13.7: The Traveling Salesperson Problem

13.8: Computing with DNA

14: Parallel Algorithms

14.1: Parallelism, the PRAM, and Other Models

14.2: Some PRAM Algorithms

14.3: Handling Write Conflicts

14.4: Merging and Sorting

14.5: Finding Connected Components

14.6: A Lower Bound for Computing a Function on n Bits

A: Java Examples and Techniques

A: 1: A Java "Main Program"

A: 2: Library IntListLib Examples

A: 3: Generic Order and the "Comparable" Interface

A: 4: Copy via the "Clone" Interface

A: 5: Subclasses Extend the Capability of Their Superclass