Algorithms (4th Edition)

This book is great! Nothing less, nothing more. I would recommend this book to all CS students and to all kind of programmers (novice, advanced, pro). Ok, you will need very strong math background, or you will have to learn math - but it is worth it!
Just don't take this book, read it from cover to cover and expect to become master of programming. You will learn how to write great algorithms, how they work and how to use it (in real life situations), but still you will need practice!
Worth every dollar!

Book offers clear examples and a good balance of the math and algorithms involved. The multiple implementations of various "core" algorithms allows the designer/developer multiple options for varied solutions.

Book is useful for everybody related to software development, has good description of basic algorithms and data structures.
Also should be good for computer science students, since is pretty simple and doesn't require deep math knowledge.

You are better off buying the third edition of the book! This edition leaves a lot of things unexplained and leaves you wondering how to do this or that. The most frustrating part is when the author gives you little to no detail about a certain thing and then asks you to implement that thing in the exercise. The previous edition of the book is more complete than this one, so whoever wants to buy this book, buy the 3rd edition!

I enjoyed this book. For the few chapters I needed to read to understand my lectures better, it helped to clarify things in ways that complemented my professor very well.

I enjoyed the ease of reading for many chapters, but some of them went way beyond my course and got too complex.

Only caveat I'd mention is that his practices for Java development will seem weird to anyone coming from professional Java development. Honestly those bad practices were too much of a distraction for me as a professional looking to review core concepts.

Reader's background: One Java basic programming course before reaching this book.
The better title for this book should be "Data Structure and Algorithms in Java", since it implements all programs in Java and utilizes many language specific features.

This book has both pros and cons as below:
pros:
Good examples drawn in charts or graphs, comprehensive codes.
Free courses on Coursera.
cons:
Wording sometimes confused readers due to different meanings with the same term between sentences.
Use non-traditional asymptotic symbols instead of big-O, which needs extra time to get used to it.

Overall this is a good book for people who needs supplementary materials and real codes for algorithms, but I won't recommend it to self-learning readers due to the cons mentioned above.

This book is a great foundation for learning the fundamentals of developing software algorithms. I would recommend that the author consider a second addition that would include using the SCALA programming language in addition to the JAVA language.

This is the most comprehensive algorithm book I've ever read.
According to my memory, the one of the authors, professor Sedgewick, might be the one of professor Donald Knuth's students.

Anyway, it covers the practical topics of the algorithms such as list, stack, queue, sort, search, graph, string with very detailed explanation and many diagrams.
Although the authors have left the code implementations as exercises and the codes in the book need to be tuned and revised for applying into the real field.

I think of it's the best introduction to get a good insight to algorithm!

An excellent resource for anyone interested in computer science. I thoroughly enjoyed reading (and re-reading) it! I feel so much more confident with sorting and searching algorithms and the like. This is a great investment.

"Algorithms" (4th edn) by Robert Sedgewick and Kevin Wayne (published
by Addison-Wesley in March 2011) is one of the best computer science
books I have ever read. It should be required reading for all CS
students and all programmers - it aims to cover the "50 algorithms
every programmer should know". Below I discuss some of the main
reasons why I think the book is so good.

