# book

### Text-only Preview

T H O M A S H. C O R M E N

C H A R L E S E. L

E I S E R S O N

R O N A L D L . R I V E S T

C L I F F O R D S T E I N

I N T R O D U C T I O N T O

A L G O R I T H M S

Thomas H. Cormen

Charles E. Leiserson

Ronald L. Rivest

Clifford Stein

The MIT Press

Cambridge, Massachusetts

London, England

c 2009 Massachusetts Institute of Technology

All rights reserved. No part of this book may be reproduced in any form or by any electronic or mechanical means

(including photocopying, recording, or information storage and retrieval) without permission in writing from the

publisher.

For information about special quantity discounts, please email special sales@mitpress.mit.edu.

This book was set in Times Roman and Mathtime Pro 2 by the authors.

Printed and bound in the United States of America.

Library of Congress Cataloging-in-Publication Data

Introduction to algorithms / Thomas H. Cormen . . . [et al.].--3rd ed.

p. cm.

Includes bibliographical references and index.

ISBN 978-0-262-03384-8 (hardcover : alk. paper)--ISBN 978-0-262-53305-8 (pbk. : alk. paper)

1. Computer programming.

2. Computer algorithms. I. Cormen, Thomas H.

QA76.6.I5858 2009

005.1--dc22

2009008593

10 9 8 7 6 5 4 3 2

Contents

1.1

Algorithms

1.2

Algorithms as a technology

2.1

Insertion sort

2.2

Analyzing algorithms

2.3

Designing algorithms

3.1

Asymptotic notation

3.2

Standard notations and common functions

4.1

The maximum-subarray problem

4.2

Strassen's algorithm for matrix multiplication

4.3

The substitution method for solving recurrences

4.4

The recursion-tree method for solving recurrences

4.5

The master method for solving recurrences

?

4.6

Proof of the master theorem

5.1

The hiring problem

5.2

Indicator random variables

5.3

Randomized algorithms

?

5.4

Probabilistic analysis and further uses of indicator random variables

6.1

Heaps

6.2

Maintaining the heap property

6.3

Building a heap

6.4

The heapsort algorithm

6.5

Priority queues

7.1

Description of quicksort

7.2

Performance of quicksort

7.3

A randomized version of quicksort

7.4

Analysis of quicksort

8.1

Lower bounds for sorting

8.2

Counting sort

8.3

Radix sort

8.4

Bucket sort

9.1

Minimum and maximum

9.2

Selection in expected linear time

9.3

Selection in worst-case linear time

10.1 Stacks and queues

10.2 Linked lists

10.3 Implementing pointers and objects

10.4 Representing rooted trees

11.1 Direct-address tables

11.2 Hash tables

11.3 Hash functions

11.4 Open addressing

?

11.5 Perfect hashing

12.1 What is a binary search tree?

12.2 Querying a binary search tree

12.3 Insertion and deletion

?

12.4 Randomly built binary search trees

13.1 Properties of red-black trees

13.2 Rotations

13.3 Insertion

13.4 Deletion

14.1 Dynamic order statistics

14.2 How to augment a data structure

14.3 Interval trees

15.1 Rod cutting

15.2 Matrix-chain multiplication

15.3 Elements of dynamic programming

15.4 Longest common subsequence

15.5 Optimal binary search trees

16.1 An activity-selection problem

16.2 Elements of the greedy strategy

16.3 Huffman codes

?

16.4 Matroids and greedy methods

?

16.5 A task-scheduling problem as a matroid

17.1 Aggregate analysis

17.2 The accounting method

17.3 The potential method

17.4 Dynamic tables

18.1 Definition of B-trees

18.2 Basic operations on B-trees

18.3 Deleting a key from a B-tree

19.1 Structure of Fibonacci heaps

19.2 Mergeable-heap operations

19.3 Decreasing a key and deleting a node

19.4 Bounding the maximum degree

20.1 Preliminary approaches

20.2 A recursive structure

20.3 The van Emde Boas tree

21.1 Disjoint-set operations

21.2 Linked-list representation of disjoint sets

21.3 Disjoint-set forests

?

21.4 Analysis of union by rank with path compression

22.1 Representations of graphs

22.2 Breadth-first search

22.3 Depth-first search

22.4 Topological sort

22.5 Strongly connected components

23.1 Growing a minimum spanning tree

23.2 The algorithms of Kruskal and Prim

24.1 The Bellman-Ford algorithm

24.2 Single-source shortest paths in directed acyclic graphs

24.3 Dijkstra's algorithm

24.4 Difference constraints and shortest paths

24.5 Proofs of shortest-paths properties

25.1 Shortest paths and matrix multiplication

25.2 The Floyd-Warshall algorithm

25.3 Johnson's algorithm for sparse graphs

26.1 Flow networks

26.2 The Ford-Fulkerson method

26.3 Maximum bipartite matching

?

26.4 Push-relabel algorithms

?

