Weiss
"Data Structures and Algorithm Analysis in Java (2nd Edition)" , Addison-Wesley.
This will be used very extensively in the second 2/3 of the course. Many of the homeworks will be either taken from this, or will have a similar smell to the problems here. The approach to both the data structures and the graph algorithms taken in class is very close to that taken here. The book differs from the "... Problem Solving" text by the same author primarily in its organisation and in some of the details of the implementations of the data structures. Having ready access to this book is highly recommended.

Arnold, Gosling, Holmes
"The Java Programming Language, 4th edition", Addison-Wesley, 2006
This is a nice resource for more in-depth descriptions of how to use the features of the language.

Gosling, Joy, Steele, Bracha
"The Java Language Specification, 3rd edition", Addison-Wesley, 2005
This gives some really detailed information on why various aspects of the language were designed as they were, and could be fun for those who want to get their hands quite a bit dirtier.

Online resources at java.sun.com:
The Java Tutorial (various subtopics)
This is a great resource, and gives nice explanations of the old and new material in the first 1/3 of the course. It will also probably be of help for the Java-specific questions in the rest of the course. This is strongly recommended for those who are a bit nervous about the Java programming content of the course, or who would like a more detailed, example-driven account.