Amazon no longer offers textbook rentals. We do!

Data Structures and Algorithm Analysis in Java

by: Weiss, Mark A.

Data Structures and Algorithm Analysis in Java

by: Weiss, Mark A.

ISBN 13:
9780321370136
ISBN 10:
0321370139
Edition: 2nd
Format: Paperback
Copyright: 01/01/2007
Publisher: Addison Wesley
Newer Edition

Rent

Sorry, this item is currently unavailable.

Note: Supplemental materials are not guaranteed with Rental or Used book purchases.

Extend or Purchase Your Rental at Any Time

Need to keep your rental past your due date? At any time before your due date you can extend or purchase your rental through your account.

Summary

In this text, readers are able to look at specific problems and see how careful implementations can reduce the time constraint for large amounts of data from several years to less than a second.This new edition contains all the enhancements of the new Java 5.0 code including detailed examples and an implementation of a large subset of the Java 5.0 Collections API.This text is for readers who want to learn good programming and algorithm analysis skills simultaneously so that they can develop such programs with the maximum amount of efficiency. Readers should have some knowledge of intermediate programming, including topics as object-based programming and recursion, and some background in discrete math.

Preface

Introduction

(28)

What's the Book About?

(1)

Mathematics Review

(5)

Exponents

(1)

Logarithms

(1)

Series

(1)

Modular Arithmetic

(1)

The P Word

(1)

A Brief Introduction to Recursion

(4)

Implementing Generic Components Pre Java 5

(5)

Using Object for Genericity

(1)

Wrappers for Primitive Types

(1)

Using Interface Types for Genericity

(2)

Compatibility of Array Types

(1)

Implementing Generic Components Using Java 5 Generics

(7)

Simple Generic Classes and Interfaces

(1)

Autoboxing/Unboxing

(1)

Wildcards with Bounds

(1)

Generic Static Methods

(1)

Type Bounds

(1)

Type Erasure

(1)

Restrictions on Generics

(1)

Function Objects

(6)

Summary

(1)

Exercises

(1)

References

(3)

Algorithm Analysis

(28)

Mathematical Background

(3)

Model

(1)

What to Analyze

(3)

Running Time Calculations

(22)

A Simple Example

(1)

General Rules

(2)

Solutions for the Maximum Subsequence Sum Problem

(6)

Logarithms in the Running Time

(4)

Checking Your Analysis

(1)

A Grain of Salt

(2)

Summary

(1)

Exercises

(5)

References

(2)

Lists, Stacks, and Queues

(44)

Abstract Data Types (ADTs)

(1)

The List ADT

(2)

Simple Array Implementation of Lists

(1)

Simple Linked Lists

(1)

Lists in the Java Collections API

(7)

Collection Interface

(1)

Iterators

(1)

The List Interface, ArrayList, and LinkedList

(2)

Example: Using Remove on a LinkedList

(1)

Listlterators

(1)

Implementation of ArrayList

(8)

The Basic Class

(1)

The Iterator and Java Nested and Inner Classes

(7)

Implementation of LinkedList

(7)

The Stack ADT

(9)

Stack Model

(1)

Implementation of Stacks

(1)

Applications

(8)

The Queue ADT

(10)

Queue Model

(1)

Array Implementation of Queues

(3)

Applications of Queues

(1)

Summary

(1)

Exercises

(6)

Trees

101

(68)

Preliminaries

101

(6)

Implementation of Trees

102

(1)

Tree Traversals with an Application

103

(4)

Binary Trees

107

(5)

Implementation

108

(1)

An Example: Expression Trees

109

(3)

The Search Tree ADT---Binary Search Trees

112

(11)

contains

113

(2)

findMin and findMax

115

(1)

insert

115

(2)

remove

117

(3)

Average-Case Analysis

120

(3)

AVL Trees

123

(12)

Single Rotation

125

(3)

Double Rotation

128

(7)

Splay Trees

135

(8)

A Simple Idea (That Does Not Work)

135

(2)

Splaying

137

(6)

Tree Traversals (Revisited)

143

(2)

B-Trees

145

(5)

Sets and Maps in the Standard Library

150

(7)

Sets

151

(1)

Maps

151

(1)

Implementation of TreeSet and TreeMap

152

(1)

An Example That Uses Several Maps

152

(5)

Summary

157

(12)

Exercises

159

(6)

References

165

(4)

Hashing

169

(32)

General Idea

169

(1)

Hash Function

170

(2)

Separate Chaining

172

(5)

Hash Tables Without Linked Lists

177

(9)

Linear Probing

177

(2)

Quadratic Probing

179

(2)

Double Hashing

181

(5)

Rehashing

186

(1)

Hash Tables in the Standard Library

187

(3)

Extendible Hashing

190

(11)

Summary

193

(1)

Exercises

194

(4)

References

198

(3)

Priority Queues (Heaps)

201

(46)

Model

201

(1)

Simple Implementations

202

(1)

Binary Heap

202

(12)

Structure Property

203

(2)

Heap Order Property

205

(1)

Basic Heap Operations

205

(5)

Other Heap Operations

210

(4)

Applications of Priority Queues

214

(2)

The Selection Problem

214

(1)

Event Simulation

215

(1)

d-Heaps

216

(1)

Leftist Heaps

217

(8)

Leftist Heap Property

217

(1)

Leftist Heap Operations

218

(7)

Skew Heaps

225

(2)

Binomial Queues

227

(10)

Binomial Queue Structure

228

(1)

Binomial Queue Operations

229

(3)

Implementation of Binomial Queues

