Algorithms / Edition 4

Hardcover (Print)
Rent
Rent from BN.com
$17.63
(Save 79%)
Est. Return Date: 10/20/2014
Used and New from Other Sellers
Used and New from Other Sellers
from $68.45
Usually ships in 1-2 business days
(Save 19%)
Other sellers (Hardcover)
  • All (21) from $68.45   
  • New (13) from $68.66   
  • Used (8) from $68.45   

Overview

This fourth edition of Robert Sedgewick and Kevin Wayne’s Algorithms is the leading textbook on algorithms today and is widely used in colleges and universities worldwide. This book surveys the most important computer algorithms currently in use and provides a full treatment of data structures and algorithms for sorting, searching, graph processing, and string processing -- including fifty algorithms every programmer should know. In this edition, new Java implementations are written in an accessible modular programming style, where all of the code is exposed to the reader and ready to use.

The algorithms in this book represent a body of knowledge developed over the last 50 years that has become indispensable, not just for professional programmers and computer science students but for any student with interests in science, mathematics, and engineering, not to mention students who use computation in the liberal arts.

The companion web site, algs4.cs.princeton.edu contains

  • An online synopsis
  • Full Java implementations
  • Test data
  • Exercises and answers
  • Dynamic visualizations
  • Lecture slides
  • Programming assignments with checklists
  • Links to related material

The MOOC related to this book is accessible via the "Online Course" link at algs4.cs.princeton.edu. The course offers more than 100 video lecture segments that are integrated with the text, extensive online assessments, and the large-scale discussion forums that have proven so valuable. Offered each fall and spring, this course regularly attracts tens of thousands of registrants.

Robert Sedgewick and Kevin Wayne are developing a modern approach to disseminating knowledge that fully embraces technology, enabling people all around the world to discover new ways of learning and teaching. By integrating their textbook, online content, and MOOC, all at the state of the art, they have built a unique resource that greatly expands the breadth and depth of the educational experience.

Read More Show Less

Product Details

  • ISBN-13: 9780321573513
  • Publisher: Addison-Wesley
  • Publication date: 3/23/2011
  • Edition description: New Edition
  • Edition number: 4
  • Pages: 976
  • Sales rank: 129,011
  • Product dimensions: 7.40 (w) x 9.10 (h) x 1.40 (d)

Meet the Author

Robert Sedgewick has been a Professor of Computer Science at Princeton University since 1985, where he was the founding Chairman of the Department of Computer Science. He has held visiting research positions at Xerox PARC, Institute for Defense Analyses, and INRIA, and is member of the board of directors of Adobe Systems. Professor Sedgewick’s research interests include analytic combinatorics, design and analysis of data structures and algorithms, and program visualization. His landmark book, Algorithms, now in its fourth edition, has appeared in numerous versions and languages over the past thirty years. In addition, with Kevin Wayne, he is the coauthor of the highly acclaimed textbook, Introduction to Programming in Java: An Interdisciplinary Approach (Addison-Wesley, 2008).

Kevin Wayne is the Phillip Y. Goldman Senior Lecturer in Computer Science at Princeton University, where he has been teaching since 1998. He received a Ph.D. in operations research and industrial engineering from Cornell University. His research interests include the design, analysis, and implementation of algorithms, especially for graphs and discrete optimization. With Robert Sedgewick, he is the coauthor of the highly acclaimed textbook, Introduction to Programming in Java: An Interdisciplinary Approach (Addison-Wesley, 2008).

Read More Show Less

Table of Contents

Preface viii

Chapter 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

Chapter 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

Chapter 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

Chapter 4: Graphs 515

4.1 Undirected Graphs 518

4.2 Directed Graphs 566

4.3 Minimum Spanning Trees 604

4.4 Shortest Paths 638

Chapter 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

Chapter 6: Context 853

Index 933

List of Algorithms 954

List of Clients 955

Read More Show Less

Customer Reviews

Average Rating 4.5
( 3 )
Rating Distribution

5 Star

(2)

4 Star

(0)

3 Star

(1)

2 Star

(0)

1 Star

(0)

Your Rating:

Your Name: Create a Pen Name or

Barnes & Noble.com Review Rules

Our reader reviews allow you to share your comments on titles you liked, or didn't, with others. By submitting an online review, you are representing to Barnes & Noble.com that all information contained in your review is original and accurate in all respects, and that the submission of such content by you and the posting of such content by Barnes & Noble.com does not and will not violate the rights of any third party. Please follow the rules below to help ensure that your review can be posted.

Reviews by Our Customers Under the Age of 13

We highly value and respect everyone's opinion concerning the titles we offer. However, we cannot allow persons under the age of 13 to have accounts at BN.com or to post customer reviews. Please see our Terms of Use for more details.

What to exclude from your review:

Please do not write about reviews, commentary, or information posted on the product page. If you see any errors in the information on the product page, please send us an email.

Reviews should not contain any of the following:

  • - HTML tags, profanity, obscenities, vulgarities, or comments that defame anyone
  • - Time-sensitive information such as tour dates, signings, lectures, etc.
  • - Single-word reviews. Other people will read your review to discover why you liked or didn't like the title. Be descriptive.
  • - Comments focusing on the author or that may ruin the ending for others
  • - Phone numbers, addresses, URLs
  • - Pricing and availability information or alternative ordering information
  • - Advertisements or commercial solicitation

Reminder:

  • - By submitting a review, you grant to Barnes & Noble.com and its sublicensees the royalty-free, perpetual, irrevocable right and license to use the review in accordance with the Barnes & Noble.com Terms of Use.
  • - Barnes & Noble.com reserves the right not to post any review -- particularly those that do not follow the terms and conditions of these Rules. Barnes & Noble.com also reserves the right to remove any review at any time without notice.
  • - See Terms of Use for other conditions and disclaimers.
Search for Products You'd Like to Recommend

Recommend other products that relate to your review. Just search for them below and share!

Create a Pen Name

Your Pen Name is your unique identity on BN.com. It will appear on the reviews you write and other website activities. Your Pen Name cannot be edited, changed or deleted once submitted.

 
Your Pen Name can be any combination of alphanumeric characters (plus - and _), and must be at least two characters long.

Continue Anonymously
Sort by: Showing all of 3 Customer Reviews
  • Anonymous

    Posted May 14, 2013

    "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

    1 out of 1 people found this review helpful.

    Was this review helpful? Yes  No   Report this review
  • Anonymous

    Posted January 28, 2014

    Vnm Iio n .m n

    Yjnj

    0 out of 1 people found this review helpful.

    Was this review helpful? Yes  No   Report this review
  • Anonymous

    Posted July 13, 2011

    No text was provided for this review.

Sort by: Showing all of 3 Customer Reviews

If you find inappropriate content, please report it to Barnes & Noble
Why is this product inappropriate?
Comments (optional)