preface difficult for readers to actually use the code as resultin this edition the online code represents class templates as single unitwith no separation of interface and implementation provides review of the +features that are used throughout the text and describes our approach to class templates appendix describes how the class templates could be rewritten to use separate compilation complete versions of the data structuresin both +and javaare available on the internet we use similar coding conventions to make the parallels between the two languages more evident summary of the most significant changes in the fourth edition the fourth edition incorporates numerous bug fixesand many parts of the book have undergone revision to increase the clarity of presentation in additionr includes implementation of the avl tree deletion algorithm-- topic often requested by readers has been extensively revised and enlarged and now contains material on two newer algorithmscuckoo hashing and hopscotch hashing additionallya new section on universal hashing has been added also new is brief discussion of the unordered_set and unordered_map class templates introduced in ++ is mostly unchangedhoweverthe implementation of the binary heap makes use of move operations that were introduced in ++ now contains material on radix sortand new section on lower-bound proofs has been added sorting code makes use of move operations that were introduced in ++ uses the new union/find analysis by seidel and sharir and shows the om (mnbound instead of the weaker om logn bound in prior editions adds material on suffix trees and suffix arraysincluding the linear-time suffix array construction algorithm by karkkainen and sanders (with implementationthe sections covering deterministic skip lists and aa-trees have been removed throughout the textthe code has been updated to use ++ notablythis means use of the new ++ featuresincluding the auto keywordthe range for loopmove construction and assignmentand uniform initialization overview contains review material on discrete math and recursion believe the only way to be comfortable with recursion is to see good uses over and over thereforerecursion is prevalent in this textwith examples in every except also includes material that serves as review of basic +included is discussion of templates and important constructs in +class design deals with algorithm analysis this explains asymptotic analysis and its major weaknesses many examples are providedincluding an in-depth explanation of logarithmic running time simple recursive programs are analyzed by intuitively converting them into iterative programs more complicated divide-and-conquer programs are introducedbut some of the analysis (solving recurrence relationsis implicitly delayed until where it is performed in detail