This is the homepage for CS 241: Data Structures, a course offered by Fritz Ruehr at the Computer Science Department of Willamette University.

The study of data structures and algorithms serves as a basic foundation to a Computer Science education. As a second course in programming, it enriches a student's understanding of the basic processes involved in computing. But it also begins to focus attention on deeper and more abiding issues. In this course, we shift our attention from simple coding techniques to the analysis of algorithms in terms of resource use (time and space), generic solutions to recurring problems and larger-scale program design. A good portion of our time will be spent becoming familiar with the discipline's standard repertoire of data structures and algorithms. In order to support larger-scale design, we will stress principles of abstraction and modularity. We will try to divide our programs into cleanly separated components, with narrow interfaces, and consider the specification of their behavior separate from its possible implementations. Through all of this, our programming vehicle will be the modern, object-oriented programming language Java. Students should come out of this course with a solid capability for programming and design and a good foundation for future study of Computer Science in general.

News

• Don't believe everything you read on the internet about exams.


• Study for the final using these review notes.


• OK, here's yet another sorting algorithm.


• Check out the Wikipedia list of data structures.


• You can find the detailed case analysis of AVL tree rotations on Roger Whitney's site at San Diego State University.
  Wikipedia also has a nice illustration of tree rotations as well as a good summary of splay trees.


• OK, wrt visiualization of sorting algorithms, we have here the more fair side-by-side comparison I was hoping for in lecture
  and, over here, the static (non-animated) pictures I emailed about (which may nevertheless not give a good sense of
  overall running time differences, as discussed in the comments to the reddit post).


• Check out these animated data structures: here they are.


• Study for the midterm using these review notes (and watch for updates!).


• By the way, speaking of logarithms, exponents and numerals, here's what a trillion dollars looks like (a Public Service Announcement).


• The link for today's lecture on tree traversals is this hot-linked diagram (some code updated with syntax highlighting!).


• Those of you still working on Java exceptions will want to check out this handy list. ☺


• Special thanks to Blake Lavender for this link to a nice site with good information & tutorials on applets, double-buffering, etc.; check it out!


• Here is The Tragedy of Linked Lists.


• I found this nice little summary of interface usage tips on the web and thought I would post it here: check it out!

Labs and written homework (in rev. chron. order)

• Lab 6: Lab 6: Hashing frequencies (English words)
  Due: Monday 27 April
• Lab 5: Lab 5: Group Game Project: Scrolling Background
  Due: Friday 10 April
• Lab 4: Tree traversal as an iterator
  Due: Friday 20 March

  Write up the depth-first and breadth-first tree traversals from the on-line sample as
  formal implementations of the Iterator class; see this diagram explaining what to do.

• Lab 3: Linked lists and stacks
  Due: Friday 20 February
• "Lab" 2: Side-scrolling Game Project Design Document
  Due: Monday 9 February

  This is the group design document for our term-long gaming project; see the various group's documents here:

  • Ally, Jose and Chris' group: Project DIagram.gif;
  • Garrison, Andrew and Trevor's group: GameTree.pdf;
  • Justin, Wesley and Blake's group: digiHeist.pdf.

• Lab 1: Clicking on Windows (a Java refresher)
  Due: Wednesday 28 January

Some on-line references

• Here is the homepage for our textbook, Data Structures and Algorithms in Java (4th edition), by Michael T. Goodrich and Roberto Tamassia.
• Check out these on-line animated sorting algorithms.
• ... and here are some more algorithm animations.

Handouts, examples for lecture, etc.

• (nothing here yet, either)

Miscellaneous links

Here are a few fun, interesting or otherwise difficult to categorize links that came up in lecture at various points.

• Here's a nice little demonstration of the power of exponentiation (in base 10): The Powers of Ten.