Introduction to Algorithms

, by Cormen, Thomas H.; Leiserson, Charles E.; Rivest, Ronald L.

Write a Review

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

ISBN: 9780070131439 | 0070131430
Cover: Hardcover
Copyright: 7/1/1990

Sorry, this item is currently not available.

Supplemental Materials

Preface

xiii

1 Introduction

(20)

1.1 Algorithms

(5)

1.2 Analyzing algorithms

(5)

1.3 Designing algorithms

(5)

1.4 Summary

(5)

I Mathematical Foundations

(116)

Introduction

(2)

2 Growth of Functions

(19)

2.1 Asymptotic notation

(9)

2.2 Standard notations and common functions

(10)

3 Summations

(11)

3.1 Summation formulas and properties

(4)

3.2 Bounding summations

(7)

4 Recurrences

(24)

4.1 The substitution method

(4)

4.2 The iteration method

(3)

4.3 The master method

(3)

*4.4 Proof of the master theorem

(13)

5 Sets, Etc.

(22)

5.1 Sets

(4)

5.2 Relations

(3)

5.3 Functions

(2)

5.4 Graphs

(5)

5.5 Trees

(8)

6 Counting and Probability

(38)

6.1 Counting

(5)

6.2 Probability

104

(7)

6.3 Discrete random variables

111

(4)

6.4 The geometric and binomial distributions

115

(6)

*6.5 The tails of the binomial distribution

121

(5)

6.6 Probabilistic analysis

126

(11)

II Sorting and Order Statistics

137

(60)

Introduction

137

(3)

7 Heapsort

140

(13)

7.1 Heaps

140

(2)

7.2 Maintaining the heap property

142

(3)

7.3 Building a heap

145

(2)

7.4 The heapsort algorithm

147

(2)

7.5 Priority queues

149

(4)

8 Quicksort

153

(19)

8.1 Description of quicksort

153

(3)

8.2 Performance of quicksort

156

(5)

8.3 Randomized versions of quicksort

161

(2)

8.4 Analysis of quicksort

163

(9)

9 Sorting in Linear Time

172

(13)

9.1 Lower bounds for sorting

172

(3)

9.2 Counting sort

175

(3)

9.3 Radix sort

178

(2)

9.4 Bucket sort

180

(5)

10 Medians and Order Statistics

185

(12)

10.1 Minimum and maximum

185

(2)

10.2 Selection in expected linear time

187

(2)

10.3 Selection in worst-case linear time

189

(8)

III Data Structures

197

(102)

Introduction

197

(3)

11 Elementary Data Structures

200

(19)

11.1 Stacks and queues

200

(4)

11.2 Linked lists

204

(5)

11.3 Implementing pointers and objects

209

(4)

11.4 Representing rooted trees

213

(6)

12 Hash Tables

219

(25)

12.1 Direct-address tables

219

(2)

12.2 Hash tables

221

(5)

12.3 Hash functions

226

(6)

12.4 Open addressing

232

(12)

13 Binary Search Trees

244

(19)

13.1 What is a binary search tree?

244

(2)

13.2 Querying a binary search tree

246

(4)

13.3 Insertion and deletion

250

(4)

*13.4 Randomly built binary search trees

254

(9)

14 Red-Black Trees

263

(18)

14.1 Properties of red-black trees

263

(2)

14.2 Rotations

265

(3)

14.3 Insertion

268

(4)

14.4 Deletion

272

(9)

15 Augmenting Data Structures

281

(18)

15.1 Dynamic order statistics

281

(6)

15.2 How to augment a data structure

287

(3)

15.3 Interval trees

290

(9)

IV Advanced Design and Analysis Techniques

299

(80)

Introduction

299

(2)

16 Dynamic Programming

301

(28)

16.1 Matrix-chain multiplication

302

(7)

16.2 Elements of dynamic programming

309

(5)

16.3 Longest common subsequence

314

(6)

16.4 Optimal polygon triangulation

320

(9)

17 Greedy Algorithms

329

(27)

17.1 An activity-selection problem

329

(4)

17.2 Elements of the greedy strategy

333

(4)

17.3 Huffman codes

337

(8)

*17.4 Theoretical foundations for greedy methods

345

(5)

*17.5 A task-scheduling problem

350

(6)

18 Amortized Analysis

356

(23)

18.1 The aggregate method

357

(3)

18.2 The accounting method

360

(3)

18.3 The potential method

363

(4)

18.4 Dynamic tables

367

(12)

V Advanced Data Structures

379

(84)

Introduction

379

(2)

19 B-Trees

381

(19)

19.1 Definition of B-trees

384

(3)

19.2 Basic operations on B-trees

387

(8)

19.3 Deleting a key from a B-tree

395

(5)

20 Binomial Heaps

400

(20)

20.1 Binomial trees and binomial heaps

401

(5)

20.2 Operations on binomial heaps

406

(14)

21 Fibonacci Heaps

420

(20)

21.1 Structure of Fibonacci heaps

421

(2)

21.2 Mergeable-heap operations

423

(8)

21.3 Decreasing a key and deleting a node

431

(4)

21.4 Bounding the maximum degree

435

(5)

