Algorithms surveys the most important computer algorithms in use today and teaches fundamental techniques to the growing number of people in need of knowing them. It

• • • Can serve as a textbook for a second course in computer science.
    • Is suitable for self-study or as a reference for people developing computer systems or applications programs.
    • Is based on complete implementations using a modern programming style based on data abstraction.
    • Emphasizes a scientific approach to evaluating performance.

The broad perspective taken makes the book both an appropriate introduction to the field and a valuable reference. Since 1983, its various editions, written in many programming languages and translated into many foreign languages, have sold over one million copies and have educated generations of programmers and developers around the world.

Chapter 1. Fundamentals

1.1 Basic Programming Model
1.2 Data Abstraction
1.3 Bags, Queues, and Stacks
1.4 Analysis of Algorithms
1.5 Case Study: Union-Find

Chapter 2. Sorting 

2.1 Elementary Sorts
2.2 Mergesort
2.3 Quicksort
2.4 Priority Queues
2.5 Applications

Chapter 3. Searching 

3.1 Symbol Tables
3.2 Binary Search Trees
3.3 Balanced Search Trees
3.4 Hash Tables
3.5 Applications

Chapter 4. Graphs

4.1 Undirected Graphs
4.2 Directed Graphs
4.3 Minimum Spanning Trees
4.4 Shortest Paths

Chapter 5. Strings

5.1 String Sorts
5.2 Tries
5.3 Substring Search
5.4 Regular Expressions
5.5 Data Compression

Chapter 6. Context

6.1 Event-Driven Simulation
6.2 B-trees
6.3 Suffix Arrays
6.4 Network Flow
6.5 Reductions
6.6 Intractability

This book surveys the most important computer algorithms in use today, 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 implementations 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. Everyone 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 half-century, 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 essential 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.
     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 one or two dozen lines of code. As a group, they represent problem-solving power of amazing scope. They have enabled the construction of computational artifacts, the solution of scientific problems, and the development of commercial applications that would not have been feasible without them.

Distinctive features. The orientation of the book is to study algorithms likely to be of practical use. The book teaches a broad variety of algorithms and data structures and provides sufficient information about them that readers can confidently 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. 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 algorithms 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 searching 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 algorithms, graph processing, and string processing. We keep the material in algorithmic context, 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.

Online lectures. A complete set of curated studio-produced lecture videos that can be used in conjunction with this text are available online. These lectures are fully coordinated with the text, but also include examples and other materials that supplement the text and are intended to bring the subject to life. As with traditional live lectures, their purpose is to inform and inspire, motivating students to study and learn from the text. Our experience is that student engagement with the material is significantly better with videos than with live lectures because of the ability to play the lectures at a chosen speed and to replay and review the lectures at any time.

Booksite. Another important feature of the book is its relationship to our Algorithms website, which we refer to as the booksite. This site is freely available and contains an extensive amount of material about algorithms and data structures for teachers, students, and practitioners, including:

An online synopsis. The text is summarized in the booksite to give it the same overall structure as the book, but linked so as to provide easy navigation through the material.

Full implementations. All code in the book is available on the booksite, in a form suitable for program development. Many other implementations are also available, including advanced implementations and improvements described in the book, answers to selected exercises, and client code for various applications. The emphasis is on testing algorithms in the context of meaningful applications.

Exercises and answers. The booksite expands on the exercises in the book by adding drill exercises (with answers available with a click), a wide variety of examples illustrating the reach of the material, programming exercises with code solutions, and challenging problems.

Dynamic visualizations. Dynamic simulations are impossible in a printed book, but the website is replete with implementations that use a graphics class to present compelling visual demonstrations of algorithm applications.

Course materials. A complete set of lecture slides is tied directly to the material in the book and on the booksite. A full selection of programming assignments, with checklists, test data, and preparatory material, is also included.

Links to related material. Hundreds of links lead students to background information about applications and to resources for studying algorithms.

One of the most important implications of the booksite is that it empowers teachers, students, and practitioners to use their own computers to teach and learn the material. Anyone with a computer and a browser can delve into the study of algorithms by following a few instructions on the booksite.
     For teachers, the booksite is a rich source of enrichment materials and material for quizzes, examinations, programming assignments, and other assessments. Together with the studio-produced videos (and the book), it represents resources for teaching that are sufficiently flexible to support many of the models for teaching that are emerging as teachers embrace technology in the 21st century. For example, at Princeton, our teaching style was for many years based on offering two lectures per week to a large audience, supplemented by “precepts” each week where students met in small groups with instructors or teaching assistants. More recently, we have moved to a model where students watch lectures online and we hold class meetings in addition to the precepts. These meetings generally involve exams, exam preparation sessions, tutorials, and other activities that previously had to be scheduled outside of class time. Other teachers may work completely online. Still others may use a “flipped” model involving enrichment of each lecture after students watch it.
     For students, the booksite contains quick access to much of the material in the book, including source code, plus extra material to encourage self-learning. Solutions are provided for many of the book’s exercises, including complete program code and test data. There is a wealth of information associated with programming assignments, including suggested approaches, checklists, FAQs, and test data.
     For practitioners, the booksite is a resource for accessing all manner of extra information associated with the book’s content. All of the booksite content provides web links and other routes to pursue more information about the topic under consideration. There is far more information accessible than any individual could fully digest, but our goal is to provide enough to whet any reader’s appetite for more information about the book’s content.

     Our goal in creating these materials is to provide complementary approaches to the ideas. People may learn a concept through careful study in the book, an engaging example in an online lectures, browsing on the booksite, or perhaps all three.

