What is this Resource?

This document was prepared by Sumant Murugesh, Tim Bell and Vanja Venrooy at the University of Canterbury. It is not an official document, but is offered as an evolving guide to the resources that are available for teaching the new material in NCEA Digital Technologies (currently focussed on the Programming and Computer Science strand). The structure has been based on various versions of the Body of Knowledge, proposed Standards, and Teaching and Learning guide; the material comes from an extensive search for relevant resources. It is our hope that this resource will evolve based on feedback from teachers, and ultimately end up as teaching plans that are built on the resources. Feedback can be sent to tim.bell [at] canterbury.ac.nz.

Achievement Standard
The resources on this page relate mostly to the Digital Technologies Achievement Standard 1.44/AS91074 (Demonstrate understanding of basic concepts from computer science)

Objectives
Demonstrate an understanding of the distinguishing concepts of algorithms and programming languages from Computer Science and Software Engineering

• Understand what an algorithm is and how it is different from a program
• Comparing and contrasting algorithms, programs, and informal instructions
• Describing an algorithm for a task, showing understanding of the way steps can be combined in sequential, conditional, and iterative structures (control flow)
• Determine the cost of an iterative algorithm on a problem of size n
• Download programs that implement different algorithms for the same problem, and compare how fast they are. For example, if students are using the Scratch language, there is a zip file of programs available that include several different implementations of searching and sorting algorithms.

Context
The key thing at this level is to be able to compare different algorithms for the same task, such as linear and binary search, and consider how they differ as the amount of data being searched increases. This can be done in a variety of ways without even implementing the algorithms; it could be a simple analysis of the time taken to do an algorithm by hand (such as searching phone books of various sizes), or timing an on-screen animation where the algorithms “race” each other, or an offline activity such as the CSUnplugged “Battleships” game, where the algorithm becomes a strategy for winning a competition.

Ideas for Teaching and Learning Activities

