Use of Visualization in Teaching Introductory Computer Science

Viera K. Proulx, Richard Rasala, Harriet J. Fell
College of Computer Science
Northeastern University Boston, MA 02115, USA
vkp@ccs.neu.edu
http://www.ccs.neu.edu/home/vkp

---

Talk presented at the Dagstuhl Seminar

New Media in Computer Science Teaching at University Level

Schloss Dagstuhl, Germany, February 3, 1998

---

Outline

Programming with graphics
Algorithm tutorials and exploration
Analysis
Dissemination

Visual feedback
Building mini applications and games
Modeling real world computer science


Visual feedback

scaled picture drawings pumpkin
house
own design
animated loops
rolling balls tilings
algorithm debugging
swimming fish
array sorting
function plotting
animating data structure behavior
binary trees
heaps
graphs
cars on a road

Building mini applications and games

piano keyboard
event loop
learn to use sound too
minipaint
simple design
user interface issues exposed
design and maintenance of menus/toolbars
memory game
two player situation
taking turns, keeping tabs

Modeling real world computer science

cryptography (Ceasar's shift) display and view histogram
learn simple encryption code Mars images

real data

motivation, excitment

sense of empowerment

lot of data

over 90 000 bytes

need for files and storage media

problems with transmission/bandwidth

mixed text, numeric, and pixel data

byte data can have multiple meanings

issues of portable text (CR/LF problems

representation of integers in different machines

unsigned bytes - conversion isuues

image enhancement

linear scaling

histogram equalization

additional topics

covert channel

discovering data tampering

sonification

morphing

simple technique

can be cone with line drawings, pixel data, using spreadsheet, etc.

nice uses:

caricature (credit Erich Neuwirth)

animation

special effects

recursive fractal grammars (L-systems)

impressive use of recursion

example of the need for extensive computational power

seeing order of growth in 'real life'

design issues for display (scaling)

need for recomputation, good design

power of algorithm

generate complex drawings from only a few lines of grammar definition

traffic simulation

display adds interesting design issues

encapsulation

independence of display and the main problem

visual representation of the behavior

Monte Carlo search for a hidden object

application to archaeology

application to oil exploration

contour maps

basis of the satelite image processing

weather maps

modeling
game of Life

ability to observe complex behavior over a long time span

ability to observe patterns not seen in hand generated display

Algorithm tutorials and exploration

sorting

animation to learn, explore, compare

student built animation for debugging

timing data for formal analysis

binary trees

animation to learn and explore

student built animation for debugging

analysis of random tree heights - interesting results

heap and heapsort

animation with dual representation
students built animation for debugging

graph algorithms

animation for exploration and understanding

display independent of data structure representation

lessons in encapsulation

students built animation for debugging

enumeration and analysis

time trials for sorting

physical time factor

wait for a long time

see other algorithms blitz through

visual representation of data

visual difference between n*n and n*log(n)

compare all in one 3D chart

opportunity to ask questions

what is the best size to switch from quicksort to insertion?

which one is best for nearly sorted data?

which one has least number of moves?

height of binary trees

discovery of stabillity

height average near 2*min height

deviations are minor

no real bad cases

implications for the study of tree balancing

in real life not needed

too complex to embed in a critical system

twice a year re-balancing

union/find algorithm:

the gain from small improvements

chain splitting: change parent pointer for a visited node only

drastic change for one line of code

better understanding

by setting up the counters the structure of data becomes more clear

new discovery

trying to avoid a mess

for each union point from numerically lower representative to the higher

astonishing result (new - as far as I know)

ad-hoc analysiss explains reason why it works so good

order of growth explorations

big Oh

bound form below

bound from above

bound by one function from both above and below

the meaning of the constant c

little oh

the meaning of:

for each c > 1 there is an n0 such that for all n > n0 ...

modify c - observe changes in n0

represent n0 as a crossover point

observe the constancy of the shape of curves

Dissemination

curriculum vs. individual projects

whole curriculum dictates author's preferences
whole curriculum discourages local experimentation
individual projects - hard to adapt if not designed for it
individual projects - hard to know if prerequisites, goals are OK

cross platform availability

needed for wide acceptance
hard to achieve
hard to maintain
Java may help...

adaptability

whole project may be too big
user may want to change parts
user may want to change source code

support

users will have questions
author cannot do tech support or curriculum help

solution

extensive documentation and navigation at the top level

lists:

complete list

list by outcomes

list by difficulty

list by time needed

list by CS applications presented

explanations

overall philosophy

formats for the components

meaning of the fields

design of the navigation

careful packaging of each lab:

teacher's cover sheet:

prerequisites

goals - with levels of learning

expected outcomes at two levels

methodology

brief synopsis for search

keywords for prerequisites, content, goals

listed for each project

several axis for search:

algorithm, data structure, design, application, basic construct

project description in several formats

for browsing/reading online

for downloading as is

for downloadign for potential modifications

download all componenets at once

source code for instructor, student

format for on-line browsing

format for downloading

makefile or project build description

all needed files and toolkits

platform specific - several versions needed

written documentation of the overall design