Curriculum. The book is intended as a textbook in a second course in computer science. It provides full coverage of core material and is an excellent vehicle for students to gain experience and maturity in programming, quantitative reasoning, and problem-solving. Typically, one course in computer science will suffice as a prerequisite—the book is intended for anyone conversant with a modern programming language and with the basic features of modern computer systems.
     The algorithms and data structures are expressed in Java, but in a style accessible to people fluent in other modern languages. We embrace modern Java abstractions (such as generics and iterators) but resist dependence upon esoteric features of the language.
     Most of the mathematical material supporting the analytic results is self-contained (or is labeled as beyond the scope of this book), so little specific preparation in mathematics is required for the bulk of the book (mathematical maturity is definitely helpful). Applications are drawn from introductory material in the sciences, again self-contained.
     The material covered is a fundamental background for any student intending to major in computer science, electrical engineering, or operations research, and is valuable for any student with interests in science, mathematics, or engineering.

Related texts. The book is intended to follow our introductory text, Computer Science: An Interdisciplinary Approach, which is a broad introduction to the field. Together, these two books can support a two- or three-semester introduction to computer science that will give any student the requisite background to successfully address computation in any chosen field of study in science, engineering, or the social sciences.
     The starting point for much of the material in the book was the Sedgewick series of Algorithms books. In spirit, this book is closest to the first and second editions of that book, but this text benefits from decades of experience teaching and learning that material. Sedgewick’s Algorithms in C/C++/Java, Third Edition is more appropriate as a reference or a text for an advanced course; this book is specifically designed to be a textbook for a one-semester course for first- or second-year college students, a modern introduction to the basics, and a reference for use by working programmers.

Acknowledgments. This book has been over 40 years in the making, so full recognition of all the people who have made it possible is simply not feasible. Earlier editions of this book list dozens of names, including (in alphabetical order) Andrew Appel, Trina Avery, Marc Brown, Lyn Dupré, Philippe Flajolet, Tom Freeman, Dave Hanson, Janet Incerpi, Mike Schidlowsky, Steve Summit, and Chris Van Wyk. All of these people deserve acknowledgement, even though some of their contributions may have happened decades ago. For this fourth edition, we are grateful to the hundreds of students at Princeton and several other institutions who have suffered through preliminary versions of the work, and to readers around the world for sending in comments and corrections through the booksite.
     We are grateful for the support of Princeton University in its unwavering commitment to excellence in teaching and learning, which has provided the basis for the development of this work.
     Peter Gordon provided wise counsel throughout the evolution of this work almost from the beginning, including a gentle introduction of the “back to the basics” idea that is the foundation of this edition. For this fourth edition, we are grateful to Barbara Wood for her careful and professional copyediting, to Julie Nahil for managing the production, to Trina Fletcher MacDonald for ably stepping into Peter’s shoes, and to many others at Pearson for their roles in producing and marketing the book. All were extremely responsive to the demands of a rather tight schedule without the slightest sacrifice to the quality of the result.

Robert Sedgewick and Kevin Wayne
Princeton, NJ, December 2016

An extensive amount of content associated with this book is available online, most of it freely available. The introduction to the COURSES page and the essay on online learning on this website tell the full story of the types of content, relationships, and how it may best be used by students and teachers of all sorts. The COURSES page for this book gives specific details. Here are some brief descriptions and quick links to this material.

Booksite. Our Algorithms website contains tens of thousands of files, fully coordinated with our textbook and also useful as a standalone resource. It consists of the following elements:

Excerpts. A condensed version of the text narrative, for reference while online.
Java code. Hundreds of easily downloadable Java programs and our I/O libraries for processing text, graphics, and sound.
Data. Real-world data sets for testing code (ours and yours).
Exercises. Selected exercises from the book and “web exercises” developed since its publication, along with solutions to selected exercises.
Programming assignments. Creative programming assignments that we have used at Princeton.

This is a living resource that is constantly being improved and updated.

Online lectures. A complete set of curated studio-produced lecture videos that can be used in conjunction with this text are available online via the CUbits platform. This platform applies modern machine-learning models to build searchable transcripts, indexing, and other features that enhance the experience of learning from the videos.

Lecture slides. The lectures are based on hundreds of detailed, carefully prepared slides that are useful for reviewing the lecture content. These are available at the websites just listed, and on the COURSES page for this book, which provides a convenient interface for browsing through them.

MOOCs. The Coursera courses Algorithms Part 1 and Algorithms Part 2 are massive open online courses based on the lecture videos that include exercises, auto-assessed programming assignments, and other features encouraging coordinated study of the material in the book.

Princeton course. You can find details on how we conduct our course at Princeton on our course website. Our students watch lectures online and are organized into small groups where they regularly complete laboratory assignments, meet with instructors, and participate in discussion groups and virtual office hours. They complete weekly programming assignments which are assessed with a modern online infrastructure. Other assessments include two programming exams and two online exams on lecture material (you can find many examples of old exam questions with answers here, an excellent source for self-assessment). We use codePost for grading and providing targeted feedback for programming assignments, Zoom for class, precept meetings, and office hours, Gradescope for online exams, cubits to curate and serve lectures, and Ed for student Q&A and peer discussion. We ensure loose synchronization via regular e-mail for authoritative communication from faculty to students.