Customer Reviews

102
4.5 out of 5 stars
Algorithms (4th Edition)
Format: HardcoverChange
Price:$61.81 + Free shipping with Amazon Prime
Your rating(Clear)Rate this item


There was a problem filtering reviews right now. Please try again later.

302 of 314 people found the following review helpful
on May 22, 2011
Format: Hardcover
"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
99 commentsWas this review helpful to you?YesNoSending feedback...
Thank you for your feedback.
Sorry, we failed to record your vote. Please try again
Report abuse
48 of 49 people found the following review helpful
on May 9, 2012
Format: Hardcover
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.
0CommentWas this review helpful to you?YesNoSending feedback...
Thank you for your feedback.
Sorry, we failed to record your vote. Please try again
Report abuse
69 of 74 people found the following review helpful
Format: Hardcover
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 Amazon 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.
11 commentWas this review helpful to you?YesNoSending feedback...
Thank you for your feedback.
Sorry, we failed to record your vote. Please try again
Report abuse
21 of 23 people found the following review helpful
on August 23, 2011
Format: Kindle EditionVerified Purchase
After 20 years doing kernel level programming and device drivers, process control systems and other realtime work, most of my algorithm knowledge has vanished from disuse. So now I'm moving back into higher-level work and I was in trouble!

This books covers it all, and it's far more readable than the Knuth books I grew up on. I really appreciate the implementation examples as well, a few unclear spots became obvious when I looked at the code.

For anyone shifting gears and needing to freshen up their programming basics, I highly recommend this book!
0CommentWas this review helpful to you?YesNoSending feedback...
Thank you for your feedback.
Sorry, we failed to record your vote. Please try again
Report abuse
38 of 45 people found the following review helpful
on March 12, 2013
Format: Kindle EditionVerified Purchase
Let me say first of all that I purchased the first printing of this text a little over a year ago. I actually like this book and believe that if you can identify the errors, it is a sufficiently instructive text.

However, between the first printing and the current third (3rd) printing, the authors have corrected over 105 errors in the book. Now, if this were a novel, it wouldn't be such a big deal. But people are using this book to learn material that will hopefully serve as a foundation for further learning. So not only does the error rate result in a waste of time but you are sometimes harming your learning process by absorbing information that is just plain wrong.

Please note that if you purchase the Kindle version of this book, your problems will compound even further since there is no quick way to annotate the many errors in the text. What this means is that before you can even begin learning the material from the book, you are first forced to sit with all 3 errata printing sheets, and manually insert comments throughout the Kindle text....for 105+ coding and textual errors! You are, in essence, re-authoring large swathes of the textbook before you can even use it!

Oh, but wait.... I forgot to mention that the Kindle version does not have PAGE NUMBERS?!! So, even with the errata in-hand (which reference errors by paper book page number), you are often unable to find the precise location of the error... particularly when the error is from a code example.

Having to correct dozens upon dozens of errors by hand for a book this size (with no page numbers!) before you can use it is INEXCUSABLE and borders on fraud. Authors and Amazon both seem very eager to chuck these electronic books at customers but from what I've seen, very little (if anything) is done by either party to ensure that electronic versions of these books receive errata updates. Either Amazon needs to address this, or authors need to work with Amazon to provide corrected, updated ePub versions of these texts to customers that have purchased them.
99 commentsWas this review helpful to you?YesNoSending feedback...
Thank you for your feedback.
Sorry, we failed to record your vote. Please try again
Report abuse
16 of 19 people found the following review helpful
on August 12, 2014
Format: Hardcover
I am a little surprised by all of the great reviews given the quality of the writing. There's plenty of good material, but the book is needlessly complex. The sentences get so twisted that even the authors start to lose track of them.

Writing like this permeates the entire tome, but in planning this review, I happened to flip to page 86. The page focuses on Java methods. Here are a few examples, just from this page, of why I am writing this review:

They say, "To implement data-type operations (the behavior of each object) we implement instance methods with code that is precisely like the code that you learned in section 1.1 to implement static methods (functions)."

Translation: Writing instance methods in Java is just like writing static methods.

The complexity is unnecessary, and the sentence turns out not to be correct. Later in the paragraph, they explain the key difference between the instance methods and static methods, and they reveal that "precisely" was precisely the wrong word choice; they meant to say "much". This may seem a picky complaint, but it is important. A good technical book must be either crystal clear or extremely accurate. To be dense and careless is unfair to the reader, who must take the time to decode each and every word carefully in order to determine the meaning.

The very next sentence goes on to accidentally explain that *every* Java method must have a return statement. Here it is:

"Each instance method has a return type, a signature (which specifies its name and the types and names of its parameter variables), and a body (which consists of a sequence of statements, including a return statement that provides a value of the return type back to the client)."

I say "accidentally" because it's pretty clearly unintentional. It's not at all that the authors don't know Java - they obviously do! - it's rather that they appear to get lost in their own unwieldy sentences. Clearly, many correct Java methods do not contain return statements, and this is illustrated beautifully by the two short and elegant examples of Java code provided on the page!

Again, from the same page: "How do we specify which objects instance variables we want to use? If you think about this question for a moment, you will see the logical answer: a reference to a variable in an instance method refers to the value for the object that was used to invoke the method."

Translation: When there is an instance of some object, its methods can only access its own variables, not those of other instances. Put another way, if some code were to call myThing.getInfo(), getInfo() would only be able to use variables stored inside of myThing.

