7 Resources
The resources listed on this page are not required for the course, or likely to be of much use in fulfilling course requirements, but they may be of interest to those wishing to learn more.
I don’t particularly care for either of them, but I would be remiss if I did not mention the two major textbooks for a conventional treatment of a data structures course. Robert Sedgewick’s "Algorithms" was first published in 1983. It has been through many editions, and currently exists in two versions, one with this title that uses Java as the implementation language, and one called "Algorithms in C++" that has some material not in the other version. Cormen, Leiserson, and Rivest’s "Introduction to Algorithms" was first published in 1990; the current edition, with the addition of fourth author Stein, is the fourth. The former is often used as a CS 240 textbook, and the latter as a CS 341 textbook.
The book "Purely Functional Data Structures" was first published in 1998, and is a version of author Chris Okasaki’s PhD thesis from 1996. A little of this material is covered in CS 240E, but the book goes much further than we do (as you might expect of PhD material), and is best approached as supplementary reading after the course has been completed. Warning: the book uses an imaginary extension of Standard ML that does not exist anywhere, with Haskell code in the appendix.
Donald Knuth’s "The Art of Computer Programming" is a canonical reference, but it is rather difficult to read casually, or even systematically. Many major results are given as exercises with high difficulty ratings. Learn where it is in the library so that you can dip into it when you want a sense of the context surrounding some result.
If you are interested in details of the Akra-Bazzi method for recurrences, you might look at the expositions by Tom Leighton and by Kurt Mehlhorn, both of which provide a citation for the original paper.
The material on balanced binary search trees in this course is partly based on a textbook in progress by Guy Blelloch and Umut Acar for a course on data structures at CMU that emphasizes parallel computation. Again, because of this emphasis, and the fact that the book hasn’t been published yet, it is best approached as after-the-fact supplementary reading.
The treatment of string matching in this course is partly based on material from the book "Algorithms on Strings, Trees, and Sequences", by Dan Gusfield, published in 1997. This book has an emphasis on computational biology and is aimed at the graduate student and researcher level. While the material we covered in CS 240E can be found in many references, the advantage of the Gusfield book is its sustained and coherent treatment.