Discussion

Additional notes

The List, USet, and SSet interfaces described before are influenced by the Java Collections Framework. These are essentially simplified versions of the List, Set, Map, SortedSet, and SortedMap interfaces found in the Java Collections Framework. The accompanying source code includes wrapper classes for making USet and SSet implementations into Set, Map, SortedSet, and SortedMap implementations.

For a superb (and free) treatment of the mathematics discussed in this chapter, including asymptotic notation, logarithms, factorials, Stirling’s approximation, basic probability, and lots more, see the textbook by Leyman, Leighton, and MeyerE. Lehman, F. T. Leighton, and A. R. Meyer. Mathematics for Computer Science. 2011.. For a gentle calculus text that includes formal definitions of exponentials and logarithms, see the (freely available) classic text by ThompsonS. P. Thompson. Calculus Made Easy. MacMillan, Toronto, 1914. Project Gutenberg EBook 33283. URL: http://www.gutenberg. org/ebooks/33283 [cited 2012-06-14]..

For more information on basic probability, especially as it relates to computer science, see the textbook by RossS. M. Ross. Probability Models for Computer Science. Academic Press, Inc., Orlando, FL, USA, 2001.. Another good reference, which covers both asymptotic notation and probability, is the textbook by Graham, Knuth, and PatashnikR. L. Graham, D. E. Knuth, and O. Patashnik. Concrete Mathematics. Addison-Wesley, 2nd edition, 1994..