Algorithms / Edition 4

"Algorithms" (4th edn) by Robert Sedgewick and Kevin W

"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 met

Was this review helpful? Yes  NoThank you for your feedback.   Report this reviewThank you, this review has been flagged.

No text was provided for this review.