CSC 216/s08/eschew disenchantment: Difference between revisions

From Expertiza_Wiki
Jump to navigation Jump to search
 
(17 intermediate revisions by 2 users not shown)
Line 10: Line 10:
===Participants and props===
===Participants and props===


Seven students will participate in the exercise. They will need numbered notecards, scotch tape, and a series of hats. There should be seven hats as follows: One master hat, two delegate hats, and four peon hats.
Seven students will participate in the exercise. They will need seven numbered note cards, scotch tape, and a series of hats. There should be seven hats as follows: One master hat, two delegate hats, and four peon hats. The instructor should have the means to display our [http://www4.ncsu.edu/~tsarehar/flash/merge/MergeSort.html flash animation] and then display the pseudocode during the exercise.


===The script===
===The script===
Line 17: Line 17:
#There should be a pseudocode description of the merge sort algorithm on a large display.
#There should be a pseudocode description of the merge sort algorithm on a large display.
#The numbered notecards must be taped together in a randomly ordered line.
#The numbered notecards must be taped together in a randomly ordered line.
#Students should be shown [http://people.engr.ncsu.edu/efg/216/s08/video/1/g2/mergesort.swf our animation of the mergeSort algorithm].


=====Pseudo Code=====
=====Pseudo Code=====
<code>
<code>
public int[] mergeSort(int[] m) {
public int[] mergeSort(int[] m) {
     if (m.length == 1) Return m
     if (m.length == 1) Return m
     if (m.length == 2) Sort m, then return m
     if (m.length == 2) Sort m, then return m
     Split m in half
     Split m in half
     Call mergeSort on each half
     Call mergeSort on each half
     Merge the two halves after they are sorted and returned
     Merge the two halves after they are sorted and returned (iterative merge of two ordered arrays)
     Return the array
     Return the array
}
}
</code>
</code>


====Activity====
====Activity====
First, the seven hats need to be assigned to the seven students. Then the student wearing the king hat should perform as though he is the initial call to mergeSort(). The king should use his delegates to handle his recursive mergeSort calls. The delegates should use their peons to handle their own mergeSort() calls.
First, the seven hats need to be assigned to the seven students. They will have different duties according to their different hats. The king represents the original call to mergeSort, the delegates are the first level of recursion, and the peons are the second level of recursion. Every student has the objective of applying mergeSort to the list they are given, but may behave differently due to the length of their list. Ideally the students will be able to infer what to do from the animation and pseudocode, but they may need hints according to the following sequence:
#The king un-tapes the list at the middle and tells a delegate to sort each half.
#Each delegate un-tapes their list in the middle and gives each half to a peon.
#Each peon should notice that their lists are of size two or fewer, and sort where necessary.
#Each delegate should accept the lists back from their two peons and merge them in order.
#The king should accept the lists back from the delegates and merge them in order.
 
 
When it is time for a participant to merge two ordered lists, they may do so without adhering to any algorithm.
 
===Further Illustration===
 
[[Image:Mergesort.jpg|frame|An example of a merge sort, showing the arrays through the process.]]

Latest revision as of 19:06, 6 November 2008

Formatting Resources

Formatting Help Guide from MetaWiki

The Hierarchical Merge Sort

The problem

In this exercise, we want to teach students the mechanics of a merge sort algorithm.

Participants and props

Seven students will participate in the exercise. They will need seven numbered note cards, scotch tape, and a series of hats. There should be seven hats as follows: One master hat, two delegate hats, and four peon hats. The instructor should have the means to display our flash animation and then display the pseudocode during the exercise.

The script

Setup

  1. There should be a pseudocode description of the merge sort algorithm on a large display.
  2. The numbered notecards must be taped together in a randomly ordered line.
  3. Students should be shown our animation of the mergeSort algorithm.
Pseudo Code

public int[] mergeSort(int[] m) {
    if (m.length == 1) Return m
    if (m.length == 2) Sort m, then return m
    Split m in half
    Call mergeSort on each half
    Merge the two halves after they are sorted and returned (iterative merge of two ordered arrays)
    Return the array
}

Activity

First, the seven hats need to be assigned to the seven students. They will have different duties according to their different hats. The king represents the original call to mergeSort, the delegates are the first level of recursion, and the peons are the second level of recursion. Every student has the objective of applying mergeSort to the list they are given, but may behave differently due to the length of their list. Ideally the students will be able to infer what to do from the animation and pseudocode, but they may need hints according to the following sequence:

  1. The king un-tapes the list at the middle and tells a delegate to sort each half.
  2. Each delegate un-tapes their list in the middle and gives each half to a peon.
  3. Each peon should notice that their lists are of size two or fewer, and sort where necessary.
  4. Each delegate should accept the lists back from their two peons and merge them in order.
  5. The king should accept the lists back from the delegates and merge them in order.


When it is time for a participant to merge two ordered lists, they may do so without adhering to any algorithm.

Further Illustration

An example of a merge sort, showing the arrays through the process.