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.

*Welcome to the Spring 2016 teaching of the course!*- Word on the street is that there is a quiz coming
*Real Soon Now*. I expect it will have questions about logarithms, “Big-O” notation, and a little bit of algorithm analysis (i.e., how do you figure out how much running time some piece of code will take). Possibly also something about Java class design, getters & setters, that kind of thing. Just a word to the wise. - That little graphic about why (and how) to avoid getters & setters
is is right here in the
`/figs`

directory. - Lab 2 is now assigned; see the Labs section below.
- We will use this “Java entities diagram” and this outline (in progress) of Java ontology in lecture to reaffirm understanding of Java and object-oriented programming.
- OK, here are some files for class discussion in lab re the
“Java refresher” assignment
(i.e., Lab 1: the Window Manager):
- The first page and second page of a sample program design;
- Some sample data (you can use this in your program demos, but you also should develop a set of your own windows);
- Some sample output of a program run via Dr. Java.

- Study for the
**final exam**using these review notes! - Here is a
page with sorting algorithm animations
(one of
*very*many available on the web!). You can find correct solutions to the Lab 4 princess data here (as text data output) and here (as a PDF of a graphic of the tree).*Hey!*- Curious about new ways to program? Check out
this video on Vimeo
by Bret Victor (of Apple, among other places) and his ideas
on how immediacy of access to runtime behavior affects coding.

*(This demo is, by the way, 2 years old ... .)* - You can find a nice, relatively browser-compatible interactive AVL tree
animation
at this link from
**qmatica**(possibly useful in studying for the Final Exam). - Here is a very sketchy overview of how pointers in an AVL tree might be re-assigned so as to effect a double-rotation “all at once”; this is definitely not optimized, and the diagrams could be more helpfully annotated, but it should provide some clues as to how to solve that last exam problem (many other orderinsg are possible as well). Details are in this PDF file.
- The link to the “illustrated code” for tree traversals is in this hot-linked diagram.
**Looking for sample code from lecture?**

You should now be able to find it in in this folder (`.java`

files only, though).

*(Warning! This is code straight from lecture: little documentation, not nec. ideal code, either!)*- Check out these graphics with some program design advice: part one and part two.
*(Just for fun: here is the final Zombie Game project from the last time I taught 141.)*- The I/O examples are here.
- The "retro mash-up" version of the windows lab is
here.

(Click repeatedly on the arrow in the lower left.) - Here are the sample console and option pane programs.
- Here is Joel Spolsky and Schlemiel the painter on Java, C and what you need to know to succeed ...

(and more from Spolsky here, plus discussion from readers, and some other thoughts) - Remember to check the
CS tutoring page.
for information about regular tutoring hours
*as well as*individual, one-on-one tutoring via the Learning Center (all free of charge!) - You can find a short example of using Scanners to open and read a file here.
- Here is
the
*Java Tutorials*“trail” on interfaces; see also here. - Study guides from the 2012 teaching of the class for the midterm and final exams are still available.
- Here is a the key to sorting algorithms (for exam study).
- Here is a quick overview of sorting (more to be added later) … and here is page with sorting algorithm animations.
- See the AVL tree (etc.) animations here.
- Here’s a couple of more direct links to the
new windows applet
and the
form applet
*(now with code embedded … at least for the second one!)*. - You can find the Applet examples in this directory.
- Relevant memes?
- This directory contains (a variation on) the sample code from lecture
on Tuesday 7 Feb
regarding call stacks and exceptions.

(Thanks to Kendra for requesting it.) - ... and you can find sample output for Lab 2
here for Fibonacci and
here for Collatz.

(Thanks to Kendra again!) - Stephanie Jones, graduating senior in CS and Math sends along this video gem on a Fibonacci analysis of Spongebob's pineapple (!).
- Maybe we should use this old lab
as a foil for learning about interfaces and
*anonymous inner classes*?

(See also**Section 1.6**of the Weiss textbook.) **Know your tools!**What's new in Java 7? Check out these links:- Oracle’s Java 7 docs page
- Wikipedia’s Java version history page
- As far as I know, we don’t have Java 7 installed in our labs; you are welcome to install it on your own machine, however.

- The Wikipedia entry on the Collatz Conjecture (not available on Wednesday 18 January 2012).
- 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 visualization 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.
- By the way, speaking of logarithms, exponents and numerals, here's what
a trillion dollars looks like
*(a Public Service Announcement)*. - The link for the 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.

- Lab 2: Timing Strings and Collections

Due: Friday 12 February - Lab 1: Clicking on Windows (a Java refresher)

Due: Monday 1 February

- Here is the source code page for our textbook, Data Structures and Algorithm Analysis in Java (3rd edition), by Mark Allen Weiss.
- Check out these on-line animated sorting algorithms.
- ... and here are some more algorithm animations.

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.