232

(5)

Priority Queues in the Standard Library

237

(10)

Summary

237

(2)

Exercises

239

(4)

References

243

(4)

Sorting

247

(46)

Preliminaries

247

(1)

Insertion Sort

248

(1)

The Algorithm

248

(1)

Analysis of Insertion Sort

248

(1)

A Lower Bound for Simple Sorting Algorithms

249

(1)

Shellsort

250

(4)

Worst-Case Analysis of Shellsort

252

(2)

Heapsort

254

(4)

Analysis of Heapsort

256

(2)

Mergesort

258

(6)

Analysis of Mergesort

260

(4)

Quicksort

264

(12)

Picking the Pivot

264

(2)

Partitioning Strategy

266

(2)

Small Arrays

268

(1)

Actual Quicksort Routines

268

(3)

Analysis of Quicksort

271

(3)

A Linear-Expected-Time Algorithm for Selection

274

(2)

A General Lower Bound for Sorting

276

(2)

Decision Trees

276

(2)

Bucket Sort

278

(1)

External Sorting

279

(14)

Why We Need New Algorithms

279

(1)

Model for External Sorting

279

(1)

The Simple Algorithm

279

(2)

Multiway Merge

281

(1)

Polyphase Merge

282

(1)

Replacement Selection

283

(1)

Summary

284

(1)

Exercises

285

(5)

References

290

(3)

The Disjoint Set Class

293

(24)

Equivalence Relations

293

(1)

The Dynamic Equivalence Problem

294

(1)

Basic Data Structure

295

(4)

Smart Union Algorithms

299

(2)

Path Compression

301

(2)

Worst Case for Union-by-Rank and Path Compression

303

(6)

Analysis of the Union/Find Algorithm

304

(5)

An Application

309

(8)

Summary

312

(1)

Exercises

312

(2)

References

314

(3)

Graph Algorithms

317

(68)

Definitions

317

(3)

Representation of Graphs

318

(2)

Topological Sort

320

(3)

Shortest-Path Algorithms

323

(21)

Unweighted Shortest Paths

325

(4)

Dijkstra's Algorithm

329

(9)

Graphs with Negative Edge Costs

338

(1)

Acyclic Graphs

338

(4)

All-Pairs Shortest Path

342

(1)

Shortest-Path Example

342

(2)

Network Flow Problems

344

(5)

A Simple Maximum-Flow Algorithm

344

(5)

Minimum Spanning Tree

349

(6)

Prim's Algorithm

351

(2)

Kruskal's Algorithm

353

(2)

Applications of Depth-First Search

355

(14)

Undirected Graphs

357

(1)

Biconnectivity

358

(3)

Euler Circuits

361

(5)

Directed Graphs

366

(1)

Finding Strong Components

367

(2)

Introduction to NP-Completeness

369

(16)

Easy vs. Hard

369

(1)

The Class NP

370

(1)

NP-Complete Problems

371

(2)

Summary

373

(1)

Exercises

373

(8)

References

381

(4)

Algorithm Design Techniques

385

(80)

Greedy Algorithms

385

(18)

A Simple Scheduling Problem

386

(3)

Huffman Codes

389

(6)

Approximate Bin Packing

395

(8)

Divide and Conquer

403

(15)

Running Time of Divide and Conquer Algorithms

404

(2)

Closest-Points Problem

406

(5)

The Selection Problem

411

(3)

Theoretical Improvements for Arithmetic Problems

414

(4)

Dynamic Programming

418

(11)

Using a Table Instead of Recursion

418

(3)

Ordering Matrix Multiplications

421

(3)

Optimal Binary Search Tree

424

(2)

All-Pairs Shortest Path

426

(3)

Randomized Algorithms

429

(11)

Random Number Generators

431

(4)

Skip Lists

435

(2)

Primality Testing

437

(3)

Backtracking Algorithms

440

(25)

The Turnpike Reconstruction Problem

440

(5)

Games

445

(7)

Summary

452

(1)

Exercises

452

(9)

References

461

(4)

Amortized Analysis

465

(26)

An Unrelated Puzzle

466

(1)

Binomial Queues

466

(5)

Skew Heaps

471

(2)

Fibonacci Heaps

473

(10)

Cutting Nodes in Leftist Heaps

474

(2)

Lazy Merging for Binomial Queues

476

(4)

The Fibonacci Heap Operations

480

(1)

Proof of the Time Bound

480

(3)

Splay Trees

483

(8)

Summary

487

(1)

Exercises

487

(2)

References

489

(2)

Advanced Data Structures and Implementation

491

(50)

Top-Down Splay Trees

491

(6)

Red-Black Trees

497

(11)

Bottom-Up Insertion

499

(2)

Top-Down Red-Black Trees

501

(5)

Top-Down Deletion

506

(2)

Deterministic Skip Lists

508

(5)

AA-Trees

513

(8)

Treaps

521

(2)

k-d Trees

523

(4)

Pairing Heaps

527

(14)

Summary

532

(2)

Exercises

534

(4)

References

538

(3)

Index

541

Amazon no longer offers textbook rentals. We do!

Data Structures and Algorithm Analysis in Java

Data Structures and Algorithm Analysis in Java

9780321370136

0321370139

Summary

Table of Contents

Supplemental Materials

Write a Review

Amazon no longer offers textbook rentals. We do!

Data Structures and Algorithm Analysis in Java

Data Structures and Algorithm Analysis in Java

9780321370136

0321370139

Summary

Table of Contents

Supplemental Materials

Write a Review

Related Products