Unlike its main rival, "An introduction to algorithms" by Cormen,
Leiserson, Rivest and Stein (CLRS), "Algorithms" contains actual
source code (written in a subset of Java). The importance of this
cannot be overstated: it means students can actually use the
algorithms to solve real problems. This enables a wealth of
interesting and motivating applications --- from web search to
genomics --- which are sprinkled throughout the book. (Source code and
data are available on the book's website.)

A natural worry with real code is that it will obscure the basic
ideas. However, by careful useful of abstract data types (classes
such as queues, bags, hash tables, trees, DAGs, etc), the authors have
done a masterful job at creating extremely concise and readable
implementations.

Using real code also forces one to address important implementation
details that are easy to overlook. For example, it is well known that
mergesort requires auxiliary memory. In the CLRS pseudocode, they
allocate temporary storage space inside their merge routine. In
practice it is much more efficient to allocate temporary storage space
once, and then pass this in as a pointer to the merge function (or let
it be a private member of the mergesort class). Where else can you
learn such important tricks?

In addition to presenting the code, there are of course accompanying
English explanations of the methods, which are very clear. One unique
thing about "Algorithms" is that there are also many detailed worked
examples, illustrating the behavior of the algorithms while running on
actual data (something that is hard to do unless you actually
implement all the algorithms!)

Another strength is that the book is that exemplifies good software
engineering practice: write the API first, devise unit tests and/or
implement applications ("clients") that use the data structure or
algorithm, and only then worry about how to implement the
API. Furthermore, multiple implementations of the API are usually
discussed, with different tradeoffs between simplicity, speed and
memory use.

For data structures, it is obviously natural to use classes, but they
also adopt this approach for many algorithms, esp. graph processing
ones. This allows the algo to do pre-processing and to store internal
state, and then to provide a service to the caller. This is more
general than the standard stateless functional view of algorithms.

Each section of the book has a large number of exercises, classified
into "simple", "creative" and "experimental". Solutions to some
exercises are available online.

An unusual feature of the book is that it contains a lot of empirical
algorithmics, in addition to theory. That is, it shows actual running
times of different implementations on problems of different sizes, and
uses this to supplement traditional theoretical analysis.

A small bonus relative to CLRS is that the book is slightly shorter
(~ 1000 pages instead of 1300). In addition it is available in Kindle
format, which means one just has to carry around an ipad instead of a
back-breaking tome. (The formatting of the Kindle edition is not
perfect, however.)

Not surprisingly, the content of "Algorithms" overlaps a lot with
CLRS. This is not obvious from the table of contents, which only
gives a high level view of the book. I have therefore created a more
detailed list of topics (see below).

The overall ordering and flow of the book is great: ideas (and code)
that are introduced early on get re-used in several places later in
the book (e.g., heaps -> priority queues -> Prim's algo for min
spanning trees). The topics also become more advanced. Consequently,
the book is best read sequentially. It is worth reading the whole thing.

Kevin Murphy
Prof. of Computer Science
University of British Columbia

Below I give a detailed summary of the topics in the book,
since this is not apparent from the table of contents.

1. Fundamentals

1.1 Basic programming model
- Intro to Java
- APIs and libraries
- Binary search (recursion)

1.2 Data abstraction
- Basics of OOP
- Avoiding 'wide' interfaces

1.3 Bags, queues and stacks
- Generics (known as templates in C++)
- Iterators
- Dijkstra's 2 stack algo for evaluating arithmetic expressions
- Resizing arrays
- Linked lists, pointers

1.4 Analysis of algorithms
- empirical algorithmics
- big O notation ("linearithmic" as a term for O(N log N))
- Randomized algorithms
- Memory usage

1.5 Case study: Union-find
- Application: Dynamic connectivity (are p,q in same set?)
- 3 implementations, culminating in the classic algorithm

2. Sorting

2.1 Elementary sorts
- Selection sort
- insertion sort
- shell sort

2.2 Mergesort
- Top-down (recursive)
- Proof that running time is N log N
- Bottom-up
- proof that lower bound for sorting requires N log N compares

2.3 Quicksort
- implementation
- analysis
- 3 way partitioning to speedup case of equal keys
- lower bound for sorting is N*entropy of key distrib.

2.4 Priority queues
- heaps
- priority queue,
- top N items from a list using PQ
- multiway merge of N sorted lists using indexed PQ
- heapsort
- comparison of sorting algos (speed, stability, in place, extra space)
- order statistics/ median finding in O(N) time

3. Searching

3.1 Symbol tables (aka associative arrays)
- ST vs ordered ST (where keys can be compared, so can get min and max)
- count word frequencies in a large document
- sequential search through unordered linked list
- binary search through ordered array

3.2 Binary search trees
- BST property (parent is bigger than left child, smaller than right)
- get and put implementation and analysis O(log N) time
- find min, delete min, delete any node
- inorder traversal

3.3 Balanced search trees
- 2-3 trees and red-black trees

3.4 Hash tables
- hash functions (eg modular hashing with Horner's rule)
- separate chaining
- linear probing

3.5 Applications
- Deduplication
- Dictionary lookup
- inverted index
- file index
- sparse matrix vector multipication

4. Graphs

4.1 Undirected graphs
- Adjacency list representation
- Depth first search
- Breadth first search
- single source shortest paths using bfs
- connected components usign dfs
- is G acyclic using dfs
- is G bipartite using dfs
- Kevin Bacon game (degrees of separation)

4.2 Directed graphs
- Multi-source reachability
- Application to mark-sweep garbage collection
- Cycle detection using dfs
- topological sort (reverse of post order)
- Kosaraju's algo for strongly connected components
- Transitive closure (all pairs reachability)

4.3 Min spanning trees of undirected weighted graphs
- Prim's algo
- Kruskal's algo

4.4 Shortest paths in weighted digraphs
- Dijkstra's algo
- Shortest paths in weighted (possibly -ve) DAGs
- Critical path method for scheduling
- Shortest paths in weighted cyclic digraphs (Bellman-Ford and -ve cycle detection )
- Application to arbitrage

5. Strings

5.1 String sorts
- key indexed counting (radix sort)
- least significant digit (LSD) sorting
- most significant digit (MSD) sorting for variable length strings
- 3-way string quicksort for repeated prefixes.

5.2 Tries
- R-way trie
- longestPrefixOf
- Ternary search tries (BST representation of R-way array)

5.3 Substring search
- brute force method
- KMP method
- Boyer-Moore method
- Rabin-Karp fingerprint

5.4 Regular expressions
- Syntax of regexp
- Check if string in language using non-deterministic finite automaton

5.5 Data compression
- Setup
- Run-length encoding
- Huffman compression
- LZW compression (using tries)

6. Context

6.1 Event driven simulation using PQs

6.2 B-trees

6.3 Suffix arrays.
- Find longest repeated substring.
- Indexing a string (keyword in context)

6.4 Ford-Fulkerson maxflow.
- Find shortest augmenting path.
- Maximum bipartite matching reduces to maxflow
- maxflow and shortest paths reduce to linear programming

6.5 NP completeness

Quite hard to fully understand unless you do the exercises and take your time. I read during my commute so this didn't work out that well. I didn't really like the layout of the Kindle version (there's not enough distinction between major and minor chapters to know when the topic changes) and the writing style (expressive long sentences) which I found hard to follow occasionally.

On the positive side, as this was my first book on algorithms, I managed to learn the terminology and ideas behind the algorithms as well as some ideas how I would go about implementing my own. However, if you're looking for an easy-to-read introductory book about algorithms I would recommend finding something else.

After having several attempts with Knuth I have tried this book.
The book gives just the things you need in practice as a Java developer.
However, it assumes some background in OOP and some Java experience.
Nevertheless I highly recommend it.

I was introduced to Sedgewick by the wonderful video lectures he has recorded on the subject, and purchased the book only later. The pages are becoming dog-eared already. What a boon to students of computer science. Don't just soak up the fully-coded algorithms: work a few of his (and Wayne's) puzzles and exercises and try to translate some of it into some other language. The latest edition and the booksite are all in Java which makes a few things a little too easy in my view, but is ideal for focusing on the foundational principles rather than the details of implementation. The booksite completes the picture of how this sort of project should be done. There's enough there to keep one busy for several lifetimes, even if he or she has no priorities being imposed by nearby professors or managers.

I've recently switched to this from the Cormen et al. book for the algorithms class I teach at Lewis & Clark College (a small liberal arts college in Portland, OR). The main difference is that this book focuses on practice, where Cormen focuses more on mathematical theory. This book seems a better fit for my students and my style of teaching.

Pros:
* Reasonable scope for a semester. Teaching from this book for the first time, I covered four of the six large chapters, plus part of the fifth.
* Explanations, diagrams, and examples are clear and concise.
* The authors know their stuff and don't hesitate to explain it. For example, they know why a hash table index should be computed as
(key.hashCode() & 0x7fffffff) % M
(where M is the size of the table) instead of
Math.abs(key.hashCode()) % M
* The slides provided on the book website are outstanding.
* Examples in the book and on the slides come from a wide variety of applications. They demonstrate cases where using the efficient algorithm really matters.
* One of the authors responds quickly to questions and errata. (As with any textbook, be sure to check the website and write the corrections into your copy.)

Cons:
* The code does not always follow Java style conventions. For example, the authors will use non-private fields and one-letter, upper-case variable names. The many classes provided are all in the default package. It is not clear how much of this stems from deliberate decisions in the name of clarity and conciseness and how much from the authors not being "native" Java speakers.
* Some of the proofs are a bit laconic ("immediate from inspection of the code").
* The authors use an unusual ~ notation instead of the more widely-used Big-Theta/Big-O notation (although the latter is explained in passing). The ~ notation is more precise, as it does not omit the constant factor, but students may need additional practice with the standard notation.

There are quite a lot of typos and errors. Though the book's website has a list of those errors, it's not very helpful because you won't refer to that webpage while you are reading. It's already a 4th Edition of the book but the rate of error is very alarming. Could have been a lot better.

Other reviews on this fine text are for older editions with pseudo code. Sedgewick and Wayne have completely revised this new Fourth Edition with plentiful Java scripts for a vast range of applications. A brand new website at Princeton is dedicated to this book and has visualizations, much more code, exercises, answers, bib links, full implementations of many problems, and a complete online summary and synopsis of the book.

The authors suggest this is for a second course in CS, but many serious students, whether independent or in undergrad, will find it useful for self teaching as well. In fact, the new website has self teaching resources if you are "going it alone" in your initial study of algorithms.

Algos cannot really be separated from their underlying data structures, and a serious new addition to this printing and edition is a much better backgrounder on the most up to date data structures, using hyper modern examples like the store and Google.

This book covers the basics, and is not an encyclopedia or reference book. It has a lot of detailed descriptions and visuals, and takes the time to be sure the student "gets" the point. In a way, it is in competition with Sedgewick's own Algorithms in C++, Parts 1-4: Fundamentals, Data Structure, Sorting, Searching (Pts. 1-4), which is now in its third edition, and more terse, advanced and encyclopedic. If you want a thorough understanding of the whole field, you probably need both if you're just starting out in the field.

If you're a beginning programmer, and want to get into the underlying logic of sorts, searches, graphs, strings and other fundamentals that drive modeling and the web, this is the place to start.

This book is a very good introduction to algorithms. The paradigm that the book uses with an explanation of the problem, then the API, then the algorithm, and then the implementation makes difficult algorithms clear. The visuals that Sedgewick has created are very helpful.

I love this book very much.
I wonder programmers prefer this book to CLRS because in this book, object-oriented java programs you can run are included.
Pictures which explain algorithms are very beautiful.

I wonder programmers entertain this book very much.

The numbers of pages of this book is huge, but materials in this book are few.
But it's ok.

Well, no matter if you grab Algorithms, Algorithms in C, or Algorithms in C++, the books are basicly all the same. They are very comprehensive and easy, even usable for a pupil at highschool, in my eyes the best book too approach Algorithms. It for sure is the ultimate bible for Undergratuates in Compscience during their first year, but it for sure lacks all the in-depth information on math and abstract computers ... If you just need some powerful Algorithms and need some source, this is the one to stick for, it helped me quite a couple times, although I never had to code in pascal,C or C++, but as remarked above, it's only for beginners, as you stick deeper in to compscience, as in yer 2nd year, you need a book sticking much deeper into theory, I guess, Donald E. Knuth is the best choice in English language for that kinda stuff.

When I first opened the book, my initial inclination was to return it. The title is deceptive since it's examples are more C like with hardly any of the C++ OO features thrown in. And since I've designed and help wrote 3D Non-Uniform Bspline (NURBS) surfaces with cutouts in C for a graphics-CAD corp. for which I was awarded patent and a company award (and with $), last thing I needed was some trivia.
I was pleasantly surprised at how readable this book was. When I was in school long ago, algorithm courses were full of heavily mathematical proofs and based on the Turing Machine model (Yuck!).
While I'm familiar with most of the algorithms in the book, his very readable style and explanations is a great refresher and reference. I'm throwing my old college algorithm books out and keeping this.

I'm a learned industrial engineer in electronics but got into informatics right after my degree. So I never had a course on algorithmic and had to learn nearly everything by myself.
After some years of working in the field, I tought it was maybe time to get some background on the subject so I got this (now an outdated edition) of the book.
Well, it was the book it took the longest to me to finish in the informatics field.
The book explains a whole bunch of basic and more advanced general-purpose algorithms, and so has a good coverrage of the subject.
However, there are two problems with the book:
1) The coding style is very bad: the author likes to use global variables, and variable names are often very cryptic. Example:
* p = parent
* g = grandparent
* gg = greatgrandparent
* c = child
* x = current node
* y = temporary node
...
2) You cannot read this book's chapters in a random way: you have to follow the chapter ordering, because often knowledge of later chapters is based of knowledge of earlier chapters, and, because of the bad coding style you have to often remember the meaning of the cryptic variable names several chapters later when they are reused. If you're like me, you've forgotten the meaning, which means reread that damn chapter, which in turn can again be based on an earlier chapter. You get the picture why it took me so long?