About the course
This is the homepage for
CS 241: Data Structures,
a course offered by
Fritz Ruehr at the
Computer Science Department of
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
- 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):
(Older news, from previous teachings, is preserved below)
- 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!).
- Hey! 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).
- 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
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:
- (Just for fun: here is the
final Zombie Game project
from the last time I taught 141.)
- The I/O examples are
- The "retro mash-up" version of the windows lab is
(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 is
the Java Tutorials “trail” on interfaces;
see also here.
- Study guides from the 2012 teaching of the class for the
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
(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:
- 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.
Labs and written homework (in reverse chron. order)
Some on-line references
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.