Data Structures
About the course
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
- Welcome to the Spring 2012 teaching of the course!.
- Here is a the key to sorting algorithms (for exam study).
- FINAL EXAM on Friday May 4 from 2-5pm!!. Study for it using these review notes!
- Here are data files with royal princesses for Lab 6:
royals1.txt (from the write-up)
and
royals2.txt.
- Here is a quick overview of sorting (more to be added later)
…
and here is page with sorting algorithm animations.
- Lab 6 is posted
…
now with extra-special visual aids! (See the bottom of the lab page.)
- See the AVL tree (etc.) animations here.
- Lab 5 is now posted!
- MIDTERM EXAM on Tue 20 March; study for it using this guide!
- 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?
- I have updated the due date for Lab 3 below to reflect a slight easing of
the schedule.
- 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!)
- 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 (!).
- Check out this
Java entities diagram and
this outline (in progress) of Java ontology.
- Sample test data for Lab 1 is
here (
sample1.txt) and
here (sample2.txt);
visualizations of the window sets are
here (sample1.png) and
here (sample2.png).
(Note that the visualizations include sample user inputs and intended results,
in a short, summary form.)
(PS: I fixed the bad data here, added a quick note to explain the figure,
and took the duck out of the blender on the
interfaces example page.)
- You can find a short example of using Scanners to open and read a file
here.
- 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.)
- Here are some notes on interfaces: read them!
- Know your tools! What's new in Java 7? Check out these links:
- The Wikipedia entry on
the Collatz Conjecture (not available on Wednesday 18 January 2012).
(Older news below)
- 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.
- 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 chron. order)
Some on-line references
Handouts, examples for lecture, etc.
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.