26.5 The relabel-to-front algorithm

27.1 The basics of dynamic multithreading

27.2 Multithreaded matrix multiplication

27.3 Multithreaded merge sort

28.1 Solving systems of linear equations

28.2 Inverting matrices

28.3 Symmetric positive-definite matrices and least-squares approximation

29.1 Standard and slack forms

29.2 Formulating problems as linear programs

29.3 The simplex algorithm

29.4 Duality

29.5 The initial basic feasible solution

C H A R L E S E. L

E I S E R S O N

R O N A L D L . R I V E S T

C L I F F O R D S T E I N

I N T R O D U C T I O N T O

A L G O R I T H M S

**T H I R D E D I T I O N****Introduction to Algorithms**

*Third Edition*Thomas H. Cormen

Charles E. Leiserson

Ronald L. Rivest

Clifford Stein

**Introduction to Algorithms**

*Third Edition*The MIT Press

Cambridge, Massachusetts

London, England

c 2009 Massachusetts Institute of Technology

All rights reserved. No part of this book may be reproduced in any form or by any electronic or mechanical means

(including photocopying, recording, or information storage and retrieval) without permission in writing from the

publisher.

For information about special quantity discounts, please email special sales@mitpress.mit.edu.

This book was set in Times Roman and Mathtime Pro 2 by the authors.

Printed and bound in the United States of America.

Library of Congress Cataloging-in-Publication Data

Introduction to algorithms / Thomas H. Cormen . . . [et al.].--3rd ed.

p. cm.

Includes bibliographical references and index.

ISBN 978-0-262-03384-8 (hardcover : alk. paper)--ISBN 978-0-262-53305-8 (pbk. : alk. paper)

1. Computer programming.

2. Computer algorithms. I. Cormen, Thomas H.

QA76.6.I5858 2009

005.1--dc22

2009008593

10 9 8 7 6 5 4 3 2

Contents

**Preface****xiii****I****Foundations****Introduction****3****1****The Role of Algorithms in Computing****5**1.1

Algorithms

*5*1.2

Algorithms as a technology

*11***2****Getting Started****16**2.1

Insertion sort

*16*2.2

Analyzing algorithms

*23*2.3

Designing algorithms

*29***3****Growth of Functions****43**3.1

Asymptotic notation

*43*3.2

Standard notations and common functions

*53***4****Divide-and-Conquer****65**4.1

The maximum-subarray problem

*68*4.2

Strassen's algorithm for matrix multiplication

*75*4.3

The substitution method for solving recurrences

*83*4.4

The recursion-tree method for solving recurrences

*88*4.5

The master method for solving recurrences

*93*?

4.6

Proof of the master theorem

*97***5****Probabilistic Analysis and Randomized Algorithms****114**5.1

The hiring problem

*114*5.2

Indicator random variables

*118*5.3

Randomized algorithms

*122*?

5.4

Probabilistic analysis and further uses of indicator random variables

*130**vi**Contents***II****Sorting and Order Statistics****Introduction****147****6****Heapsort****151**6.1

Heaps

*151*6.2

Maintaining the heap property

*154*6.3

Building a heap

*156*6.4

The heapsort algorithm

*159*6.5

Priority queues

*162***7****Quicksort****170**7.1

Description of quicksort

*170*7.2

Performance of quicksort

*174*7.3

A randomized version of quicksort

*179*7.4

Analysis of quicksort

*180***8****Sorting in Linear Time****191**8.1

Lower bounds for sorting

*191*8.2

Counting sort

*194*8.3

Radix sort

*197*8.4

Bucket sort

*200***9****Medians and Order Statistics****213**9.1

Minimum and maximum

*214*9.2

Selection in expected linear time

*215*9.3

Selection in worst-case linear time

*220***III****Data Structures****Introduction****229****10****Elementary Data Structures****232**10.1 Stacks and queues

*232*10.2 Linked lists

*236*10.3 Implementing pointers and objects

*241*10.4 Representing rooted trees

*246***11****Hash Tables****253**11.1 Direct-address tables

*254*11.2 Hash tables

*256*11.3 Hash functions

*262*11.4 Open addressing

*269*?

11.5 Perfect hashing

*277**Contents**vii***12****Binary Search Trees****286**12.1 What is a binary search tree?

*286*12.2 Querying a binary search tree

*289*12.3 Insertion and deletion

*294*?

12.4 Randomly built binary search trees

*299***13****Red-Black Trees****308**13.1 Properties of red-black trees

*308*13.2 Rotations

*312*13.3 Insertion

*315*13.4 Deletion

*323***14****Augmenting Data Structures****339**14.1 Dynamic order statistics

*339*14.2 How to augment a data structure

*345*14.3 Interval trees

*348***IV****Advanced Design and Analysis Techniques****Introduction****357****15****Dynamic Programming****359**15.1 Rod cutting

*360*15.2 Matrix-chain multiplication

*370*15.3 Elements of dynamic programming