I was hoping to use this book with my students, but I am disappointed that the authors seem to have lost sight of students as readers. The students who learn out of these books don't yet know the material. It takes careful crafting to unpack difficult ideas for a reasonably motivated novice. The authors didn't take this challenge seriously enough, leaving the reading experience very frustrating for the audience that matters the most.

I still hold high hopes for future editions. In spite of this review, there are some really good aspects to this work. I have no doubt that, if the authors took the time to switch from an academic style of writing to a mode pedagogical one, this book could become the truly extraordinary resource it is meant to be. The authors have high aspirations, but they haven't achieved them yet.
0CommentWas this review helpful to you?YesNoSending feedback...
Thank you for your feedback.
Sorry, we failed to record your vote. Please try again
Report abuse
10 of 11 people found the following review helpful
on December 13, 2011
Format: HardcoverVerified Purchase
This is a great book for anyone who knows java and wants to understand Algorithms. This covers lot of basic Data Structures and Algorithms written in Java with generics. I have read lot of data structure and algorithm books, but this one especially is for java programmers. Most of the algorithm books, only cover the basic pseudo code and leave the implementation, but this one gives a complete implementation of most of the famous algorithms. One more thing, I like particularly about the book is the supporting website, which has lot of test data and the author has provided test cases for each of the programs given in the book.

This is not all, every chapter comes with lot of interesting compilation of exercises and creative problem, which will make your fundamentals clear. I think it is a must read for anyone who wants to really brush up on their data structure and algorithms fundamentals.

Thanks for writing this great book.
0CommentWas this review helpful to you?YesNoSending feedback...
Thank you for your feedback.
Sorry, we failed to record your vote. Please try again
Report abuse
7 of 7 people found the following review helpful
on April 6, 2012
Format: HardcoverVerified Purchase
This is the book I wish I had, way back in the day, in my Algorithms class. The examples are very well presented. Concepts are explained, and the code examples are spot on. The book presents a library of routines that are built on in successive chapters. This makes skipping ahead to specific examples somewhat challenging. The code and libraries are available on-line.

Everything is in JAVA, which was perfect for my use.

I've suggested that members of my team take a look at this book - not as required reading, but as a tool to have in their toolbox.

A quest for some shortest path algorithms to use in optimizing warehouse operations brought me to this book. I knew the general algorithm I wanted to use, but needed some help. Two minutes looking at an on-line chapter was all it took to convince me to purchase the book. I'm glad I did.
0CommentWas this review helpful to you?YesNoSending feedback...
Thank you for your feedback.
Sorry, we failed to record your vote. Please try again
Report abuse
8 of 9 people found the following review helpful
VINE VOICEon May 18, 2014
Format: HardcoverVerified Purchase
I bought this book as a supplement to Cormen's Algorithms book--sometimes I find it handy to have two different explanations of the same concepts. Some of the explanations in this book are significantly more clear than the explanations in Cormen's book--sometimes Cormen gets a bit too wrapped up in the mathematical syntax without enough words around the math and I find this book very handy to back fill those missing words. So I like the conversational style of this book.

There's a few things I strongly dislike about this book--

1. The Java syntax is massively distracting. I'd rather have pseudocode.

2. The pages are glossy--a lot of books are doing this, but it causes reflections on the pages, which makes it more optically difficult to read. This is infuriating!

3. The index is fairly bad. For example, 'string matching' isn't in the index, but Knuth Morris Pratt IS in the index.

That said, I use this book often when working through new algorithm design when Cormen lets me down...but this is never my first go-to-book.
0CommentWas this review helpful to you?YesNoSending feedback...
Thank you for your feedback.
Sorry, we failed to record your vote. Please try again
Report abuse
5 of 5 people found the following review helpful
on October 31, 2012
Format: Kindle EditionVerified Purchase
For the experienced programmer or novice this a book you will appreciate and be glad you purchased.

If genius is like it is said, the ability to make a complex subject simple to understand then Robert Sedgewick is truly a genius.

Sedgewick explores some of the top algorithms in use today and focuses on their application, and implementation. Each algorithim, it's application, and performance is also summarized for quick reference.

Sedgewick steps through the algorithm with dynamic visual depictions of the data structures involved.

I can't say enough good things this book. This book assists the developer or programmer to effectively learn and use algorithms, and get on with life. It's rare to see a book this well written for the purpose of learning as well as reference. Especially on a subject as involved as algorithms.

In conjunction with the book, I would recommend using the online MOOC courses, Algorithms Part I, and Algorithms Part II, available at Princeton University. Here, Sedgewick, has developed some enjoyable and instructional video lectures and presentations of the book.

I would also like to thank Robert Sedgewick for this brilliant piece of work, and Princeton University for bringing it online.
0CommentWas this review helpful to you?YesNoSending feedback...
Thank you for your feedback.
Sorry, we failed to record your vote. Please try again
Report abuse
     
 
Customers who viewed this also viewed
Introduction to Algorithms, 3rd Edition
Introduction to Algorithms, 3rd Edition by Thomas H. Cormen (Hardcover - July 31, 2009)
$77.47

The Algorithm Design Manual
The Algorithm Design Manual by Steve Skiena (Hardcover - July 26, 2008)
$81.65

 
     

Send us feedback

How can we make Amazon Customer Reviews better for you?
Let us know here.

Your Recently Viewed Items and Featured Recommendations 
 

After viewing product detail pages, look here to find an easy way to navigate back to pages you are interested in.