• Estimate how long it takes to look up a name in the local telephone book using a conventional (binary search) method compared with looking through every page starting at page 1 (linear search). Now consider how the two methods compare if the phone book was 10 times larger, or even a thousand times larger. (Linear search might take days or weeks, whereas binary search doesn't take much longer even for a book with millions of pages.)
• Give students a pile of 50 cards with numbers on them, and have a competition to see who can sort them the fastest. What are the best strategies?
• Find the sum of the first n whole numbers (1 + 2 + ... + n), either by hand or using a computer program. Contrast the amount of effort needed (e.g. in terms of arithmetic operations) using the obvious method of n-1 additions, with using a formula for the sum (n*(n+1)/2).
• Explore the purpose (not the details) of a wide variety of appropriate algorithms, such as search algorithm for sorted lists, sorting algorithms, graph algorithms for finding paths and checking connectedness, maze algorithms, long multiplication (normal and “russian peasant”), and greatest common divisor.
• Given two lists of the number plates of every car that went down two streets, discuss algorithms to produce a single list of all cars that travelled down both roads. (There are several ways to do this, one of the fastest is to sort the two lists before comparing them; a slow one is to search one list for each item in the other list).

Our Picks
Here is a shortlist of resources we have picked from the comprehensive list below that were either developed for high school use or can be easily adapted for the purpose.

• Virginia Tech CS department has a complete module on algorithms 

• Joe Carthy has good plain English notes on Comparing Algorithms

• Mark Baker has a comprehensive website for Discussion of Sorting Algorithms

• Shannon Duvall has The Adventures of Theta Man that help teach Algorithm Analysis using a fairy tale story

• Earl Paine and Stu Schwartz has a presentation explaining Binary Searching and its efficiency

• Susan Rodger has an exercise in developing algorithms.

• Barbara Ryder has some activities for searching and sorting.

• The Seven Bridges puzzle – to demonstrate the concept of graph algorithms

• Mathsite has a guided brick sort activity to teach sort algorithms

• Dave Feinberg's How Fast Is My Algorithm? (note: uses Array data structure)

• Universite Nice has an Interactive Simulation of Bubble Sort, where the user gets to try out the sort and recieve feedback for mistakes

• Jason Wentworth of the University of Wisconsin - Oshkosh, a student of Thomas L. Naps has Sorting Out Sorting - The Sequel, an interactive way to demonstrate some common sort algorithms

• University of Washington's BENEFIT (Fluency with Information Technology) course has a great animation of Bubble Sorting of CDs in a library

• Sorting Algorithm Animation System (SAAS) features a very clear comparison of sort algorithms using animation.

• CS Unplugged Sorting Algorithms Activity- examines selection, sort, insertion, bubble and merge sorts.

• CS Unplugged Sorting Algorithms Activity video at Sorting Algorithms on YouTube

• Computing Science Inside Workshop (Requires Registration) – Algorithm Development

• Frank Baker has a card sorting activity

• Traffic Jam is a problem solving activity that requires you to develop an algorithm

• CS4FN's Swap Puzzle online game to introduce algorithm development

• Mr Barton Maths has a great resource called Sorting Algorithms that teaches most sort algorithms hands on

• University of Washington's BENEFIT (Fluency with Information Technology) course (Requires Registration) module in Lesson 4: All About Algorithms

• saylor Computer Science course: CS303: Algorithms offers a great unit plan with useful readings

 

Unit Plan
A Unit Plan for teaching that uses some of the above resources that relates to this standard is attached as a PDF at the bottom of this resource page.

Comprehensive list of resources that relate to this standard

The resources below are a mixture that were developed for a varied audience ranging from high school students to university undergraduates, therefore we have attempted to classify the resources in terms of their readiness to be used by teachers. There are those that aim to convey a Basic understanding of the concepts and those that are Advanced and therefore might assist teachers with their professional development activities.

---

Online Guides: Basic Resources
These set of resources aim at conveying a basic understanding of the concepts with tutorials, lecture notes and handouts.

• Wikipedia entries: Algorithm, Turing Machine, Nondeterministic Algorithm, Sorting Algorithms, Search Algorithms, Bin Packing Algorithms, Fair Division and Cake or Cookie Cutting Algorithm

• Wikipedia Popular Algorithm entries: Bubble Sort, Merge Sort, Quicksort, Selection Sort, Insertion Sort

• Algorithmist, a wiki on anything algorithms

• University of Washington's BENEFIT (Fluency with Information Technology) course is a free course for instructors covering a whole module in Lesson 4: All About Algorithms. This module covers the basics of algorithms, better algorithms and search algorithms with lots of activities included.
  Note: You need to register as an instructor to access the course materials.

• BBC h2g2 site has a great explanation on Algorithms:
  
  1. Basic Sorting Algorithms
  2. Packing Algorithms
  3. Tree Searching Algorithms

• Mark Baker has a website Discussion of Sorting Algorithms, where he discusses the algorithms and their performance. This resource was developed with UK 'A' Level and above, grades 11-12 and teachers in mind. Related materials are below:
  
  1. Sorting for Teachers (Program): demonstrates four popular sorting algorithms and allows a detailed inspection of how they work.
  2. Sorting Algorithms Student workbook 

• The Student Room UK has a Wiki revision sections on the following topics:
  
  1. Algorithms: that clearly explains the Order of Algorithms
  2. Sorting Algorithms: discusses bubble and shuttle sorts and their efficiency
  3. Packing Algorithms: discusses first fit and first fit decreasing algorithms

• aihorizon has short introductions to the following algorithms (with examples written in C++):
  
  1. Efficiency and the Space-Time Continuum
  2. Sorting Algorithms: Introduction
  3. Bubble Sort
  4. Selection Sort
  5. Radix Sort
  6. Insertion Sort
  7. Heap Sort
  8. Binary Search Algorithm

• eHow has a good article explaining How to do a Bubble Sort

• Shannon Duvall has The Adventures of Theta Man that help teach Algorithm Analysis using a fairy tale story

• Teach-ICT  has a mini website on sorting, searching and merging algorithms. Note: some parts of this site may be too advanced for this level, say the concept of an array data structure is covered in level 2

• Virginia Tech CS department offers a complete module on algorithms

• Exmouth College (via Uniservity) has the following teaching resources including worksheets and links to other resources on the same server:
  
  1. Comparing Algorithms
  2. Searching and Sorting

• saylor Computer Science course: CS303: Algorithms offers a great unit plan with useful readings

• Herong Yang has a tutorial book on Sorting Algorithms at Herong's Tutorial Notes on Sorting

• Rod Stephens has an article Sorting it Out based on his book Visual Basic Algorithms.

• Andrew Hunt and David Thomas has a very informative article How to Be a Better Coder where they discuss estimating the resources that algorithms use—time, processor, memory, and so on.

• ComputingStudents has sections with brief explanation of the following topics at locations below:
  
  1. Algorithm Analysis and Pseudocode
  2. Big-O Notation
  3. Binary Search
  4. Selection Sort
  5. Insertion Sort
  6. Bubble Sort
  7. Quick Sort
  8. Merge Sort

• Nishant Gupta has lessons on Curriki in sorting algorithms and how to differentiate them on the basis of time complexity, running time, space consumption, etc. Students can easily remember and memorize these things using the notes file attached inside this lesson. View here.
  
  1. Lesson 1 - Introduction to Algorithms
  2. Lesson 2 - Divide and Conquer Method
  3. Lesson 3 - Greedy Method
  4. Lesson 4 - Dynamic Programming
  5. Lesson 5 - Different Types of Sorting

• Laurent Haan has a good clear tutorial in Introduction to Algorithm Complexity

• aliali (tes UK) (requires free registration) has a resources to demonstrate bubble, quick and shuttle sort algorithms

• SRWhitehouse (tes UK) (requires free registration) has the following resources in algorithms:
  
  1. To demonstrate bubble, quick, shell and shuttle sort algorithms
  2. Tracing an algorithm, bin-packing, pseudo-code, order and efficiency of algorithms
  3. Worksheet on tracing algorithms (pseudo-code)

• Joe Carthy offers a very clear explanation of Complexity Theory in his course handout in Comparing Algorithms: Complexity Theory

• Earl Paine and Stu Schwartz has a resource in the form of a presentation called Binary Searching at the CSTA K-12 Repository introducing sequential and binary searching. Includes walk-throughs of a short sample list, using both algorithms, as well as a discussion of effiency. (language-independent)

• Top Coder offers some good tutorials and resources in Algorithms by various authors. We have selected some good reading below:
  
  1. The Importance of Algorithms
  2. Sorting
  3. Binary Search
  4. Computational Complexity 1
  5. Computational Complexity 2

• Dave Feinberg's course Introduction to Programming using Java has How Fast Is My Algorithm? which is good for understanding algorithms and their complexity. Note: This material uses the Array data structure hence some prior explanation may be required

• Maria Litvin and Gary Litvin have a textbook Java Methods for free chapter by chapter download. See the following chapters that would be of particular interest at this level (especially if done in conjunction with Java programming)
  
  1. Chapter 4.  Algorithms
  2. Chapter 19.  Big-O Analysis of Algorithms

• 2 July Maths UK website for Mathematics has Notes on algorithm development that discusses sorts, searches and others

• Hemsworth Arts and Community College Maths Faculty has resources on sort algorithms where students should appreciate the relative advantages of the different algorithms in terms of the number of iterations required:
  
  1. Shell Sort
  2. Sorting Test
  3. Sorting Practice
  4. Sorting Notes

• Cambridge University Press offers a free excerpt from Stan Dolan on Algorithms that covers the following: know what an algorithm is, be able to apply the algorithms known as Bubble Sort, Shuttle Sort and First-Fit, know how to define the size of a problem, and the efficiency and order of an algorithm.

• Shashank has a good article Comparison and Non-Comparison of Sorting Algorithms

• Mega-Math has a complete section on Algorithms at locations below with exercises and solutions in most cases:
  
  1. Greedy algorithms 
  2. Brute force algorithms
  3. Mathematics in Maps and Planning
  4. Brute Force and Other Algorithms

• Thomas Niemann has the Sorting and Searching Algorithms: A Cookbook that offers great explanation of a collection of searching and sorting algorithms. However some of the data structures used may be a bit advanced for students at this level.

• Warp has a website for Comparison of Several Sorting Algorithms. This study is on sorting items in an array in memory using comparison sorting (because that's the only sorting method that can be easily implemented for any item type, as long as they can be compared with the less-than operator).
  
  See also the article on Double-Burst-Selection Sort.

• BetterExplained has a great article Sorting Algorithms that discusses the complexity and running time of each.

• Michael Fong has a great site dedicated to explaining each Sort Algorithm in detail discussing their working and complexity:
  
  1. Bubble Sort
  2. Selection Sort
  3. Insertion Sort
  4. Shell Sort
  5. Merge Sort
  6. Quick Sort
  7. Heap Sort
  8. Counting Sort
  9. Radix Sort
  10. Bucket Sort 

• A Star Maths and Physics website offers a range of helpful resources in learning the following algorithms:
  
  1. The Shell Sort Algorithm
  2. Bubble Sort Algorithm
  3. The Quick Sort Algorithm
  4. The Shuttle Sort Algorithm
  5. Packing Algorithms – The First Fit Algorithm
  6. The First Fit Decreasing Algorithm

• Jaswinder Pal Singh explains sorting and searching algorithms in his lecture on Algorithms. See also the continutation to the lecture.

• George Bebis has the following lecture presentations of interest in algorithms. Please be aware these are lectures offered at university level and some areas could be too advanced for this level:
  
  1. Asymptotic Analysis
  2. Insertion Sort, Bubble Sort, Selection Sort
  3. Mergesort, Quicksort
  4. Randomizing QuickSort
  5. Heapsort
  6. Linear Sorting
  7. Hashing
  8. Binary Search Trees
  9. Red Black Trees
  10. Dynamic Programming
  11. Graphs
  12. Minimum Spanning Trees
  13. Shortest Paths
  14. NP-Completeness

• William Denniss has a page The Heroic Tales of Sorting Algorithms which attempts to explain some popular sort algorithms in terms of their complexity

• Software Security Lab, Taiwan has some lectures in algorithm analysis that explains some key concepts such as costs, the Big-Oh Notation and sort algorithms:
  
  1. Analysis of Algorithms (some parts may be too advanced for this level)
  2. Divide and Conquer, Merge/Quick Sort (some parts of this could be ignored as they go beyond our level)

• Celtic Kane Online's Computer Science Primer course has a short section in Sorting which explains the many different ways to sort lists — learn what each method is and how it works.

• Jeremy Kubica's Computational Fairy Tales has the following fairy tales/stories that explain the algorithms below:
  
  1. Hunting Dragons with Binary Search
  2. Breadth First Search and the Pig Thief
  3. Why Tailors Use Insertion Sort
  4. Bullies, Bubble Sort, and Soccer Tickets
  5. Minimax Search and the Oracle of Old Toronto

• Laura I. Toma has the following course notes on algorithms and their effeciency:
  
  1. Efficiency of Algorithms
  2. Efficiency of Algorithms continued (discusses searching and sorting algorithms)
  3. More on Efficiency of Algorithms

• Greg Mori has a course Data Structures and Programming (uses Java and C++ implementations) with the following resources:
  Note: These notes discuss a lot more than what is required for high school, but the notes should be very clear and easy to understand for teachers!
  
  1. Big O Notation: discusses time and space efficiency of algorithms with examples
  2. Binary Search Trees: discusses trees in general with sort algorithms for trees
  3. External Storage: discusses searching through large data sets

• William J. Taffe has lecture notes in Algorithms

 

Online Guides: Advanced Resources
These set of resources aim at conveying an advanced understanding of the concepts with tutorials, lecture notes and handouts. They are generally more suitable for teachers to get a a broader view of the topic than for teaching students.

• Lars Vogel has a tutorial in Complexity Analysis of Algorithms. See also other related algorithms and their implementation in Java:
  
  1. Quicksort
  2. Mergesort
  3. Sequential and binary search
  4. Shuffle an Array or a List - Algorithm
  5. Towers of Hanoi
  6. Dijkstra's Shortest Path Algorithm

• Bogotobogo has a section on Algorithms that discuss the following algorithms with examples:
  
  1. Algorithms - Introduction
  2. Bubble Sort
  3. Insertion Sort
  4. Quick Sort
  5. Bucket Sort
  6. Shell Sort
  7. Merge Sort
  8. Heap Sort
  9. Selection Sort
  10. Counting Sort
  11. Radix Sort
  12. Stack Data Structure

• Neli P. Zlatareva has a few lectures with notes on algorithm analysis:
  
  1. Algorithm Efficiency, execution times, Big-O etc
  2. Comparing some popular sorting techniques in terms of their efficiency
  3. Some advanced sorting methods and their efficiency

• Jessen Havill has some good examples of common algorithms at locations below:
  
  1. First iterative algorithms
  2. Bubble sort
  3. Towers of Hanoi
  4. Postfix algorithms
  5. Checking permutations
  6. Binary search tree algorithms
  7. Maze algorithms

• Daniel Ángel Jiménez has lecture notes in his course Analysis of Algorithms. See lecture 9 in particular on the limits of sorting algorithms.

• Robert Sedgewick and Kevin Wayne at Princeton University offer good explanation of Various Sort Algorithms implemented in Java. This is a great resource for teachers running this standard alongside programming ones. See also the algorithm animation applet Java Animations of Shellsort and Variants and Elementary Sorts lecture slides.

• David Schmidt’s course in Data Structures discusses sorting and searching algorithms and measuring time complexity  with theory and exercises at the locations below:
  
  1. Searching and Sorting
  2. Time complexity measures

• Robert Holte has a data structures course with lecture notes in Sorting Algorithms

• softpanorama has an interesting read at Slightly Skeptical View on Sorting Algorithms

• Rashid Bin Muhammad has sections explaining each of the following algorithms including their complexity:
  

  1. Bubble Sort

  2. Insertion Sort
  3. Selection Sort
  4. Shell Sort
  5. Heap Sort
  6. Merge Sort
  7. Quick Sort
  8. Counting Sort
  9. Radix Sort
  10. Bucket Sort

• Eric Pacuit gives a lecture on Cake Cutting Algorithms (also referred to as Cookie Cutting Algorithms, see Wikipedia: Fair Division and Cake or Cookie Cutting Algorithm)

• Konstantin (Costas) Busch has a very clear presentation on Cake Cutting Algorithms called Cake Cutting is Not a Piece of Cake

• Donald Chin has the following resources including exercises from his course Design and Analysis of Algorithms. These resources are quite advanced for this level.
  
  1. Short guide to Big-Oh and Algorithm Analysis
  2. Motivating Examples
  3. Code Analysis Exercises
  4. Code Analysis for Loops Exercises
  5. Analysing Mergesort, Quicksort, Quickselect

• Vladik Kreinovich has the following lecture notes and exercises for the course Elementary Data Structures and Algorithms:
  
  1. Lecture Notes in Complexity
  2. Fibonacci Numbers assignment to compare the efficiency of recursive and non-recursive approaches for one specific problem
  3. Assignment is to practice searching, sorting, and runtime estimations

 

---

Visual Simulations & Demonstrations: Basic Resources
Here we have compiled a list of visualisation resources that demonstrate the more main stream sort algorithms, and also use simpler graphics to illustrate the concepts.

• Thomas L. Naps has Sorting Out Sorting, an interactive way to demonstrate some common sort algorithms:
  
  1. The demo with guidance and interactivity
  2. Lite Version with audio guidance
  3. Documentation

• Mr Barton Maths has a great resource called Sorting Algorithms, which is an impressive spreadsheet which covers bubble sort, shuttle sort, and other sorting algorithms. the original list of numbers can be edited to suit your needs.

• University of Washington's BENEFIT (Fluency with Information Technology) course has a great animation of Bubble Sorting of CDs in a library. See also another presentation From Algorithm to Program

• Sorting Algorithm Animation System (SAAS) features a very clear comparison of sort algorithms using animation. This animation can also be downloaded for offline use at any time.

• Math Site is a good site that explains sort algorithms and also lets you do the sort yourself with instructions on each step of the algorithm. Students can use this site to get guided on sort algorithms step-by-step

• Universite Nice has an Interactive Simulation of Bubble Sort, where the user gets to try out the sort and recieve feedback for mistakes.

• R Mukundan demonstrates both Linear and Binary searches using visual simulation at the Java Applets Centre

• Max Nagl has AniSort, a set of animations for popular sorts

• Tristan Tower has the following sort algorithm demos with the power to step through code:
  
  1. Quick Sort
  2. Counting Sort

• David Martin's Sorting Algorithms visually demonstrate the concept of some popular algorithms for sorting data.

• Brian S. Borowski's Sorting Demo is a gallery to demonstrate most sort algorithms with source code supplied. Note: This demo is unique in that the user can input the data to be sorted and watch the animation!

• Toshimi Minoura has the Bubble Sort applet

• Sartaj K Sahni has the following applets to demonstrate algorithms where you can create your own arrays:
  
  1. Bubble Sort
  2. Insertion Sort

• Ryan Compton has a really cool way to visualise algorithms is using different sound frequencies that need ordering or sorting

• Aldo Cortesi has a static way of representing sorting algorithms using SortVis. See also his earlier blog on Visualising Sorting Algorithms

• Ian Greenleaf has another fun and static way of Visualizing Sorting Algorithms

• David Galles at the University of San Francisco has a complete range of visualisations in one package called Data Structure Visualisations that has visualisations of several sort algorithms and much more. Please remember that you will need Java installed for opening this JAR file.

• Keld Helsgaun has the following applets that demonstrate some algorithms:
  Note: Please use Internet Explorer only for these applets to work properly
  
  1. Insertion sort
  2. Selection sort
  3. Bubble sort
  4. Shellsort
  5. Partition
  6. QuickSort1
  7. QuickSort2
  8. Heap
  9. Priority queue
  10. Mergesort
  11. String searching
  12. Graph search
  13. See the complete list of applets at Animering af algoritmer

• Phillips-University of Marburg, Germany has an applet to demonstrate several algorithms at Data Structure Navigator. Please use the instructions below:
  1. Unzip the contents to a folder
  2. Double click and open 'start'
  3. From the menu choose Data Structures - Sorting Algorithms
  4. Click on the desired algorithm

• R K Ghosh from IIT, India has an Applet Page for Sorting that demonstrates several sorting algorithms

• Kirk Pruhs from University of Pittsburgh has several applets to demonstrate sorting algorithms below:
  1. Sorting Applet 1  allows the user to enter up to 25 of their own numbers and watch the applet sort the numbers
  2. Sorting Applet 2 This applet uses bar graphics as size indicators and includes a counter for the numbers of moves made and the number of comparisons made
  3. Sorting Applet 3 This applet also uses bars as values and uses a little bit more animation to show the steps involved in performing certian sorts. This applet also has information printed at the bottom to show / explain why objects are being moved as they are. The applet also has several interresting modes to play around with.

• Erhard Ploedereder, University of Stuttgart has The Sort Algorithm Animator  V1.0

• Alejo Hausner from Princeton University has the following algorithm visualisations:
  
  1. Bubble sort
  2. Quicksort
  3. Merge sort

• Herb Dershem from Hope College CS has a website called The Animator that visualises several sorting algorithms

• Dominique Thiébaut has the Sorting Algorithms page that demonstrates Insertion, Quick, Shell, Selection, Heap and Bubble sorts with source code shown in some cases.

• 2 July Maths UK website for Mathematics has some useful resources in Algorithms and their development:
  
  1. Notes on algorithm development (discusses sorts, searches and others)
  2. Bubble sort
  3. Quick sort
  4. Shuttle sort
  5. Bin Packing

• YouTube user ollloolo has done the Bubble Sort using Lego Bricks and Workmen!

• waldomaths has the following resources and teaching materials:
  
  1. Bubble Sort (Slideshow)
  2. Shuttle Sort (Slideshow)

• Christine Mumford has excellent demonstrations of the following bin/box packing and Travelling Salesman algorithms developed by various people:
  
  1. Level Packing by Steve Cotton (Read Me Help)
  2. Split Packing by Steve Cotton   (Read Me Help)
  3. Bottom Left Packing by Steve Cotton   (Read Me Help)
  4. Bin Packing Algorithms: Level and Shelf  by Heidi Smith
  5. Slicing Floorplan 1: Slicing Floorplans, Slicing Trees, Binary Operators, Stack Evaluation or Dead Space by Lisa Daniels
  6. Slicing Floorplan 2: Enter your own Postfix Expression by Lisa Daniels
  7. Travelling Salesman Heuristic: Nearest Neighbour, Multi-Fragment, Farthest Insertion by Howard Plummer

• Stephen Y. Chen has the website to demonstrate Recursive Sorting:
  
  1. Quick Sort to demonstrate the standard operation of recursion -- "depth-first, left to right". See description and instructions
  2. Merge Sort to demonstrate the standard operation of recursion -- "depth-first, left to right". See description and instructions
  3. Modified Quick Sort to demonstrate the recursive sorting algorithms operating in "level-order". See description and instructions
  4. Modified Merge Sort to demonstrate the recursive sorting algorithms operating in "level-order". i.e. this version of merge sort creates two halves, then four quarters, then eight eighths, etc.  In the level-order applet, all recursive calls at the same level (e.g. the eight eighths) are processed in sequence. See description and instructions

• Norahiko has a nice set of visual simulations of sorts with source code in Javascript

• I PROGRAMMER has SilverSort, a sorting lab in Sliverlight made to work with Silverlight version 4 for IE. For more documentation, please visit Silver Sorting Lab

• Kirk Pruh hosts the following applets for sorting demonstrations:
  
  1. Animation of Sort Algorithms Applet written by Justin Dildy & Sandeep Poonen
  2. Sorting Demo Applet which also allows comparisons of algorithms. Note: run different sort algorithms on the same set of data and click on Compare Algorithms to get the table of results

• James Seibel has the Interactive HTML5 Canvas Demonstration of Dijkstra's Algorithm which is a great visualisation of Dijkstra's shortest path algorithm

• John Morris has some algorithm animations developed by Woi Ang and others. This site also offers some analysis of the sort algorithms:
  
  1. Woi Ang's Insertion Sort Animation
  2. Woi Ang's QuickSort Animation
  3. Chien Wei Tan's QuickSort Animation
  4. Woi Ang's Bin Sort Animation
  5. Woi Ang's Radix Sort Animation
  6. See also Mervyn Ng's Minimum Spanning Tree Animation
  7. See also Mervyn Ng's Animation of Dijkstra's Algorithm

• Dorgival Olavo Guedes Neto has Animation of Sorting Algorithms

 

Visual Simulations & Demonstrations: Advanced Resources
These visualisation resources are to demonstrate several other sort algorithms, and some times need setting up, and use complex graphics to illustrate the concepts.

• Henry has several Java Applets that can be used to demonstrate different sort algorithms

• David Eck has another visual or timed view of sorting algorithms

• Thomas Baudel has visualisations of sort algorithms

• The Learning Point has visualisations of some algorithms and data structures

• Fachhochschule Flensburg has a page dedicated to sequential and parallel sorting algorithms. See in particular the Sorting Contest that compares some sort algorithms

• Showsort has visualisations of a complete set of algorithms from bubble sort to tree sort. This application presents a graphical representation of sorting an array of integers. In addition to the animated sorting, this app includes a description of each sorting algorithm with the source code.
  Note: This applet is not recommended for Internet Explorer.

• Jacob Seidelin has Canvas visualisation of algorithms and is another way to visualise sorting algorithms
  
  Teachers could print these out for different search parameters for different sort algorithms and hang these canvases as posters in the classroom. These could then be used in quizzing the students on specific algorithms or comparing sorts side by side.

• Benjamin Erb has created a colourful poster to visualize how 12 of the famous sorting algorithms work:
  
  1. Sorting Algorithm Visualization Poster (PNG)
     
  2. Sorting Algorithm Visualization Poster (PDF)
  3. Information in German

• Virginia Tech Algorithm Visualization Research Group has visualisations of Heap Sort and Radix Sort techniques.

• Algorithms in Action project from University of Melbourne has Shell Sort, Quick Sort, Heap Sort and several other algorithm visulations. See also the graph algorithms such as Breadth First Search and Depth First Search

• Several developers created AlViE that can be used to visualise many algorithms. You can download the complete package here. You can view video demonstrations of some popular algorithms below:
  1. Depth First Search
  2. Breadth First Search
  3. Dijkstra
  4. Fibonacci 
  5. Towers of Hanoi

• TRAKLA2 Software Project has published a list of algorithm learning environments with limited functionality intended for Data Structures and Algorithms course:

  1. Binary search
  2. Quicksort
  3. Mergesort (iterative)
  4. Mergesort (recursive)
  5. Heapsort
  6. Selection sort
  7. Insertion sort
  8. BFS
  9. DFS
  10. Dijkstra‘s algorithm

• Arno has a private blog with an English translation of the original work in German from Peter Weigel and Andreas Boltzmann at Sorting Algorithms Visualized

• Dominique Thiebaut has a few Sorting Algorithms visualisations in a repository

• Darry Nester from Bluffton University has Sorting Demonstrations in Java showing steps through the code. This could be a good tutorial for students who are trying to code the different algorithms

• Robert Sedgewick's Java Animations of Shellsort and Variants

• Wolfram Demonstrations Project has the following activities you can give to students to try:
  Note: You will need to install the Wolfram CDF Player in order to use these activities. You can either download each demonstration or use your browser to run it
  
  1. Quick Sort Vs Selection Sort
  2. Extended Bead Sort
  3. Breadth First and Depth First Searches
  4. Towers of Hanoi

 

---

Classroom Activities and Games: Basic Resources
Here we list mostly activities that demonstrate the concept of an algorithm and how different algorithms work differently. For example, by doing the CS Unplugged's Lighest and Heaviest activity, students can get an understanding of how different sort algorithms work in relation to each other

• CS Unplugged Activity 6 - Battleships: Searching Algorithms

• CS Unplugged Activity 7 - Sorting Algorithms examines selection sort, quick sort, insertion sort, bubble sort and merge sort.

• Brian S. Borowski's Guessing Game could be used to illustrate the concept of Binary Search.

• Jo Edkins has the Weighing Balls Puzzle that explains the concept of using binary splitting to sort out balls with different weights.

• Cre8ate Maths UK has a resource called Ferries that allows pupils to develop their own strategies and to consider the idea of an ‘efficient’ algorithm. The activity explores First Fit and Full Bins algorithms and lets students compare the effectiveness of these algorithms.
  Note: You will need to register (free) as a teacher at Cre8ate Maths UK to access this resource

• Mordechai (Moti) Ben-Ari from the Weizmann Institute of Science, Israel has programmed linear, binary and hashing searches, and also quick sort and selection sort algorithms in Scratch which can be downloaded in a zip file of the complete set of activities . Please read the ReadMe.txt for documentation.

• CS4FN has the following online activities/articles that demonstrates concepts in algorithms and complexity:
  
  1. Swap Puzzle (Interactive Activity): Algorithms is also about devising efficient ways of doing things. Two different ways of doing something could both guarantee to get the job done but one may be quicker than the other and so better.
  2. Bean Counting
  3. Non-reversing Mirror
  4. The cure that just folds away

• The Royal Institution UK and Microsoft Research together have produced activities in sorting algorithms for the classroom. See also, games and tryouts related to these lectures at the interactive website

• Computer Science & Engineering for K-12 (cse4k12.org) has an activity Using Collectible Card Game(CCG) cards to Teach Searching/Sorting. Note: You will need a Google account to access this activity

• MATHmaniaCS Lesson 7 – Searching

• MATHmaniaCS Lesson 8 - Sorting

• Computing Science Inside Workshop (Requires Registration) – Algorithm Development

• Jim Loy has the The High Low Game that demonstrates a binary search

• Susan Rodger, Susan Horowitz and Barbara Ryder have several activities that are designed to promote logical thinking and learning logical approaches to programming in the Construct Algorithmic Structure section

• ROCS, Purdue University has Logic Puzzles that were developed as an extension activity to teach students logical thinking in order to solve puzzles.

• Suffolk Maths has the following spreadsheet based activities to demonstrate different algorithms in terms of the number of iterations required developed by Debi Hand:
  
  1. Bubble Sort Checker
  2. Shuttle Sort Checker

• Dr Lisa N. Michaud has the following resources in algorithms:
  
  1. Algorithms Handout
  2. Develop an Algorithm Lab Session (Top Down Approach)

• The Peasant Algorithm and Ancient Egyptian Multiplication are tricks for doing multiplication using only doubling. At heart they are really just multiplying binary numbers. More resources at locations below:
  
  1. For information on how this algorithm is related to binary numbers, please read The Math Forum's explanation at Russian Peasant Multiplication.
  2. To introduce concepts of algorithms, read about Formal algorithms for Subtraction
  3. To introduce concepts of algorithms, read about Formal algorithms for Multiplication

• CS4FN has an activity related to the French Peasant's Multiplication called the The French Peasant's Lock and Gray Code. The solution to the lock is actually something know to Computer Scientists as Gray Code : a code used in modern digital TV. Whatever, their physical form all the variations of the lock puzzle have the same solution and are logically (and so their solutions algorithmically) identical. Solve one and you've solved them all (Computer Scientist's love pulling that trick with problems!)

• Frank Baker has a card sorting activity, that gets students to think about the problem of sorting some playing cards.  The rules of the "game" essentially abstract the "rules" for the comparison-based sorting in a computer. It seems to work well to get kids into the CS mindset, and builds some confidence that they can succeed. It has the nice side effect of teaching the O(n^2) sorting algorithms and a little big-oh analysis (if you choose to do so) all on the first day!

• MathsNet has the following free resources:
  
  1. Quick Sort Algorithm
  2. Comparing Algorithms

• Richard Lawlor has the following explanatory notes for the popular sorting algorithms below. Teachers can use these notes to either explain the sorts of set tasks for writing these algorithms.
  
  1. Selection Sort
  2. Bubble Sort
  3. Quick Sort,  Example 2
  4. Merge Sort Example and Pseudocode
  5. Searching Algorithms

• School Workout UK has the following useful resources:
  
  1. Teaching notes on Bubble and Shuttle Sort
  2. See also an Assessment on Algorithms

• Namamic UK has illustrative examples for explaining the following algorithms:
  
  1. Binary Search
  2. Bubble Sort

• IFORS Melbourne has the following applets that demonstrate (with interactivity in some cases) some algorithms below. Note: Please run these only on Internet Explorer
  
  1. Shortest Path Problem
  2. Dijkstra's Algorithm

 

Classroom Activities and Games:  Advanced Resources
These resources are not neccessarily aimed at a higher level of students, they sometimes require more preparation and in some cases more pupils in the classroom. For example, Steve Wolfman's Couting the Class activity requires 50 students as a guideline and may need customising to your own class needs.

• Paul A. G. Sivilotti has a Kinaesthetic Learning Activity (KLA) activity to introduce CS concepts to high school girls called Parallel Programming: Parallel Programs are Fast. This activity compares sort algorithms such as Bubble Sort, Even-Odd Transposition Sort and Radix Sort.

• Steve Wolfman has a KLA activity Counting the Class for students to invent and analyze for counting the number of people in the class and implement at least one on the spot. After the exercise, students will understand that many different algorithms may address a single problem. They will recognize that there may be tradeoffs between speed, accuracy, and accuracy guarantees (such as upper and lower bounds).

 

---

Videos: Basic Resources
These videos help to re-inforce the concepts of algorithms.

• A fun video to watch is where a 19 month old girl tries to sort out her toy boxes in order of the next largest one at The Maggie Sort Algorithm

• YouTube user ollloolo has done the Bubble Sort using Lego Bricks and Workmen!

• YouTube user udiprod has a funny, but explanatory visulisation of Quick Sort using robots and a comparison with Bubble sort

• YouTube user AlgoRythmics has a fun way of demonstrating sort algorithms using dance. More information can be found at I PROGRAMMER:
  
  1. Shell Sort with Hungarian (Székely) folk dance
  2. Selection Sort with Gypsy folk dance 
  3. Bubble Sort with Hungarian ("Csángó") folk dance
  4. Insertion Sort with Romanian folk dance

• Watch the video based on the CS Unplugged Activity 7 on Sorting Algorithms on YouTube

• A related YouTube video from CS Unplugged show is on Binary Search: Divide and Conquer

• XOAX offers a great set of tutorial videos with explanation of popular algorithms and more at locations below. You can also view the playlist here.
  
  1. Bubblesort
  2. Insertion Sort
  3. Merge Sort
  4. Quicksort
  5. Linear and Binary Searching
  6. Big O, Big Omega, and Big Theta Notation

• Watch a Schoolhouse Rock-style YouTube video that teaches the difference between two sorting algorithms---selection sort and quick sort. Created for use in an introductory computer science class at Rutgers University (NJ, USA)

• O2 Learn has the following tutorial video explaining The Quick Sort Algorithm

• codegearguru has series of videos that demonstrate the 4 different sort algorithms using playing cards at locations below:
  
  1. Bubble Sort
  2. Insertion Sort
  3. Selection Sort
  4. Merge Sort

• Knight School 2009 at Menlo School has a video on Algorithmic Thinking on YouTube that illustrates how several simple sorting algorithms operate, using people as the objects to be sorted at Sorting Algorithms. Please see the notes attached below the video for further explanation of each sort algorithm used here.

• Royce Neagle has videos on the two following related topics below (these are more suitable beyond level 1):

  1. Hill Climbing: Using searching to solve problems with many solutions, some of which are better than others.
  2. Optimisation: Techniques used to solve very hard problems with no quick and easy answer.

• Brian K Harvey and Dan Garcia run a course CS10 Beauty and Joy of Computing that has lectures of interest below:
  
  1. Algorithms
  2. See also Algorithmic Complexity

• waldomaths has the following explanatory videos (requires Internet Explorer browser):
  
  1. Bubble Sort Algorithm
  2. Shuttle Sort Algorithm

• Larry Snyder and Mel Oyler offer video lectures in the following topics:
  
  1. Searching
  2. Algorithmic Thinking
  3. Binary Search - A Fundamental Algorithm
  4. Thinking, Algorithmic & Otherwise

 

Videos: Advanced Resources
These videos are from lectures offered at undergraduate level in CS and therefore can be used for reference and further study by teachers.

• Tim Roughgarden has his complete set of video lectures from his course Design and Analysis of Algorithms

• MIT Open Courseware in Electrical Engineering and Computer Science has the following relevant lectures by Eric Grimson and John Guttag. The lectures are available on their archives in MP4 format and also on YouTube.
  
  1. Complexity; log, linear, quadratic, exponential algorithms
  2. Binary search, bubble and selection sorts

• MIT Open Courseware has a complete set of free lectures and videos for their course Introduction to Algorithms

• Grady Booch in this thought-provoking presentation (delivered at the 2007 SIGCSE Technical Symposium) explores the beauty and the complexity of software development and raises key questions about the limits of what we know, what we can do, and what we should do. He also explores the history of software development and what the future might hold. Teachers can use this presentation to inform their own knowledge or classroom practices and share it with students to provoke interesting discussions about our history and our future.
  
  Download presentation.
  Download videos at Data and Halo.

• HegartyMaths has the following tutorial videos in various algorithms:
  
  1. Bubble Sort Algorithm
  2. Shuttle Sort Algorithm
  3. Order of an Algorithm
  4. Chinese Postman/Route Inspection
  5. Travelling Salesperson

 

Attachment	Size
Computer Science Concepts AS 1.44 Unit Outline - 09.08.10.pdf	275.44 KB