Textbook and Readings

Textbook: Mark Allen Weiss. Data Structures and Problem Solving in C++. Pearson, 2nd edition, 1999. This book is a required textbook for this course. Detailed coverage information will be announced as we progress in the semester.

Assigned Readings: Material will be added here as we progress through the semester.

Other Readings: All the following are recommended, but not all are required. Further details and additional readings will be announced in class and may appear here as well. Some may move to the assigned category as we progress.

1.

Arne Andersson. Balanced search trees made simple. In Proceedings of the Workshop on Algorithms and Data Structures, pages 60–71, Montreal, Canada, August 1993.

This paper introduces AA-trees and includes very nice examples and figures.

2.

Samuel W. Reynolds. A generalized polyphase merge algorithm. Communications of the ACM, 4(8):347–349, 1961.

This paper provides a succinct and readable description of polyphase merging. It is a very useful supplement to the description in the textbook, which is missing many important details.

3.

Sanjeev Saxena. Dominance made simple. Information Processing Letters, 109(9):419–421, April 2009.

This short paper is a good example of how some of the basic concepts studied in this course may be used as building blocks to solve more complex problems.

4.

Derrick Coetzee. An efficient implementation of Blum, Floyd, Pratt, Rivest, and Tarjan’s worst-case linear selection algorithm. http://moonflare.com/, January 2004.

5.

Jon Bentley and Don Knuth. Programming pearls: Literate programming. Communications of the ACM, 29(5):364–369, May 1986.

6.

Paul E. Black. Dictionary of algorithms and data structures. http://www.nist.gov/dads/, September 1998.

7.

Lloyd Allison. Suffix trees. http://www.allisons.org/ll/AlgDS/Tree/Suffix/, 2008.

© 2020 Sudarshan S. Chawathe
Validated HTML 4.01 Transitional. Check.