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