User - MathOverflow

Answer by avr-white for Applications of Math: Theory vs. Practice

2010-09-11T00:47:39Z

I use Octave and Matlab to code algorithms to quickly check particular things out. Sometimes, that involves simplifying things. See for example, my answer to a question which misuses the word "permutation" on this site, when what is really meant is a fairly simple problem.

Simplifying the complex sounding questions by looking at all of the aspects of it is a mathematical trait and habit I've been trained in, especially by mathematics and mathematicians. Formal education can also mislead you into applying the tools you have at hand rather than the best tool for the job. Just because you've got a chainsaw doesn't mean that you have to or even can use it to solve the problem that needs a delicate chisel or gouge.

I also like to use command line tools such as "sed" and "awk" on large columnar text data files, usually with the "bash" shell in unix or linux.

Answer by avr-white for Open source mathematical software.

2010-09-13T23:29:29Z

I'll second the votes for Sage, Macsyma as Maxima and Wxmaxima, Scilab, Octave, R, and GAP.

For kids to play with are KGeometry KiG (K-interactive-Geometry), letting you draw out geometric relationships and actively move points around, letting all defined subcomponents change with it: e.g. draw three points, define+draw the line segments between the points, define+draw the perpendicular bisectors of these line segments, define+draw a circle that touches the three points of the triangle. Now drag any of the three points of the triangle around and watch all of the defined components move along to remain the bisectors / intersections / circles consistently. It's a great way to play around with geometric constructions.

Also, you can't go wrong with using awk, sed, and bash on the command line.

Answer by avr-white for Uniquely generate all permutations of three digits that sum to a particular value?

2010-09-11T00:30:42Z

This really is the same as finding the plane $x+y+z=n$ in 3-space $\mathbb{R}^3$ and finding the intersection of this plane with the lattice points in $\mathbb{Z}^3$.

Octave code (also matlab code) which returns answers in lexicographical order:

for x=0:n
for y=0:(n-x) % y must be less than (n-x+1)
z=(n-x-y); % semicolor suppresses printing
disp([x y z])
end y,x

Don't make it more complicated than it has to be. Also similar answer below. For every point on the 2-d lattice, $\mathbb{Z}^2$, calculate the $z=n-x-y$ value, and it's a valid answer for $0 \le z \le n$, $x \ge 0$, $y \ge 0$.

Answer by avr-white for What is the easiest randomized algorithm to motivate to the layperson?

2010-09-11T01:07:06Z

Ant algorithms to determine and select the best path from one place to another; ant algorithms can also be used to select the goals along with the paths.

Ant trails and pheremones are easy to describe. Every one has seen them and it's fascinating to explain how miniscule ant-brains can carry out a parallel distributed algorithm that can also be used to select the best routing path on the internet or for a quick and dirty solution to the traveling salesman problem.

Answer by avr-white for Similarity of weighted graphs

2010-09-11T00:13:36Z

Comparing two graph structures with the same number of vertices and edges to see if they are equivalent would be the graph isomorphism problem. The graph isomorphism problem is known to be NP in complexity, but it is not known if it is NP-complete nor is it known to be solvable in polynomial time.

Comparing two graph structures with different numbers of edges and vertices would be a slightly bigger problem. Call the graph with the smaller number of vertices $G_1$ and the graph with the larger number of vertices $G_2$. Now you have to search to see if $G_1$ is isomorphic or similar to a subset of $G_2$. Depending on the relative sizes of the graphs, this could take a long time to evaluate.

If you already has a similarity metric defined for two graphs with the same number of vertices, e.g. $d(G_a,G_b)$, where $|V_a|=|V_b|$, then you could proceed as follows.

One way to attack the problem is to take the smaller graph as the template and see if you can overlay it onto the larger graph by taking a subset of the vertices of $G_2$, call it $H_n$ where $n$ can be one of the $\binom{|V_2|}{|V_1|}$ ways of picking a subgraph of $G_2$ with the same number of vertices as $G_1$. $|V_1|$= the number of vertices in $G_1$, and $|V_2|$= the number of vertices in $G_2$ in this case.

One similarity metric to use to compare two graphs with the same number of vertices would be to apply a mapping between vertices between $G_1$ and $G_2$, e.g. {$m: V_{1,a} \to V_{2,b}$}.

Then add up the number of coincident edges: for each edge in $G_1$ which connects $V_{1,i}$ and $V_{1,j}$, find the two corresponding vertices in $G_2$ , $V_{2,m(a)}$ and $V_{2,m(b)} $,and see if there is a corresponding edge is $G_2$ between these corresponding vertices.

Comment by

2010-09-13T23:16:38Z

Sorry. :), didn't see your code below. Though this code is for octave rather than for BASIC.