A light-weighted visualization tool
for facilitating students’ learning of
sorting algorithms
Sen Zhang, Hanfu Mi
State University of New York
College at Oneonta
What does a course teach?
Simple facts, concepts, definitions,
notations, etc.
Observations & properties
Principles & theories
Complicated concepts & procedures
Case studies
…
Merlot 2006
SUNY, College at Oneonta
Concepts in Computer Sciences tend
to be abstract for various reasons.
Highly generalized
Dynamic nature
Procedure oriented
Transformed representation
Formally defined, in mathematical and/or logical
languages
Usually not in plain natural languages
Complicated
Different platforms and magnitudes
Invisible
Merlot 2006
SUNY, College at Oneonta
How to teach procedures and
complicated concepts?
Verbal
Visual
One picture is worth one thousand words!
Chalk & Board
PowerPoint
Customized tools
Merlot 2006
SUNY, College at Oneonta
One picture is worth one thousand words!
Sometimes, interpreting the essential
concepts in natural languages could be
inadequate, especially if you teach first time
students.
Verbal is sequential, while a non-trivial
concept is usually parallel, complex, and multifaceted.
One possible solution is to use visualization to
complement the weakness of the sole
language interpretation.
Merlot 2006
SUNY, College at Oneonta
A scenario where visualization is
particularly useful.
In a Data Structures course taught in Oneonta,
we explored, adopted and developed the
visualization tools to facilitate students’
learning of some topics which could otherwise
be challenging to grasp.
Merlot 2006
SUNY, College at Oneonta
Static vs. Dynamic
Due to the media restriction, visualization
were traditionally conveyed by static
graphics.
instructors’ drawings on the blackboard or a
transparency
figure illustrations in traditional textbooks
Computer software makes dynamic
visualization possible.
Different approaches.
Java Applets
MatLab
PowerPoint Animation
Excel through VBA
Merlot 2006
SUNY, College at Oneonta
Advantages of using
visualization tools in teaching
Make effective use of classroom time
Help student engaged in class
Respond to different inputs quickly without
delay
Extend active learning to outside of
classroom
Merlot 2006
SUNY, College at Oneonta
A light-weighted visualization tool
for facilitating students’ learning
of sorting algorithms
A tool for sorting algorithms
Light-weighted
More interesting work! If we have time.
Merlot 2006
SUNY, College at Oneonta
Basic definition of sorting
algorithms
A sorting algorithm is an algorithm that puts
elements of a list in a certain order. The
most used orders are numerical order and
lexicographical order.
Efficient sorting is important to optimizing
the use of other algorithms (such as search
and merge algorithms) that require sorted
lists to work correctly.
Merlot 2006
SUNY, College at Oneonta
Comparison based sorting
algorithms
Bubble sort
Insert sort
Selection sort
Mergesort (or Merge sort)
Quicksort (or quick sort)
Merlot 2006
SUNY, College at Oneonta
Bubble sort
The basic idea is to compare two
neighboring objects, and to swap them if
they are in the wrong order.
This is probably the simplest way to sort an
array of objects.
Unfortunately, it is also the slowest way!
Merlot 2006
SUNY, College at Oneonta
Selection sort
The idea of selection sort is rather simple.
We repeatedly find the next largest (or smallest)
element in the array and move it to its final position
in the sorted array. Assume that we wish to sort the
array in increasing order, i.e. the smallest element
at the beginning of the array and the largest
element at the end.
We begin by selecting the largest element and
moving it to the highest index position. We can do
this by swapping the element at the highest index
and the largest element. We then reduce the
effective size of the array by one element and
repeat the process on the smaller (sub)array. The
process stops when the effective size of the array
becomes 1 (an array of 1 element is already
sorted).
Merlot 2006
SUNY, College at Oneonta
Insertion sort
Insertion sort keeps making the left side of
the array sorted until the whole array is
sorted. It sorts the values seen so far and
repeatedly inserts unseen values in the
array into the left sorted array.
The insertion sort algorithm is the sort
unknowingly used by most card players
Merlot 2006
SUNY, College at Oneonta
Mergesort
Mergesort is a recursive sorting procedure
that uses O(n log n) comparisons in the
worst case.
To merge sort an array of n elements, we
perform the following three steps in
sequence:
If n<2 then the array is already sorted. Stop
now.
Otherwise, n>1, and we perform the
following three steps in sequence:
Sort the left half of the array.
Sort the right half of the array.
Merge the now-sorted left and right halves.
Merlot 2006
SUNY, College at Oneonta
Quicksort
Pick an element from the array (the pivot),
partition the remaining elements into those
greater than and less than this pivot, and
recursively sort the partitions.
Ideally, partitioning would use the median of
the given values, but the median can only
be found by scanning the whole array and
this would slow the algorithm down. In that
case the two partitions would be of equal
size; In the simplest versions of quick sort
an arbitrary element, typically the first
element is used as an estimate (guess) of
the median.
Merlot 2006
SUNY, College at Oneonta
The tool is light-weighted.
It does not need extra hardware such as DVD
players for movies.
It does not need compilers such as C++ and Java
It does not need an expressive running
environment such as Matlab
It does not assume too much specialized
knowledge in Computer Science
All it needs is MS Office Suite, which is almost
available in every campus PC, and the VBA script
language support coming together with
MSOFFICE.
Merlot 2006
SUNY, College at Oneonta
Script languages
Scripting languages (commonly called
scripting programming languages or script
languages) are computer programming
languages created to shorten the traditional
edit-compile-link-run process.
The name comes from a written script such
as a screenplay, where dialog is repeated
verbatim for every performance.
A script is usually interpreted rather than
compiled.
Merlot 2006
SUNY, College at Oneonta
Script languages
Script languages can be found at almost every
level of a computer system. Besides being found at
the level of the operating system, they appear in
computer games, web applications, word
processing documents, network software and
more. In many ways, the terms high-level
programming language and scripting language
have become entwined, and there is no clear
delineation between the two.
VBA script is quite sophisticated and has been
used to write elaborate programs, which are often
still called scripts even though they go well beyond
automating simple computer tasks.
Merlot 2006
SUNY, College at Oneonta
PowerPoint Presentation
PowerPoint
Presentation time
Design time
How to design a PowerPoint presentation
Who do the job?
How much time one can expect to finish a quick sort
algorithm animation in PowerPoint?
Can we do better?
Let us elaborate the ideas by using an some
work we have done.
Merlot 2006
SUNY, College at Oneonta
How to design PowerPoint
Animations?
Man power
Software, e.g. a script
Again, you need to write a program
Write once, reuse many times.
Merlot 2006
SUNY, College at Oneonta
Future works
Students’ perception about the concept
Assessment of students’ perception
Active visualization
Visualization tools implementation
Merlot 2006
SUNY, College at Oneonta
Questions?
Merlot 2006
SUNY, College at Oneonta
Thank you very much!
Merlot 2006
SUNY, College at Oneonta
Descargar

A light-weighted visualization tool for facilitating