## An illustration of Minuit minimizing a function

Here is an animation of how the function minimizer Minuit minimizes a function. The function to be minimized depends on two parameters so that one can visualize it. It was inspired by the ‘banana shaped valley’ function so that Minuit must take several steps to find the minimum. The value of the goal function is indicated by the color, i.e. the goal function is a ‘spiral’ whose depth increases as one goes more counterclockwise.

The types of the steps (shown at the top left) were inferred from the functions from which it was called. The minimization typically has two alternating phases: numerical determination of the gradient and line search along some promising direction. At the end, the second derivative is calculated (although the function has a discontinuity on one side).

The red point shows the coordinates with which Minuit calls a goal function to be minimized.

The arrow at the top left shows the direction from the previous to the current step. For example during the line search phase, the direction remains mostly fixed or is reversed while during the gradient calculation phase it looks like first the horizontal component is calculated and then the vertical one.

Read Full Post | Make a Comment ( None so far )

## An animation of adding elements to a heap

Here is an animation of how elements are inserted into a heap (sometimes used to implement a prioirty queue). At the top you can see the elements arranged in a tree, at the bottom is the corresponding array representation of the heap. The correspondence between the tree nodes and the array is such that the children of array element j are stored in positions 2j+1 and 2j+2 (where the indexing starts at 0).

The algorithm corresponds to what is described in section 4.3.2 of in “The Algorithm Design Manual” by Steven Skiena. Each time an element is added, it is put into the first empty position in the array representation at the bottom. This corresponds to making the new element a child of one of the leaf nodes. Then, the element is ‘bubbled up’ (swapped with its parent) as long as it is smaller than the parent.

Running the example requires Java Webstart (and is at your own risk, the author does not take any responsibility for any negative effects caused by running this example). To start the demo, click here. This demo makes use of the Trident java animation library.

Comments and suggestions are welcome !

Read Full Post | Make a Comment ( None so far )

## An animation of the Quicksort algorithm

Here is a (preliminary) animation of the Quicksort algorithm. At the same time, this is a small project to try out the Trident java animation library.

Running the example requires Java Webstart (and is at your own risk, the author does not take any responsibility for any negative effects caused by running this example). To start the demo, click here.

A few explanations:

• The example is modeled after the Quicksort implementation as given in “The Algorithm Design Manual” by Steven Skiena (Section 4.6)
• Those boxes which are already at the final position are drawn in white (instead of gray)
• The boxes with dark red background are those currently being worked on (between the variables l and h). The variables l and h themselves are shown by the boxes ‘L’ and ‘H’
• The variable i is displayed by the box I
• The pivot (against which the element at i is compared) is at position h in this implementation
• The box F corresponds to the value of the variable ‘firsthigh’ in Skiena’s book

You’ll notice that:

• after i reached the right end of the range currently being worked on (end of routine ‘partition’), the value originally at h will be put where ‘firsthigh’ is and is at its final position. The elements left of it (in the current range) will have a smaller value, the ones on the right a larger value.

Comments and suggestions are welcome !

Read Full Post | Make a Comment ( None so far )