Introduction to algorithms

Introduction to Algorithms
Second Edition

Thomas H. Cormen Charles E. Leiserson Ronald L. Rivest Clifford Stein

Introduction to Algorithms
Second Edition

The MIT Press Cambridge, Massachusetts

London, England Dubuque, IA St. Louis Montr´ al e Madison, WI Toronto

McGraw-Hill Book Company Boston Burr Ridge, IL New York San Francisco

This book is one of a series of textswritten by faculty of the Electrical Engineering and Computer Science Department at the Massachusetts Institute of Technology. It was edited and produced by The MIT Press under a joint production-distribution agreement with the McGraw-Hill Book Company. Ordering Information: North America Text orders should be addressed to the McGraw-Hill Book Company. All other orders should be addressed to The MITPress. Outside North America All orders should be addressed to The MIT Press or its local distributor. c 2001 by The Massachusetts Institute of Technology First edition 1990 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 thepublisher. This book was printed and bound in the United States of America. Library of Congress Cataloging-in-Publication Data Introduction to algorithms / Thomas H. Cormen . . . [et al.].—2nd ed. p. cm. Includes bibliographical references and index. ISBN 0-262-03293-7 (hc. : alk. paper) 1. Computer programming. 2. Computer algorithms. I. Title: Algorithms. II. Cormen, Thomas H. QA76.6 I5858 2001005.1—dc21 2001031277

Contents

Preface

xiii

I Foundations
Introduction 1 3 The Role of Algorithms in Computing 5 1.1 Algorithms 5 1.2 Algorithms as a technology 10 Getting Started 15 2.1 Insertion sort 15 2.2 Analyzing algorithms 21 2.3 Designing algorithms 27 Growth of Functions 41 3.1 Asymptotic notation 41 3.2 Standard notations and common functions Recurrences 62 4.1 Thesubstitution method 63 4.2 The recursion-tree method 67 4.3 The master method 73 4.4 Proof of the master theorem 76 Probabilistic Analysis and Randomized Algorithms 91 5.1 The hiring problem 91 5.2 Indicator random variables 94 5.3 Randomized algorithms 99 5.4 Probabilistic analysis and further uses of indicator random variables 105

2

3

51

4

⋆
5

⋆

vi

Contents

II Sorting andOrder Statistics
Introduction 6 123

Heapsort 127 6.1 Heaps 127 6.2 Maintaining the heap property 6.3 Building a heap 132 6.4 The heapsort algorithm 135 6.5 Priority queues 138

130

7

Quicksort 145 7.1 Description of quicksort 145 7.2 Performance of quicksort 149 7.3 A randomized version of quicksort 7.4 Analysis of quicksort 155 Sorting in Linear Time 165 8.1 Lower bounds for sorting 8.2Counting sort 168 8.3 Radix sort 170 8.4 Bucket sort 174 165

153

8

9

Medians and Order Statistics 183 9.1 Minimum and maximum 184 9.2 Selection in expected linear time 185 9.3 Selection in worst-case linear time 189

III Data Structures
Introduction 10 197 Elementary Data Structures 200 10.1 Stacks and queues 200 10.2 Linked lists 204 10.3 Implementing pointers and objects 10.4Representing rooted trees 214 Hash Tables 221 11.1 Direct-address tables 222 11.2 Hash tables 224 11.3 Hash functions 229 11.4 Open addressing 237 11.5 Perfect hashing 245

209

11

⋆

Contents

vii

12

⋆
13

Binary Search Trees 253 12.1 What is a binary search tree? 253 12.2 Querying a binary search tree 256 12.3 Insertion and deletion 261 12.4 Randomly built binary search trees 264Red-Black Trees 273 13.1 Properties of red-black trees 13.2 Rotations 277 13.3 Insertion 280 13.4 Deletion 288 273

14

Augmenting Data Structures 302 14.1 Dynamic order statistics 302 14.2 How to augment a data structure 14.3 Interval trees 311

308

IV Advanced Design and Analysis Techniques
Introduction 15 321

Dynamic Programming 323 15.1 Assembly-line scheduling 324 15.2...