Algorithms (4th Edition)

[Link]

This Book is Available on [Link]

 Algorithms (4th Edition)

[Link]

Algorithms
FOURTH EDITION

This Book is Available on [Link]

 Algorithms (4th Edition)

[Link]

This page intentionally left blank

This Book is Available on [Link]

 Algorithms (4th Edition)

[Link]

Algorithms
FOURTH EDITION

Robert Sedgewick
and
Kevin Wayne

Princeton University

Upper Saddle River, NJ • Boston • Indianapolis • San Francisco

New York • Toronto • Montreal • London • Munich • Paris • Madrid
Capetown • Sydney • Tokyo • Singapore • Mexico City

This Book is Available on [Link]

 Algorithms (4th Edition)

[Link]

______________________________

To Adam, Andrew, Brett, Robbie

and especially Linda
______________________________

___________________

To Jackie and Alex

___________________

This Book is Available on [Link]

 Algorithms (4th Edition)

[Link]
CONTENTS
Preface . . . . . . . . . . . . . . . . . . . . . . . . .viii

1 Fundamentals . . . . . . . . . . . . . . . . . . . . . .3
1.1 Basic Programming Model 8
1.2 Data Abstraction 64
1.3 Bags, Queues, and Stacks 120
1.4 Analysis of Algorithms 172
1.5 Case Study: Union-Find 216
2 Sorting . . . . . . . . . . . . . . . . . . . . . . . 243
2.1 Elementary Sorts 244
2.2 Mergesort 270
2.3 Quicksort 288
2.4 Priority Queues 308
2.5 Applications 336
3 Searching . . . . . . . . . . . . . . . . . . . . . . 361
3.1 Symbol Tables 362
3.2 Binary Search Trees 396
3.3 Balanced Search Trees 424
3.4 Hash Tables 458
3.5 Applications 486

vi

This Book is Available on [Link]

 Algorithms (4th Edition)

[Link]

4 Graphs . . . . . . . . . . . . . . . . . . . . . . . 515
4.1 Undirected Graphs 518
4.2 Directed Graphs 566
4.3 Minimum Spanning Trees 604
4.4 Shortest Paths 638
5 Strings . . . . . . . . . . . . . . . . . . . . . . . 695
5.1 String Sorts 702
5.2 Tries 730
5.3 Substring Search 758
5.4 Regular Expressions 788
5.5 Data Compression 810
6 Context . . . . . . . . . . . . . . . . . . . . . . . 853

Index . . . . . . . . . . . . . . . . . . . . . . . . . 933

Algorithms . . . . . . . . . . . . . . . . . . . . . . 954
Clients . . . . . . . . . . . . . . . . . . . . . . . . 955

vii

This Book is Available on [Link]

 Algorithms (4th Edition)

[Link]

PREFACE

T
his book is intended to survey the most important computer algorithms in use today,
and to teach fundamental techniques to the growing number of people in need of
knowing them. It is intended for use as a textbook for a second course in computer
science, after students have acquired basic programming skills and familiarity with computer
systems. The book also may be useful for self-study or as a reference for people engaged in
the development of computer systems or applications programs, since it contains implemen-
tations of useful algorithms and detailed information on performance characteristics and
clients. The broad perspective taken makes the book an appropriate introduction to the field.
the study of algorithms and data structures is fundamental to any computer-
science curriculum, but it is not just for programmers and computer-science students. Every-
one who uses a computer wants it to run faster or to solve larger problems. The algorithms
in this book represent a body of knowledge developed over the last 50 years that has become
indispensable. From N-body simulation problems in physics to genetic-sequencing problems
in molecular biology, the basic methods described here have become essential in scientific
research; from architectural modeling systems to aircraft simulation, they have become es-
sential tools in engineering; and from database systems to internet search engines, they have
become essential parts of modern software systems. And these are but a few examples—as the
scope of computer applications continues to grow, so grows the impact of the basic methods
covered here.
Before developing our fundamental approach to studying algorithms, we develop data
types for stacks, queues, and other low-level abstractions that we use throughout the book.
Then we survey fundamental algorithms for sorting, searching, graphs, and strings. The last
chapter is an overview placing the rest of the material in the book in a larger context.

viii

This Book is Available on [Link]

 Algorithms (4th Edition)

Distinctive features The orientation of the book is to study algorithms likely to be of

[Link]
practical use. The book teaches a broad variety of algorithms and data structures and pro-
vides sufficient information about them that readers can confidently implement, debug, and
put them to work in any computational environment. The approach involves:

Algorithms. Our descriptions of algorithms are based on complete implementations and on

a discussion of the operations of these programs on a consistent set of examples. Instead of
presenting pseudo-code, we work with real code, so that the programs can quickly be put to
practical use. Our programs are written in Java, but in a style such that most of our code can
be reused to develop implementations in other modern programming languages.

Data types. We use a modern programming style based on data abstraction, so that algo-
rithms and their data structures are encapsulated together.

Applications. Each chapter has a detailed description of applications where the algorithms
described play a critical role. These range from applications in physics and molecular biology,
to engineering computers and systems, to familiar tasks such as data compression and search-
ing on the web.

A scientific approach. We emphasize developing mathematical models for describing the

performance of algorithms, using the models to develop hypotheses about performance, and
then testing the hypotheses by running the algorithms in realistic contexts.

Breadth of coverage. We cover basic abstract data types, sorting algorithms, searching al-
gorithms, graph processing, and string processing. We keep the material in algorithmic con-
text, describing data structures, algorithm design paradigms, reduction, and problem-solving
models. We cover classic methods that have been taught since the 1960s and new methods
that have been invented in recent years.

Our primary goal is to introduce the most important algorithms in use today to as wide an
audience as possible. These algorithms are generally ingenious creations that, remarkably, can
each be expressed in just a dozen or two lines of code. As a group, they represent problem-
solving power of amazing scope. They have enabled the construction of computational ar-
tifacts, the solution of scientific problems, and the development of commercial applications
that would not have been feasible without them.

ix

This Book is Available on [Link]