22 Data Structures for Disjoint Sets

440

(23)

22.1 Disjoint-set operations

440

(3)

22.2 Linked-list representation of disjoint sets

443

(3)

22.3 Disjoint-set forests

446

(4)

*22.4 Analysis of union by rank with path compression

450

(13)

VI Graph Algorithms

463

(168)

Introduction

463

(2)

23 Elementary Graph Algorithms

465

(33)

23.1 Representations of graphs

465

(4)

23.2 Breadth-first search

469

(8)

23.3 Depth-first search

477

(8)

23.4 Topological sort

485

(3)

23.5 Strongly connected components

488

(10)

24 Minimum Spanning Trees

498

(16)

24.1 Growing a minimum spanning tree

499

(5)

24.2 The algorithms of Kruskal and Prim

504

(10)

25 Single-Source Shortest Paths

514

(36)

25.1 Shortest paths and relaxation

518

(9)

25.2 Dijkstra's algorithm

527

(5)

25.3 The Bellman-Ford algorithm

532

(4)

25.4 Single-source shortest paths in directed acyclic graphs

536

(3)

25.5 Difference constraints and shortest paths

539

(11)

26 All-Pairs Shortest Paths

550

(29)

26.1 Shortest paths and matrix multiplication

552

(6)

26.2 The Floyd-Warshall algorithm

558

(7)

26.3 Johnson's algorithm for sparse graphs

565

(5)

*26.4 A general framework for solving path problems in directed graphs

570

(9)

27 Maximum Flow

579

(52)

27.1 Flow networks

580

(7)

27.2 The Ford-Fulkerson method

587

(13)

27.3 Maximum bipartite matching

600

(5)

*27.4 Preflow-push algorithms

605

(10)

*27.5 The lift-to-front algorithm

615

(16)

VII Selected Topics

631

(356)

Introduction

631

(3)

28 Sorting Networks

634

(20)

28.1 Comparison networks

634

(5)

28.2 The zero-one principle

639

(3)

28.3 A bitonic sorting network

642

(4)

28.4 A merging network

646

(2)

28.5 A sorting network

648

(6)

29 Arithmetic Circuits

654

(34)

29.1 Combinational circuits

655

(5)

29.2 Addition circuits

660

(11)

29.3 Multiplication circuits

671

(7)

29.4 Clocked circuits

678

(10)

30 Algorithms for Parallel Computers

688

(42)

30.1 Pointer jumping

692

(9)

30.2 CRCW algorithms versus EREW algorithms

701

(8)

30.3 Brent's theorem and work efficiency

709

(5)

*30.4 Work-efficient parallel prefix computation

714

(6)

30.5 Deterministic symmetry breaking

720

(10)

31 Matrix Operations

730

(46)

31.1 Properties of matrices

730

(9)

31.2 Strassen's algorithm for matrix multiplication

739

(6)

*31.3 Algebraic number systems and boolean matrix multiplication

745

(4)

31.4 Solving systems of linear equations

749

(13)

31.5 Inverting matrices

762

(4)

31.6 Symmetric positive-definite matrices and least-squares approximation

766

(10)

32 Polynomials and the FFT

776

(25)

32.1 Representation of polynomials

778

(5)

32.2 The DFT and FFT

783

(8)

32.3 Efficient FFT implementations

791

(10)

33 Number-Theoretic Algorithms

801

(52)

33.1 Elementary number-theoretic notions

802

(6)

33.2 Greatest common divisor

808

(6)

33.3 Modular arithmetic

814

(6)

33.4 Solving modular linear equations

820

(3)

33.5 The Chinese remainder theorem

823

(4)

33.6 Powers of an element

827

(4)

33.7 The RSA public-key cryptosystem

831

(6)

*33.8 Primality testing

837

(7)

*33.9 Integer factorization

844

(9)

34 String Matching

853

(33)

34.1 The naive string-matching algorithm

855

(2)

34.2 The Rabin-Karp algorithm

857

(5)

34.3 String matching with finite automata

862

(7)

34.4 The Knuth-Morris-Pratt algorithm

869

(7)

*34.5 The Boyer-Moore algorithm

876

(10)

35 Computational Geometry

886

(30)

35.1 Line-segment properties

887

(5)

35.2 Determining whether any pair of segments intersects

892

(6)

35.3 Finding the convex hull

898

(10)

35.4 Finding the closest pair of points

908

(8)

36 NP-Completeness

916

(48)

36.1 Polynomial time

917

(7)

36.2 Polynomial-time verification

924

(5)

36.3 NP-completeness and reducibility

929

(10)

36.4 NP-completeness proofs

939

(7)

36.5 NP-complete problems

946

(18)

37 Approximation Algorithms

964

(23)

37.1 The vertex-cover problem

966

(3)

37.2 The traveling-salesman problem

969

(5)

37.3 The set-covering problem

974

(4)

37.4 The subset-sum problem

978

(9)

Bibliography

987

(10)

Index

997

FREE SHIPPING

Rent More, Save More! Use code: BBRENTAL

5% off 1 book, 7% off 2 books, 10% off 3+ books

Introduction to Algorithms

Table of Contents

Supplemental Materials