Notes from Mike Clancy presentation in the visualization seminar,
October 27, 1998
My goal: design a self-paced version of CS 61B
self-paced = no lectures; face-to-face consultation
with tutors for help and evaluation of work content = data structures + algorithms + fundamentals of software
engineering; course is taught in Javatime to implementation = probably a couple of years
Data structures and algorithms covered in CS 61B
patterns of use for commonly used data structures:
stacks, queues, priority queues, trees, sequences, dictionaries, sets
manipulation of linked structures and structures using arrayssorting algorithms
Goal for the data structures/algorithms part of CS 61B
Identify and implement data structures
and algorithms suitable for a given solution. Identification
Is one of the commonly used data structures, or a
variation, appropriate?
Suitability
Do the operations match those required for solution?
Are the resources (time, memory) needed for implementation
available?
Implementation
Apply relevant skills in manipulating array and linked
structures.
Typical tradeoffs
Array vs. linked representation?
access time rearrangement timememory utilization
Store vs. recompute?
How visualization might help
Implementation
Show how a given algorithm works.
Suitability
Display the resources used by a given algorithm or
data structure.
Indicate what aspect of the algorithm or data structure
contributes most to its resource requirements.
Unvisual features of program code or pseudocode
It's text.
It's static.
Program statements don't say what's really going on.
implicit information
the big picture
Ways visualization of program execution might help
display of implicit information
use of color to highlight interesting information or algorithm
features
display of multiple views or representations
use of animation to portray dynamic processes
A neat book
Software Visualization: Programming as a Multimedia
Experience, edited by John Stasko et al. (MIT Press, 1998)
Software Visualization describes (among other things)
things to display about a program and ways to display
them
content (explicit and implicit information)
transformation (incremental vs. discrete, current vs. historical)
properties of a visualization
animation
metaphors
scale
interaction
uses of color
encoding the state of data structures
highlighting activity
uniting multiple views
emphasizing patterns
making history visible
"Sorting out Sorting" (1978): a milestone in algorithm
visualization (we watched part of this video)
Features
metaphor (bars whose lengths represent associated data
values)
color (highlighting comparisons, displaying implicit information
about what's been sorted)
animation (displaying exchanges)
multiple views (graphs of resource use, position vs. value
display, comparison of multiple algorithms)
no actual code or pseudocode
display conventions vary somewhat among algorithms
Some cognitive results described in Software Visualization
Stasko (1993)
CS grad students learning an algorithm with an
animation were compared with those learning without animation.
The animation group learned a bit better and thought that the
animation helped.
Lawrence (1994)
Students in a data structures course were compared
learning an algorithm in (a) lecture alone, (b) lecture + passive
lab, and (c) lecture + active lab where they could supply their own
test data.
The lab groups did significantly better.
The active lab group did slightly better than the passive lab
group.
nothing where students created their own visualizations
Problems
Identifying interesting events in an algorithm may be
difficult.
Connecting them to the relevant program code may be difficult.
There may not be a good match between what's on the screen and
cognitive structures, e.g. plans.
Highlighting one kind of info may obscure other kinds.
I plan to
make my instructional objectives explicit;
collect and analyze student misconceptions about relevant
algorithms;
locate software that lets students prepare their own
visualizations;
develop scaffolded activities in which students prepare
visualizations that reveal relevant aspects of algorithms.
|