Notes on CSE 332, Data Abstractions, as a pre- or co-requisite to CSE 312, Foundations II.
Approximately the last third of 312 covers algorithmic material, for
which the Data Abstractions course provides important background.
Quoting from the Curriculum Committee
planning documents
prepared when these courses were adopted:
The main items needed from the Programming Abstractions course
for Foundations II would be graphs and asymptotic runtime analysis
which would be necessary for the complexity part of the
course. Since that is in the last third of the course and those
topics would be relatively early in the Programming Abstractions
course a co-req would be okay.
For the few students in 312 who are not concurrently enrolled in CSE 332
(or took it elsewhere, long ago, or otherwise feeling a bit shaky),
some independent study of this material will be important. I
recommend:
- Get a copy of the CSE 332 text, currently
Mark Allen Weiss, Data Structures and Algorithm Analysis in
Java, Second Edition, Addison Wesley, 2007.
Errata.
CSE 332 covers roughly Chapters 2 and 4-9 of this book.
- Far and away the most important parts are chapters 2 and 9 - read these carefully.
- Chapters 3-8 (the more data structures oriented part) contain
many implementation details. The details are not so relevant
for 312, but getting a broad picture of when these structures
are useful and what they buy (e.g. lookup in a list in log n
time vs n time) is important background. Reading the intro
sections of chapters 3-8 may suffice for this. I suspect the
Wikipedia articles on the topic in each chapter title will
provide a second, hopefully concise, overview. I recommend this
as well, and welcome feedback as to whether this is useful
and/or pointers to better resources. Sections 6.4 (Applications
of Priority Queues) and 7.7 (Quicksort) are also recommended.
- The book seems to spend some time on Java language features
and libraries. These are not at all relevant to 312, but may be
necessary to the extent that you need to be able read examples
in the book.
- Chapter 10 might also be good, although I will cover some of this myself (in a different way).
|
 |
Computer Science & Engineering
University of Washington
Box 352350
Seattle, WA 98195-2350
(206) 543-1695 voice, (206) 543-2969 FAX
|
CSE Home