*378*15.4 Longest common subsequence

*390*15.5 Optimal binary search trees

*397***16****Greedy Algorithms****414**16.1 An activity-selection problem

*415*16.2 Elements of the greedy strategy

*423*16.3 Huffman codes

*428*?

16.4 Matroids and greedy methods

*437*?

16.5 A task-scheduling problem as a matroid

*443***17****Amortized Analysis****451**17.1 Aggregate analysis

*452*17.2 The accounting method

*456*17.3 The potential method

*459*17.4 Dynamic tables

*463**viii**Contents***V****Advanced Data Structures****Introduction****481****18****B-Trees****484**18.1 Definition of B-trees

*488*18.2 Basic operations on B-trees

*491*18.3 Deleting a key from a B-tree

*499***19****Fibonacci Heaps****505**19.1 Structure of Fibonacci heaps

*507*19.2 Mergeable-heap operations

*510*19.3 Decreasing a key and deleting a node

*518*19.4 Bounding the maximum degree

*523***20****van Emde Boas Trees****531**20.1 Preliminary approaches

*532*20.2 A recursive structure

*536*20.3 The van Emde Boas tree

*545***21****Data Structures for Disjoint Sets****561**21.1 Disjoint-set operations

*561*21.2 Linked-list representation of disjoint sets

*564*21.3 Disjoint-set forests

*568*?

21.4 Analysis of union by rank with path compression

*573***VI****Graph Algorithms****Introduction****587****22****Elementary Graph Algorithms****589**22.1 Representations of graphs

*589*22.2 Breadth-first search

*594*22.3 Depth-first search

*603*22.4 Topological sort

*612*22.5 Strongly connected components

*615***23****Minimum Spanning Trees****624**23.1 Growing a minimum spanning tree

*625*23.2 The algorithms of Kruskal and Prim

*631**Contents**ix***24****Single-Source Shortest Paths****643**24.1 The Bellman-Ford algorithm

*651*24.2 Single-source shortest paths in directed acyclic graphs

*655*24.3 Dijkstra's algorithm

*658*24.4 Difference constraints and shortest paths

*664*24.5 Proofs of shortest-paths properties

*671***25****All-Pairs Shortest Paths****684**25.1 Shortest paths and matrix multiplication

*686*25.2 The Floyd-Warshall algorithm

*693*25.3 Johnson's algorithm for sparse graphs

*700***26****Maximum Flow****708**26.1 Flow networks

*709*26.2 The Ford-Fulkerson method

*714*26.3 Maximum bipartite matching

*732*?

26.4 Push-relabel algorithms

*736*?

26.5 The relabel-to-front algorithm

*748***VII****Selected Topics****Introduction****769****27****Multithreaded Algorithms****772**27.1 The basics of dynamic multithreading

*774*27.2 Multithreaded matrix multiplication

*792*27.3 Multithreaded merge sort

*797***28****Matrix Operations****813**28.1 Solving systems of linear equations

*813*28.2 Inverting matrices

*827*28.3 Symmetric positive-definite matrices and least-squares approximation

*832***29****Linear Programming****843**29.1 Standard and slack forms

*850*29.2 Formulating problems as linear programs

*859*29.3 The simplex algorithm

*864*29.4 Duality

*879*29.5 The initial basic feasible solution

*886*# Document Outline

- Contents
- Preface
- I Foundations
- 1 The Role of Algorithms in Computing
- 2 Getting Started
- 3 Growth of Functions
- 4 Divide-and-Conquer
- 5 Probabilistic Analysis and Randomized Algorithms

- II Sorting and Order Statistics
- 6 Heapsort
- 7 Quicksort
- 8 Sorting in Linear Time
- 9 Medians and Order Statistics

- III Data Structures
- 10 Elementary Data Structures
- 11 Hash Tables
- 12 Binary Search Trees
- 13 Red-Black Trees
- 14 Augmenting Data Structures

- IV Advanced Design and Analysis Techniques
- 15 Dynamic Programming
- 16 Greedy Algorithms
- 17 Amortized Analysis

- V Advanced Data Structures
- 18 B-Trees
- 19 Fibonacci Heaps
- 20 van Emde Boas Trees
- 21 Data Structures for Disjoint Sets

- VI Graph Algorithms
- 22 Elementary Graph Algorithms
- 23 Minimum Spanning Trees
- 24 Single-Source Shortest Paths
- 25 All-Pairs Shortest Paths
- 26 Maximum Flow

- VII Selected Topics
- 27 Multithreaded Algorithms
- 28 Matrix Operations
- 29 Linear Programming
- 30 Polynomials and the FFT
- 31 Number-Theoretic Algorithms
- 32 String Matching
- 33 Computational Geometry
- 34 NP-Completeness
- 35 Approximation Algorithms

- VIII Appendix: Mathematical Background
- A Summations
- B Sets, Etc.
- C Counting and Probability
- D Matrices

- Bibliography
- Index