Archive

Archive for the ‘mathematics’ Category

Installing ESS (Emacs Speaks Statistics)

20 April 2011 Leave a comment

Problem

You have a non-standard directory under which you install software. You have installed Emacs under this directory. Now you want to install ESS under this directory as well so that Emacs could interact with R.

Solution

Suppose your non-standard directory is

/scratch/username/usr

where username is your actual username. I assume that you have installed both Emacs and R under this directory. Download ESS and extract the downloaded tarball to

/scratch/username/usr/share/emacs/site-lisp

Edit your /home/username/.emacs by inserting the following lines:

;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;     
;; ESS: Emacs Speaks Statistics, mainly for R
;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;     

(load "/scratch/username/usr/share/emacs/site-lisp/ess-x.y.z/lisp/ess-site")
(setq inferior-R-program-name "/scratch/username/usr/bin/R")

Remember to replace “x.y.z” with the actual version number of ESS that you use. Now load Emacs and to use R from Emacs, enter the command

M-x R

This should bring up an R session from within Emacs. Here’s a screenshot for your viewing pleasure:

Typeset trees using TikZ/PGF

31 March 2011 Leave a comment

Some combinatorial trees typeset using TikZ/PGF. The Linux filesystem hierarchy:

The Linux filesystem hierarchy.

\begin{tikzpicture}
[-,thick]
\footnotesize
\node {\texttt{/}} [edge from parent fork down]
  child {node {\texttt{bin}}}
  child {node {\texttt{etc}}}
  child {node {\texttt{home}}
    child {node {\texttt{anne}}}
    child {node {\texttt{sam}}}
    child {node {$\dots$}}
  }
  child {node {\texttt{lib}}}
  child {node {\texttt{opt}}}
  child {node {\texttt{proc}}}
  child {node {\texttt{tmp}}}
  child {node {\texttt{usr}}
    child {node {\texttt{bin}}
      child {node {\texttt{acyclic}}}
      child {node {\texttt{diff}}}
      child {node {\texttt{dot}}}
      child {node {\texttt{gc}}}
      child {node {\texttt{neato}}}
      child {node {$\dots$}}
    }
    child {node {\texttt{include}}}
    child {node {\texttt{local}}}
    child {node {\texttt{share}}}
    child {node {\texttt{src}}}
    child {node {$\dots$}}
  }
  child {node {$\dots$}};
\end{tikzpicture}

Classification tree of organisms:
Classification tree of organisms.

\begin{tikzpicture}
[sibling distance=6cm,-,thick]
\footnotesize
\node {organism}
  child {node {plant}
    [sibling distance=2cm]
    child {node {tree}
      child {node {deciduous}}
      child {node {evergreen}}
    }
    child {node {flower}}
  }
  child {node {animal}
    [sibling distance=2.5cm]
    child {node {invertebrate}}
    child {node {vetebrate}
      [sibling distance=4.7cm]
      child {node {bird}
        [sibling distance=1.5cm]
        child {node {finch}}
        child {node {rosella}}
        child {node {sparrow}}
      }
      child {node {mammal}
        [sibling distance=1.5cm]
        child {node {dolphin}}
        child {node {human}}
        child {node {whale}}
      }
    }
  };
\end{tikzpicture}

The Bernoulli family tree of mathematicians:
Bernoulli family tree of mathematicians.

\begin{tikzpicture}
[-,thick,%
  every node/.style={shape=rectangle,inner sep=3pt,draw,thick}]
\footnotesize
\node {Nikolaus senior} [edge from parent fork down]
  [sibling distance=4cm]
  child {node {Jacob}}
  child {node {Nicolaus}
    child {node {Nicolaus I}}
  }
  child {node {Johann}
    [sibling distance=2cm]
    child {node {Nicolaus II}}
    child {node {Daniel}}
    child {node {Johann II}
      child {node {Johann III}}
      child {node {Daniel II}}
      child {node {Jakob II}}
    }
  };
\end{tikzpicture}

An expression tree:

Expression tree for the perfect square identity.

\begin{tikzpicture}
[-,thick]
\node {$+$}
  [sibling distance=2.5cm]
  child {node {$\times$}
    [sibling distance=1cm]
    child {node {$a$}}
    child {node {$a$}}
  }
  child {node {$\times$}
    [sibling distance=1cm]
    child {node {$2$}}
    child {node {$a$}}
    child {node {$b$}}
  }
  child {node {$\times$}
    [sibling distance=1cm]
    child {node {$b$}}
    child {node {$b$}}
  };
\end{tikzpicture}

Simple graphs, bridges of Konigsberg and directed graphs

26 March 2011 Leave a comment

Some combinatorial graphs drawn using TikZ/PGF. The seven bridges of Konigsberg:

Seven bridges of Konigsberg

\begin{tikzpicture}
[lineDecorate/.style={-,thick},%                                                
  nodeDecorate/.style={shape=circle,inner sep=2pt,draw,thick}]
%% nodes or vertices                                                            
\foreach \nodename/\x/\y/\direction/\navigate in {
  a/0/0/left/west, b/0/2/left/west, c/0/4/left/west, d/4/2/right/east}
{
  \node (\nodename) at (\x,\y) [nodeDecorate] {};
  \node [\direction] at (\nodename.\navigate) {\footnotesize$\nodename$};
}
%% edges or lines                                                               
\path
\foreach \startnode/\endnode in {a/d, b/d, c/d}
{
  (\startnode) edge[lineDecorate] node {} (\endnode)
}
\foreach \startnode/\endnode in {a/b, b/c, c/b, b/a}
{
  (\startnode) edge[lineDecorate,bend left] node {} (\endnode)
};
\end{tikzpicture}

