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 their
possible implementations. Through all of this, our programming vehicle will be the
modern, high-level programming language Python. 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 Fall 2020 teaching of the course!
As the semester progresses, new News items will be added to the top
of this section, after the line below, so that the most recent ones appear first.
You should thus get in the habit of coming to this page to check the top of
the News for announcements, etc.
I have kept the old news items from earlier teachings of the course
and the most recent one (Fall 2019) intact below, in a separate
section, just in case we need them.
(Note that previous versions of the course were taught in Java;
the Fall 2020 version is the first to be taught in Python.)
Check out the Python version of the
Window structure (and now
here as well).
(more to come over the weekend).
Here is the Fall 2020 syllabus
(note that I am not distributing this or many other documents on paper
this semester, due to issues with the Covid-19 pandemic).
And here’s a link the the
Labs section way down below—currently the
labs listed there are for the Java version of the course, but I will
leave them up and live for you to peruse until the new Python versions
are released during the course of the semester.
Hereafter starts the Old News part of the section …
- Finally, here is that humorous link about what debugging
programs feels like:
from reddit.com/r/programmerhumor.
- Study for the Final Exam using
these review notes.
- Study for the midterm exam using
these review notes.
- Want to practice your AVL tree intuitions? Check out these
“algorithm animation” pages featuring AVL trees:
you insert your own values into the tree and watch it change
as you go!
- Here is a visualization by David Galles at the University of San Francisco. ;
- and here is one from
VisuAlgo.net,
which has a lot of other free material, visualizations and otherwise.
(On this one, be sure to click the AVL Tree header at the top.)
- Get started on your midterm exam studying now with these
three sample quizzes from the archives.
Let’s agree that we will do these as a self-graded assignment
due on Mon 14 Oct for “grading” in class.
(Meaning: be prepared to share your answers, perhaps on the board, and
to understand how other people solved them.)
Check them over now and ask questions (if you have any) on Friday the 11th.
- We used this “illustrated code” for tree traversals in a
hot-linked diagram
to discuss using stacks versus queues for tree traversals (on Wed 9 Oct).
Regarding near-term scheduling:
the mid-term exam has been scheduled (by class vote)
for Fri 25 Oct:
remember that there is no class on Fri 18 Oct,
as it is the college-wide mid-semester break day;
a mid-term exam review outline will be posted soon—we will
spend Mon 21 and Wed 23 in lecture
reviewing for the upcoming exam.
- Play the Java Name Game here!
- More textbook reading, and this time with questions during class!
So, for Friday 13 September, let’s all read the first three sections
of Weiss, Chapter 3 (Lists, Stacks, and Queues) … looks like
that means pages 57-67 (shouldn't take you too long). See you on Friday!
- Time for some textbook! In addition to brushing up on your
Java in Weiss, Chapter 1 (to the extent you find necessary or useful,
depending on your individual situation, you should start reading
about Algorithm Analysis in Weiss, Chapter 2.
- Here is
the Java Tutorials “trail” on interfaces;
see also here.
- 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.
- … and although we won’t have time to cover it all in
class, you may also wish to consult this
Java concepts outline
(from my old Lightning Java class).
Note: those triangles on the left click to reveal a lot more!
- The
example window Applet
I wrote is now defunct, although we saw
a movie of it in class.
But you can still read this
tricked-out graphic summary
with various links, including instructions for how you might be able to
get the Applet to run on your system (sorry—no Chrome!).
- Here are some files for class discussion in lab re the
“Java refresher” assignment
(i.e., Lab 1: the Window Manager):
- … and check out these graphics with some program design advice:
part one
and
part two.
- Here is the colorful refresher material on Java references, classes, etc.:
A Quick Review of Java Classes and Objects.
- Here is the Fall 2019 syllabus
(you also should have gotten a paper copy in class on the first day).
Fritz will be available, at the following times and dates to provide
extra help and “demo” labs, in the Ford 202 CS lab:
Wed., May 8th, noon-2:00 (or 3:00) pm;
Tue., May 14th, noon-2:00 (or 3:00) pm.
(The timing specs mean: I'll be there between noon and 2:00 for sure, and
will stay as late as 3:00 if there is continuing need.)
- Study for the Final Exam using
these review notes
(… and remember the sample quizzes here).
- By the way, you can find some relevant data files for Lab 5 (the princesses)
in both the lab file (namely the data files
royals1.txt and
royals2.txt),
but also right here, namely
a picture of the second data-set tree and
the official list of succession (i.e., output)
for that second sample file.
(Note, by the way, that "Bippity Boppity Boo" don’t quite come out in
that order; that's intentional … .)
- OK, the following links have been moved up to the top here for easy access;
we have:
- Thanks and a “hat tip” to Conor for sending along
a link to this
YouTube video on hash tables and hashing!
- Here is some code for lecture that
provides
Iterator access to BSTs.
- Lab 5: Royal Succession Order
(aka the Royal Princesses of Femenye)
has now been posted in the Labs section below; it will be due
at the end of the semester (but feel free to demo it before then
if you finish it early).
- Study for the midterm exam using
these review notes
and
the sample quizzes here.
- We will use
this array implementation of queues
from our textbook author (
Mark Allen Weiss of Florida International University)
as a “driver” for lecture on Monday 18 March.
- Lab 4: Using Stacks to Match Brackets
(the “stack lab”)
has now been posted in the Labs section below, with a due date of
Monday 1 April.
- We will use
this quick stack implementation
as an example in lecture.
PS: check out the
original Eniac programmers I mentioned earlier in class;
see also the Eniac Programmers Project.
(Well, perhaps in an earlier semester, but still … .).
- If you don’t get
this joke
because you haven’t seen the movie, just ask your parents.
(But notice that I’m not the only one who jokes about it.)
- Lab 3 (the “DCLL lab”)
has now been posted in the Labs section below, with a due date of
Monday 11 March.
- According to popular vote, the
midterm exam
has been scheduled for Friday 22 March; a midterm
review sheet will be posted beforehand and we will spend
at least one day during lecture just doing a review.
- Lab 2 has now been posted in the
Labs section below, with a due date of
Monday 25 February.
- If you look below, you will see that the Lab 1 due date has been extended
to Friday, the 8th of February.
(Special thanks to Nick and friends for the idea.)
- Here are some little example classes for lecture
on primitive and reference variables.
- For starters,
here is the Spring 2019 syllabus
(you will also get a paper copy in class on the first day).
- Check out the following link if you are interested in
how Java’s hash functions are implemented.
- Our favoite software pundit (Joel Spolsky) made it to the top of the
news the other day with
this blog post about what not to do when working with older code.
- Some AVL Tree animation links:
- OK, I have added 3 illustrated code changes to the end of
the Example file from the note below.
I hope they are useful in studying for Monday’s midterm exam!
- OK, the fully-revised “second edition” of the Timing Lab
is now posted (but be sure to use
refresh in your browser!).
- Hey! Remember that lecture by Turing Award winner Barbara Liskov
(of CLU fame) that I mentioned a few weeks back? I forgot to link it
in at the time, but I re-started it in my browser and noticed that,
in addition to interfaces (or their pre-cursors) she also talks
about exceptions and (especially relevant this week) iterators!
So, check out her lecture
here on YouTube.
- How long does it take to access memory (RAM)? What if a cache is involved?
Are there limits to the speed of memory access? And what does O-notation
have to tell us about all this?
Now that you are trained in O-notation and well-versed in these issues, check out
this blog post by Emil Ernerfeldt, a programmer in Stockholm, Sweden, who writes
about
The Myth of RAM
(the first of four parts).
- There are a lot of AVL tree (and other data structures) animations out
there on the web, but this one
is fun and lively.
- I mentioned in class the
“Codeless Code”
web site with koans about programming.
- Professor Levenick points out a very nice web-based tool for
inspecting and debugging programs, developed by Philip Guo
after work by David Pritchard and Will Gwozdz. Try typing in
some code and running it with the
Java version of the tool here;
it’s available for another half dozen languages as well.
Finally, you could try out the “shared session”
feature after watching
this video.
-
But, check out specifically this
diagram showing how to insert into a DCLL.
- I seem to recall that I mentioned
this phenomenon
in lecture the other day … .
- 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.
- Here is a
page with sorting algorithm animations
(one of very many available on the web!).
- 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, two several 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.
- 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!)
- (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.
- Study guides from the 2012 teaching of the class for the
midterm
and
final exams
are still available.
- 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 (or Ash) for requesting it.)
- ... and you can find sample output for Lab 2
here for Fibonacci and
here for Collatz.
(Thanks to Kendra / Ash 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 (former student)
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
Current work archive
Third week of classes
Reading: Chapter 2 of the textbook, and bring questions about O-notation.
Coding: Be ready to ask questions about or demo your program for the
skiing paths. We will start looking into the next program (Clicking
on Windows) for next week.
Second week of classes
Reading: Chapter 1 of the textbook and bring questions about Python features.
And read specifically about classes, objects, and methods, toward the end
of Chapter 1.
Coding: You are too imagine that you are writing a program to take,
as input,
a series of points (pairs of x and y coordinates)
representing a “looped path” from the first point, along
line segments represented by each pair of points, and returning in the
end from the last to the first. Ultimately we may worry about a way
to read these values in, but for now we will just work on two functions,
each of which takes the same list of pairs (of numbers) as arguments.
The first function should compute the distance along the whole path
(including looping back to the first point); you should write and use
a distance “helper function” which takes two points and
returns the distance between them. The second function will test a more
subtle aspect of the same list of points: does the path hat they form
ever cross over itself, either in the sense of two segments intersecting,
or in the sense even of a single point at a “juncture” of
two segments at their ends touching (having an endpoint in common),
except of course in the case when two adjacent segments touch in order
to form the path. This function should at least return a boolean values
indicating whether or not the path is “good” (no unexpected
crossings). If possible, you might return instead a list of the problematic
crossing points, which would be empty if the path is good.
In lecture: we’ll talk about:
Reading: continue with Chapter 3 of the textbook, reading about
stacks, their implementation, and balancing parentheses.
In lecture: we’ll talk about the material from Chapter 3.
Lab:
We will try to finish up the Clicking on Windows lab—you
don’t need to come to lab unless you have work still to do on
the Windows lab.
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.
