BTC640/Assignment1-Winter2012

Overview

You will need to work in teams and implement a visual representation using Processing.js of one of the algorithms listed below.

If done properly the animations you create can be used to demonstrate data structures and algorithms in the DSA555/BTP500 courses in the following years.

Stack

Inspiration: http://www.cosc.canterbury.ac.nz/mukundan/dsal/StackAppl.html

The canvas will only have the stack itself. In the page beside the canvas there will be:

• A field that can be used to specify the value of the next element to be inserted, it can only be an unsigned integer.
• A button to push the element with the value in the field onto the stack.
• A button to pop an element off the stack. The value in the popped element has to be displayed somewhere in the canvas.
• The push/pop operations have to be animated.

Queue

Inspiration: http://www.cosc.canterbury.ac.nz/mukundan/dsal/QueueAppl.html

The canvas will only have the queue itself, arranged horisontally (not vertically as in the example above). In the page beside the canvas there will be:

• A field that can be used to specify the value of the next element to be inserted, it can only be an unsigned integer.
• A button to enqueue the element with the value in the field into the queue.
• A button to dequeue the element from the front of the queue. The value in the dequeued element has to be displayed somewhere in the canvas.
• The enqueue/dequeue operations have to be animated.

Cyclic Queue

Inspiration: http://www.cosc.canterbury.ac.nz/mukundan/dsal/CQueueAppl.html

This is the same as the Queue above, except all the space is preallocated, just not beeing used. Also both the front and rear of the queue may move upon enqueue/dequeue.

Singly Linked List

Inspiration: http://www.cosc.canterbury.ac.nz/mukundan/dsal/LinkListAppl.html

This is a singly linked list. The canvas will only have the list itself, including all the elements, connected by arrows (pointers). In the page beside the canvas there will be:

• A field that can be used to specify the value of the next element to be inserted, it can only be an unsigned integer.
• A button to prepend the element with the value in the field to the list.
• A button to remove the element from the front of the queue. The value in the removed element has to be displayed somewhere in the canvas.
• A field that can be used to specify a value to search for, and a button to do the search.
• The prepend/remove/search operations have to be animated.

Bubble Sort

Inspiration: http://math.hws.edu/TMCM/java/xSortLab/

The array is of a fixed size, the point is not the data structure but the sorting algorithm. The canvas will:

• Show the animations for including the current bubble and swapping the elements.
• Show the known biggest elements in the array.

In the page beside the canvas there will be:

• Buttons for step, stop/go, and restart with random elements.
• Fields for (optionally) manually populating the array with values.

Selection Sort

Same as the above, but a different algorithm.

Insertion Sort

Same as the above, but a different algorithm.

MinHeap

Inspiration: http://www.cosc.canterbury.ac.nz/mukundan/dsal/MinHeapAppl.html