A house graph:

House graph

\begin{tikzpicture}
[lineDecorate/.style={-,thick},%                                                
  nodeDecorate/.style={shape=circle,inner sep=2pt,draw,thick}]
%% nodes or vertices                                                            
\foreach \nodename/\x/\y/\direction/\navigate in {
  a/0/5/above/north, b/2/3/right/east, e/-2/3/left/west,
  c/2/0/right/east, d/-2/0/left/west}
{
  \node (\nodename) at (\x,\y) [nodeDecorate] {};
  \node [\direction] at (\nodename.\navigate) {\footnotesize$\nodename$};
}
%% edges or lines                                                               
\path
\foreach \startnode/\endnode in {a/b, b/c, b/e, c/d, d/e, e/a}
{
  (\startnode) edge[lineDecorate] node {} (\endnode)
};
\end{tikzpicture}

A weighted multigraph:
Weighted multigraph

\begin{tikzpicture}
[nodeDecorate/.style={shape=circle,inner sep=1pt,draw,thick}]
%% nodes or vertices                                                            
\foreach \nodename/\x/\y in {v_1/4/0, v_2/0/0, v_3/0/3, v_4/4/3, v_5/7/1.5}
{
  \node (\nodename) at (\x,\y) [nodeDecorate] {\scriptsize$\nodename$};
}
%% edges or lines                                                               
\tikzstyle{EdgeStyle}=[->,>=stealth,thick]
\tikzstyle{LabelStyle}=[fill=white]
\foreach \startnode/\endnode/\bend/\weight in {
  v_1/v_2/bend left/1, v_1/v_3/bend left/3, v_2/v_3/bend left/1,
  v_2/v_4/bend left/3, v_3/v_1/bend left/1, v_3/v_2/bend left=0/2,
  v_3/v_4/bend left/1, v_4/v_1/bend left=0/3, v_4/v_5/bend left/2,
  v_5/v_1/bend left=0/3, v_5/v_1/bend left/6, v_5/v_4/bend left/1}
{
  \scriptsize
  \Edge[label=$\weight$,style=\bend](\startnode)(\endnode)
}
\end{tikzpicture}

Version 0.7 of book “Algorithmic Graph Theory” released

24 February 2011 4 comments

Here is version 0.7 of the book Algorithmic Graph Theory. The relevant download options are:

Version 0.7 fleshes out the chapter “Random Graphs”. Here is the content of the chapter in brief:

  1. Network statistics
  2. Binomial random graph model
  3. Erdos-Renyi model
  4. Small-world networks
  5. Scale-free networks

Liar paradox in novel “Don Quixote”

14 February 2011 Leave a comment

While reading Cervantes’ novel Don Quixote [1], I came across the following version of the liar paradox. The quote is from Part II, Chapter 51, page 798.

Sir, a deep river divides a certain lord’s estate into two parts… Listen carefully, your worship, for the case is an important one and rather difficult. I must tell you, then, that over this river is a bridge, and at one end a gallows and a sort of courthouse, in which four judges sit to administer the law imposed by the owner of the river, the bridge and the estate. It runs like this: “Before anyone crosses this bridge, he must first state on oath where he is going and for what purpose. If he swears truly, he may be allowed to pass; but if he tells a lie, he shall suffer death by hanging on the gallows there displayed, without any hope of mercy.” Though they know the law and its rigorous conditions, many people cross the bridge and, as they clearly make true statements the judges let them pass freely. Now it happened that they once put a man on his oath, and he swore that he was going to die on the gallows there—and that was all. After due deliberation the judges pronounced as follows: “If we let this man pass freely he will have sworn a false oath and, according to the law, he must die; but he swore that he was going to die on the gallows, and if we hang him that will be the truth, so by the same law he should go free.”

[1] Cervantes. Don Quixote. Penguin Books, 1950.

Categories: humour, logic, philosophy Tags: , ,

Version 0.6 of book “Algorithmic Graph Theory” released

6 January 2011 Leave a comment

Happy new year, folks! As a new year’s gift to you, here is version 0.6 of the book Algorithmic Graph Theory. The relevant download options are:

Version 0.6 adds the new chapter “Tree Data Structures” that discusses priority queues and various efficient implementations of priority queues, including binary heaps and binomial heaps. Here is the content of the new chapter in brief:

  1. Priority queues
  2. Binary heaps
  3. Binomial heaps
  4. Binary search trees

Challenge your cryptology skills

25 December 2010 Leave a comment

In science, mathematics, and informatics there are various problem solving competitions aimed at challenging and expanding the talents of high school students. In the biological science, we have the International Biology Olympiad, in mathematics the International Mathematical Olympiad, and in informatics the International Olympiad in Informatics and the Internet Problem Solving Contest.

But cryptology is very much at the intersection of mathematics and informatics. There are some famous competitions in cryptology such as the National Institute of Standards and Technology (NIST) call in 1997 for a new encryption standard, a challenge that was met in late 2001 with the adoption of the Rijndael cipher as the Advanced Encryption Standard (AES) to replace the aging Data Encryption Standard (DES). The latest cryptology competition from NIST is a call for a new hash algorithm, called the Cryptographic Hash Algorithm Competition. As of this writing, the competition is in its third round of selection of a new hash algorithm.

The latter two competitions are oddly out of place for high school students. What comes close to a cryptology challenge for high school students is a competition I very recently learned about: the Crypto Challenge Contest. The contest is not really designed exclusively for high school students. You can find cryptology challenges suitable for high school students and up to cryptology researchers. However, many of the problems in Level I of the Crypto Challenge Contest are suitable for high school students. For those students who love a programming challenge, you might want to have a go at the problems in Level II. Happy problem solving.