Open main menu

CDOT Wiki β

BTC640/Assignment1-Winter2012

You can see the best submissions for this assignment HERE

Teams

BTC640

  1. Hyungryul (Steven) Chun, Raymond Hung, Jordan Kirkham, Sandra To, Stanley Tsang
  2. Kiu Kwan Leung, Dixon Lau, Krush Pachani
  3. Sukhbir Singh Ghotra, Gagandeep Singh Gill, Imtiaz Latif, Cheryl Mascarenhas
  4. Marius Stratulat, Aayush Dhamala, Amirreza Bijarchi, Nikita Kuznetsov, Carl Desautels
  5. Dmitry Garanin, Melvin Berena, Jude Fernandez, Calvin Au
  6. Ali Shoja, Shahan Saeed, Nan Zhou
  7. Diogo Monteiro
  8. Adam Joseph Chan, Aakash Dhawan, Edward Ka Kiu Sin
  9. Jessy Scott Cohoon, Lu Liu

Overview

Degree students: you will need to work in teams (ideally 3 person teams) and implement a visual representation using Processing.js of the algorithms listed below. Your team needs to accumulate a total difficulty of 3 - that can be any combination of the options listed below.

Diploma students: you can work in teams in which case you need to accumulate a total difficulty of 2. You may also work on your own, in which case you only need a difficulty of 1.

Email me as soon as possible with a list of team members, even if you're working on your own.

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.

Your code only needs to work in Firefox.

Plagiarism Rules

You may use any resources, including code from the internet or books. It will not be considered plagiarism as long as you mention where you got which code from. There is no minimum percentage of code in your assignment that you have to write completely by yourself.

You may also copy code from other students, but only with their permission, and again you have to mention who you got what code from.

If I see that some code has been copied and you haven't listed the source - I will consider it plagiarism, and treat it as explained in the Seneca Academic Policy.

Submission

Submit the following to Moodle:

  • A zip file with all your work so I can extract it and run it.
  • The file where you list the sources of your code, including a list of what each team member worked on.

The deadline for this assignment is the 30th of march. Late penalty is 10% per day. Even if your assignment is 5 days late or more - you still need to submit a satisfactory assignment to pass the course.

This assignment is worth 25% of your final grade.

Data Structures and Algorithms to Choose From

Stack

Difficulty: 1

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

Difficulty: 1

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

Difficulty: 1

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

Difficulty: 1

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

Difficulty: 3

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

Difficulty: 3

Same as the above, but a different algorithm.

Insertion Sort

Difficulty: 3

Same as the above, but a different algorithm.

MinHeap

Difficulty: 3

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