Textbook and Readings

Textbook: Mark Allen Weiss. Data Structures and Problem Solving Using Java. Addison-Wesley, 4th edition, 2010. The university bookstore carries this book, which is a “required textbook” for this course. You may be able to get by with the 3rd edition (at your risk), but do not use an even earlier one.

The core topics for this course are found mainly in Chapters 18 and beyond; a few earlier chapters, such as 5, 8, and 14 are also relevant. Detailed coverage information will be announced as we progress in the semester. Most chapters in roughly the first third of the textbook, as well as some later chapters, discuss topics that are covered in the prerequisite course, COS 225. We will not be covering these topics in this course but they are important for successful completion of homeworks and tests (so it is advisable to brush up on them).

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.

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.

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.

3.

Gilad Bracha. Generics in the Java programming language. Tutorial. http://java.sun.com/, July 2004.

This tutorial is optional reading but I strongly suggest that everyone read it. The concepts explained here are essential for making good use of generics in Java and it is very painful to learn them the hard way (e.g., while debugging your code).

4.

Sudarshan S. Chawathe. Segment-based map matching. In Proceedings of the IEEE Intelligent Vehicles Symposium (IV), pages 1190–1197, Istanbul, Turkey, June 2007.

The main purpose of this paper, for this course, is providing a concrete example how data structures and related concepts find use in current research and applications. Sections I, II, and III are required reading. The rest of the paper is optional reading.

5.

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

6.

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

7.

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

8.

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

9.

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.

© 2010 Sudarshan S. Chawathe