Introduction to Algorithms

Key differences between 3rd and 2nd editions

• Time lapse between previous and latest publications: 8 years (2001 vs 2009).
• The first edition of Introduction to Algorithms textbook, published in 1990, was also known as "The Big White Book of Algorithms".
• The hardcover edition does not include a dust jacket.
• The Third Ed. includes 100 new exercises and 28 new problems.
• A quick look at the table of contents shows that key Second edition's chapters and sections present in the Third edition.
• Main changes between the Second and Third editions:
• Two chapters have been removed:
• 19 "Binomial Heaps"
• 27 "Sorting Networks". The zero-one principle can be found in the 3rd Ed. as the 0-1 sorting lemma in Problem 8.7.
• Chapter 4 on divide-and-conquer algorithms has new section on solving the maximum-subarray problem with the divide-and-conquer technique.
• Chapter 15 now starts with the new section (instead of "Assembly-line scheduling" in the 2nd Ed) explaining how to convert the problem of rod cutting into algorithm, using dynamic programming. The subsection "Subproblem graphs" outlines how subproblem graph can be used determine the running time of the dynamic programming algorithm.
• Completely new Chapter 20 "Van Emde Boas Trees" covers:
• various approaches for storing a dynamic data set
• design of recursive data structure, how to perform operations on a proto-Van Emde Boas structure.
• design of data structure that is similar to the proto-vEB structure but stores more information.
• In the Chapter 26 the material on flow networks now bases flows entirely on edges.
• Completely new Chapter 27 "Multithreaded Algorithms" introduces:
• the dynamic multithreading model and the metrics of work, span, and parallelism.
• how to multiply matrices with multithreading.
• more difficult task of multithreading merge sort.
• New Appendix D "Matrices" presents material on matrix basics.
• The syntax of pseudo-code has been slightly changed. "D" is now used to indicate assignment and "=" to test for equality, just as C, C++, Java, and Python do. Eliminated the keywords do and then and adopted "/ /' as comment-to-end-of-line symbol. Dot-notation is used to indicate object attributes.