Determinant in Haskell

In linear algebra, the determinant is quite a useful operation that can be done on matrices. To further my understanding of Haskell, I decided to program a solver for systems of equations. One of the best ways to do this dynamically is through Cramer's Rule which needs to be able to calculate determinants. So, here's my recursive code for finding determinants:

determinant :: (Num a, Fractional a) => [[a]] -> a

determinant [[x]] = x
determinant mat =
 sum [(-1)^i*x*(determinant (getRest i mat)) | (i, x) <- zip [0..] (head mat)]

So, in this code, the base case is a 1x1 matrix. The getRest function simply returns the matrix without the head row (topmost) and without the \(i\)th column.

The code and tests are available on my github.

Creating a Sine Function in Haskell

Using Taylor Series derivation I found the following infinite sum expression for sin:
\[
  \sin \left(x \right) = \sum_{i = 1}^{\infty} \frac{x^{2 i - 1}}{\left( 2 i - 1 \right)!} \left( -1 \right)^{i - 1}
\]
The exact derivation is available as a PDF on github.

The translation of this sum into Haskell code was simple:

sin' :: (Num a, Fractional a) => a -> a
sin' x = sum [sinTerm x i | i <- [1..33]]


sinTerm :: (Num a, Fractional a) => a -> Integer -> a
sinTerm x i = (x^oddTerm / fromIntegral (factorial oddTerm))*(-1)^(i-1)
  where oddTerm = 2*i - 1

So, this code is pretty straight forward, if you wanted to get more accuracy on the results you could change "33" to be some greater value (33 says that we will sum up 33-1=32 terms of the taylor series).

Of course this code references factorial which is defined simply as:

factorial :: Integer -> Integer
factorial 1 = 1
factorial n = n * factorial (n-1)

As usual, code and tests are available on github.

Proof by Induction Example

Proof by induction is a powerful, accepted tool for producing not only mathematical proofs but also proofs of algorithms in computer science and other fields as well.

The concept of proof by induction, is generally described as being a three step process:

1. Prove a base case (in many cases we call this \(P(1)\)).
2. Assume that the \(k\)th case is true (we call this \(P(k)\)).
3. Show that the \(k+1\)th case is true (we call this \(P(k+1)\)).

As can be seen \(P(1) \rightarrow P(2)\), since our base case has been established at \( P(1)\) and we have shown that for our \( k+1\)th case, when \( k = 1\) (i.e. \(P(2)\)) our proposition stands. This can be further extended to show that \( P(2) \rightarrow P(3) \rightarrow ... \rightarrow P(n)\).

So, in less-mathematical terms, proof by induction is as simple as proving some proposition is true for some starting value, and then verifying that it is true for the next one, and the next one, continuing on as far as it needs to or, in other words, to the \(n\)th value.

The following is a simple, somewhat standard example.

Problem

\( \forall n \in \mathbb{N} \), prove that: \[ \sum_{i = 1}^{n} i = \frac{n \left( n + 1 \right)}{2} \]

(This is saying that if we sum up all the numbers from one to \(n\), that sum should equivalently be calculable by \( \frac{n \left( n + 1 \right)}{2} \))

Proof

 Before we start the proof, it's useful to...
\[
  \text{let } P(n) =  \sum_{i = 1}^{n} i
\]

Now...

Proof by Induction

Step 1: Prove base-case, \( P(1) \):

So, the sum of all number from one to one is:
\[
  P(1) = \sum_{i = 1}^{1} i = 1
\]

Now we verify that our formula works for \( n = 1\):
\[
  \frac{n \left(n + 1 \right)}{2} = \frac{1 \left(1 + 1 \right)}{2} = \frac{2}{2} = 1
\]

It checks!

Step 2: Assume that \( P(k) \) is true:

So, here we are assuming that:
\[
  P(k) = \sum_{i = 1}^{k} i = 1 + 2 + 3 + ... + k = \frac{k \left( k + 1 \right)}{2}
\]

Step 3: Show that \( P(k+1) \) is consistent:

So, \( P(k+1) \) looks like, (replacing \(n\) with \( k + 1\)):
\[
  P(k+1) =  \sum_{i = 1}^{k+1} i = 1 + 2 + 3 + ... + k + (k + 1) = \frac{\left( k + 1 \right) \left[ \left( k + 1 \right) + 1 \right]}{2}
\]

Noticing that \( 1 + 2 + 3 + ... + k \) is the same as \( P(k) \) from Step 2:
\[
  \frac{k \left( k + 1 \right)}{2} + \left( k + 1 \right) = \frac{\left( k + 1 \right) \left[ \left( k + 1 \right) + 1 \right]}{2}
\]

Multiplying both sides by \(2\):
\[
   k \left( k + 1 \right) + 2\left( k + 1 \right) = \left( k + 1 \right) \left[ \left( k + 1 \right) + 1 \right]
\]

Distribute \(k\) and \(2\) on the left, add the \(1\)s on the right:
\[
  k^2 + k + 2k + 2 = \left( k + 1 \right) \left( k + 2 \right)
\]

FOIL the right:
\[
  k^2 + k + 2k + 2 = k^2 + 2k + k + 2 \text{      $\square$}
\]

It's really as easy as that!

Simple Partial Differential Equations Example

I am really enjoying my current partial differential equations class, so I thought I'd share an example problem. Note that this is probably one of the simplest problems in partial DE.

Problem

\begin{equation}
  \text{(1)    } k^2 \frac{\partial^2 U}{\partial t^2} = \frac{\partial^2 U}{\partial x^2}
\end{equation}
\begin{equation}
  \text{(2)    } U \left( 0, t \right) = 0
\end{equation}
\begin{equation}
  \text{(3)    } U \left( L, t \right) = 0
\end{equation}
\begin{equation}
  \text{(4)    } U \left( x, 0 \right) = 0
\end{equation}
\begin{equation}
  \text{(5)    } \frac{\partial U}{\partial t} \left( x, 0 \right) = f \left( x \right)
\end{equation}

Solution

We are looking for a solution of the form:
\[
  U = XT
\]
Where \(X\) is a function of \(x\) and \(T\) is a function of \(t\).

Translating (1) to match the expected solution, we get:
\[
  k^2 XT^{\prime\prime} = X^{\prime\prime} T
\]

Dividing each side by \( XT \):
\[
  k^2 \frac{T^{\prime\prime}}{T} = \frac{X^{\prime\prime}}{X}
\]

Since we have a function of only \(T\) on the left and only \( X \) on the right, we know that these are equal to a constant.
\[
  k^2 \frac{T^{\prime\prime}}{T} = \frac{X^{\prime\prime}}{X} = constant = \left\{\begin{array}{lr}
  0 \\
  -\lambda^2 \\
  \lambda^2
\end{array}   \right.
\]

The notation above says that the constant can either be \(0\), some negative number (as forced to be negative by \( -\lambda^2 \)) or some positive number (forced by \( \lambda^2 \)).

Case \( constant = 0 \):

Finding \( X \):
\[
  \frac{X^{\prime\prime}}{X} = 0 \Rightarrow X^{\prime\prime} = 0
\]

Integrating both sides:
\[
  X^{\prime} = A
\]
Where \( A \) is an arbitrary constant.

Integrating again:
\[
  X = A x + B
\]
Where \( B \) is an arbitrary constant.

Finding \( T \):
\[
  \frac{k^2 T^{\prime\prime}}{T} = 0 \Rightarrow T^{\prime\prime} = 0
\]

Integrating both sides:
\[
  T^{\prime} = C
\]
Where \( C \) is an arbitrary constant.

Integrating again:
\[
  T = C t + D
\]
Where \( D \) is an arbitrary constant.

Since \( U = XT \):
\[
  U = \left(A x + B\right) \left( C t + D \right)
\]
Therefore, this satisfies (1).

Looking at (2), we have:
\[
  U \left( 0, t \right) = 0 \Rightarrow \left(A (0) + B\right) \left( C t + D \right) = 0 \Rightarrow B \left( C t + D \right)= 0
\]

This implies that \( B = 0 \), so:
\[
  U = A x \left( C t + D \right) = x \left( C t + D \right)
\]
satisfies (1) and (2); note that the constant \( A \) was absorbed into the other constants (since they are, after all, just arbitrary constants).

Looking at (3), we have:
\[
  U \left( L, t \right) = 0 \Rightarrow L \left( C t + D \right) = 0
\]

To make this true, we can't change the value of \( L \) because it is a constraint, so the only option is to make \( C = D = 0\).

So,
\[
  U = 0
\]
This, however, is an uninteresting solution for \( U \). So, we examine the next possible constant.

Case \( constant = -\lambda^2 \):

Finding \( X \):
\[
  \frac{X^{\prime\prime}}{X} = -\lambda^2
\]

Multiply both sides by \( X \):
\[
  X^{\prime\prime} = -\lambda^2 X
\]

Using methods from differential equations (DE), we know that we can solve this by subbing \( \alpha^2 \) in for \( X^{\prime\prime} \) and \( 1 \) in for \( X \):
\[
  \alpha^2 = -\lambda^2
\]

Taking the square root of both sides we get:
\[
  \alpha = \pm \lambda i
\]

From DE we know that this fits the form \(\alpha = b \pm c i \), where the answer the the DE is:
\[
  X = e^{bx} \left[ A \cos \left( c x \right) + B \sin \left( c x \right)\right]
\]
Where \(A\) and \(B\) are arbitrary constants.

Therefore:
\[
  X = e^{0x} \left[ A \cos \left( \lambda x \right) + B \sin \left( \lambda x \right)\right] = \left[ A \cos \left( \lambda x \right) + B \sin \left( \lambda x \right)\right]
\]

Finding \( T \):

\[
  k^2 \frac{T^{\prime\prime}}{T} = -\lambda^2
\]

Multiply both sides by \( \frac{T}{k^2} \):
\[
  T^{\prime\prime} = -\frac{\lambda^2}{k^2} T
\]

Using methods from differential equations (DE), we know that we can solve this by subbing \( \beta^2 \) in for \( T^{\prime\prime} \) and \( 1 \) in for \( T \):
\[
  \beta^2 = -\frac{\lambda^2}{k^2}
\]

Taking the square root of both sides we get:
\[
  \beta = \pm \frac{\lambda}{k} i
\]

From DE we know that this also fits the form \(\beta = b \pm c i \), where the answer the the DE is:
\[
  T = e^{bt} \left[ C \cos \left( c t \right) + D \sin \left( c t \right)\right]
\]
Where \(C\) and \(D\) are arbitrary constants (not necessarily the same as \(A\) and \( B \)).

Therefore:
\[
  T = e^{0t} \left[ C \cos \left( \frac{\lambda}{k} t \right) + D \sin \left( \frac{\lambda}{k} t \right)\right] = \left[ C \cos \left( \frac{\lambda}{k} t \right) + D \sin \left( \frac{\lambda}{k} t \right)\right]
\]

Since \( U = XT \):
\[
  U = \left[ A \cos \left( \lambda x \right) + B \sin \left( \lambda x \right)\right] \left[ C \cos \left( \frac{\lambda}{k} t \right) + D \sin \left( \frac{\lambda}{k} t \right)\right]
\]
Therefore, this satisfies (1).

Looking at (2), we have:
\[
  U \left( 0, t \right) = 0 \Rightarrow \left[ A \cos \left( 0 \right) + B \sin \left( 0 \right)\right] \left[ C \cos \left( \frac{\lambda}{k} t \right) + D \sin \left( \frac{\lambda}{k} t \right)\right] = 0
\]

\(\cos \left( 0 \right) = 1\) and \( \sin \left( 0 \right) = 0\), so,
\[
  A \left[ C \cos \left( \frac{\lambda}{k} t \right) + D \sin \left( \frac{\lambda}{k} t \right)\right] = 0
\]

This implies that \( A = 0 \), so:
\[
  U = \sin \left( \lambda x \right) \left[ C \cos \left( \frac{\lambda}{k} t \right) + D \sin \left( \frac{\lambda}{k} t \right)\right]
\]  
satisfies (1) and (2); note that the constant \( B \) was absorbed into the other constants (since they are, after all, just arbitrary constants).

Looking at (3), we have:
\[
  U \left( L, t \right) = 0 \Rightarrow \sin \left( \lambda L \right) \left[ C \cos \left( \frac{\lambda}{k} t \right) + D \sin \left( \frac{\lambda}{k} t \right)\right] = 0
\]

So, we need to pick a value for \( \lambda \) that causes the above expression to always be zero. We find that there are an infinite number of them (everywhere \( \sin \left( n \pi \right) \) where n is a natural number (better suited to match the solution than an integer). So, because of this, we find that:
\[
  \lambda = \frac{n \pi}{L},\, \forall n \in \mathbb{N}
\]

So, subbing in for \( \lambda \), we have:
\[
  U = \sin \left( \frac{n \pi x}{L} \right) \left[ C \cos \left( \frac{n \pi}{L k} t \right) + D \sin \left( \frac{n \pi}{L k} t \right)\right]
\]
Which satisfies (1), (2) and (3).

Looking at (4), we have:
\[
  U \left( x, 0 \right) = 0 \Rightarrow \sin \left( \frac{n \pi x}{L} \right) \left[ C \cos \left( 0 \right) + D \sin \left( 0 \right)\right] = 0
\]

\(\cos \left( 0 \right) = 1\) and \( \sin \left( 0 \right) = 0\), so,
\[
    U \left( x, 0 \right) = 0 \Rightarrow \sin \left( \frac{n \pi x}{L} \right) \left( C \right) = 0
\]

This implies that \( C = 0\), so,
\[
  U = \sin \left( \frac{n \pi x}{L} \right) \left( D \right) \sin \left( \frac{n \pi}{L k} t \right)
\]
Satisfies (1), (2), (3) and (4).

Since constraint (5) is non-zero, I will evaluate it lastly. For now, I claim that:
\[
  U = \sum_{n = 1}^{\infty} D_n \sin \left( \frac{n \pi x}{L} \right) \sin \left( \frac{n \pi}{L k} t \right)
\]
\( \forall n \in \mathbb{N}\), also satisfies (1), (2), (3), and (4). This claim is justified because, as show above, constraint (3) is satisfied for all values of \( n \). So, for whatever \( n \) I pick from the natural numbers (\( 1,2,3...\), \(\mathbb{N}\)) the resulting \( U \) will also be an answer. So, summing together the infinite answers for \( U \) still meets the problem's criteria. \( D \) became \( D_n \) because \( D \) is not necessarily the same thing for any \( n \) value.

So, considering constraint (5), we need to first find \( \frac{\partial U}{\partial t}\):
\[
  \frac{\partial U}{\partial t} = \sum_{n = 1}^{\infty} D_n \sin \left( \frac{n \pi x}{L} \right) \left( \frac{n \pi}{L k} \right) \cos \left( \frac{n \pi}{L k} t \right)
\]

Looking at the actual constraint, (5):
\[
  \frac{\partial U}{\partial t} \left( x, 0 \right) = f \left( x \right) \Rightarrow \sum_{n = 1}^{\infty} D_n \sin \left( \frac{n \pi x}{L} \right) \left( \frac{n \pi}{L k} \right) \cos \left( 0 \right) = f \left( x \right)
\]

Since, \( \cos \left( 0 \right) = 1\):
\[
  f \left( x \right) = \sum_{n = 1}^{\infty} D_n \sin \left( \frac{n \pi x}{L} \right) \left( \frac{n \pi}{L k} \right)
\]

By the Fourier sine series, we know that the coefficients are given by:
\[
  D_n \left( \frac{n \pi}{L k} \right) = \frac{2}{L} \int_0^L f \left( x \right) \sin \left( \frac{n \pi x}{L} \right) dx
\]
We include \( \left( \frac{n \pi}{L k} \right) \) because it does not match the Fourier series and needs to be divided out.

Solving for the actual coefficients:
\[
  D_n = \frac{2 k}{n \pi} \int_0^L f \left( x \right) \sin \left( \frac{n \pi x}{L} \right) dx
\]

Where our final \( U \) is, as above:
\[
  U = \sum_{n = 1}^{\infty} D_n \sin \left( \frac{n \pi x}{L} \right) \sin \left( \frac{n \pi}{L k} t \right)
\]

Now, we could go on to examine the \( constant = \lambda^2 \) case. However, it ends up just being \( 0 \) (and is therefore redundant). You can use methods like those above to come to this conclusion for yourself.

Nieve Prime Finder in Haskell

To solve a cyber-dojo challenge (implement a function/method that returns the prime factors of a number) I decided to implement a somewhat nieve (but workable) isPrime function in Haskell. Here's the code:

-- Public type-definition
isPrime :: Integer -> Bool

-- Private type-definition
lookForPrimeFrom :: Integer -> Integer -> Bool

isPrime 2 = True
isPrime n
 | n < 2     = False
 | even n    = False
 | otherwise = lookForPrimeFrom n 5

lookForPrimeFrom n i
 | ceiling (sqrt (fromIntegral n))+1 < i   = True
 | (n `mod` i) == 0                        = False
 | otherwise                               = lookForPrimeFrom n (i+2)


This code (to me at least) seems very self-documenting. The more I'm playing around with Haskell, the more I'm enjoying it and seeing its strength as a functional language. I think if I were to map this algorithm into more mathematical notation it would look like:

\[
  \forall n \in \mathbb{N}
\]
\[
  p \left( n \right) = \left\{ \begin{array}{lr}
  0, & n = 1 \\
  1, & n = 2 \\
  0, & \text{$n$ is even} \\
  1, & \nexists m \in \left\{ x \in \mathbb{N} \, | \, 5 \leq x \leq{\sqrt{n}}, \text{$x$ is odd}  \right\}
  
\end{array} \right.
\]

As you can see, this is somewhat nieve; however, the Haskell code really is quite similar to the mathematical notation.

Communication between Python and Ruby Using Sockets

Sockets are a neat and (relatively) simple means of communication between different programs in a client-server relationship. They can also be used when it is necessary to communicate data between languages and speed is not a large issue.

The following code examples are a Python lyric server that I built and a Ruby client. Their full code is available on my github account.

simple_lyric_server.py (some implementation details hidden, see github for more):

import socket

 class LyricServer(object):
    def __init__(self):
        # Details hidden... See github

    def try_get_lyrics(self):
        # Details hidden... See github

    def define_socket(self, port, n_requests=5):
        """
            Used to define the socket object from inputs
        """
        host = socket.gethostname()
        print "Lyric Thief Server: Hostname is %s" % str(host)
        self._socket.bind((host, port))
        self._n_requests = n_requests

    def handle_lyric_requests(self):
        self._socket.listen(self._n_requests)

        while True:
            client, address = self._socket.accept()
            print "Lyric Thief Server: Connected to %s" % str(address)

            self.lyrics = ''
            data = json.loads(client.recv(1024))
            try:
                self.artist, self.song = data['artist'], data['song']
            except KeyError:
                client.send("Invalid JSON passed")
                print "Lyric Thief Server: Invalid JSON Passed"
                client.close()
                return

            self.try_get_lyrics()

            # Try sending the lyrics line-by line

            for line in self.lyrics.split('\n'):
                client.send(line+'\n')

            print "Lyric Thief Server: Sent Lyrics, Closing Connection"
            client.close()

 
if __name__ == '__main__':
    server = LyricServer()
    server.define_socket(915, 5)
    server.handle_lyric_requests() 


So, quickly walking through what the methods do:

• define_socket(self, port, n_requests=5) uses the properties attached to a socket object to construct the server's socket, where port is the port that the server will run on and n_requests specifies the maximum number of requests that the server can handle at once.
• handle_lyric_request(self) tries to lookup (online) the lyrics of the song/artist pair JSON data that is passed in from a client and then send back an appropriate response.

Now looking at ruby_client.rb: 

require 'socket'

host = Socket.gethostname
port = 915

s = TCPSocket.new host, port
s.puts('{ "artist" : "Counting Crows", "song" : "Omaha"}')
lyrics = ""

begin
  while line = s.gets
    lyrics += line
  end
rescue
end 
s.close 

So, this Ruby client is much simpler. Essentially all it's doing is (1) building a new TCPSocket using the host machine and the same port as specified in the Python server, (2) writing a JSON object to the port (a request for the "Counting Crows" song "Omaha"), then it (3) reads in the lyrics and closes the connection.

JavaScript in Rails 3.2

After struggling to get CoffeeScript running correctly in my current Rails app, I decided to try using plain-ol' JavaScript and everything worked like a charm. CoffeeScript is very cool (don't get me wrong), however, setting it up is a painful and poorly documented process that proved (in my case) to be fruitless. Anyhow, I though it might be helpful to document how simple it is to get normal JavaScript working on a Rails app.

Firstly, enter the following line in the view that needs JavaScript code:
    <%= javascript_include_tag "my_js_file" %>

This line ensures that my_js_file.js is included in the current view (note that in the "include tag" the ".js" is omitted).

Secondly,  simply code/add your JavaScript file to /app/assets/javascripts/. It will now be available in your view!

I am somewhat conflicted as to how valuable this modus operandi is (there are a few good articles arguing about the benefits of using CoffeeScript); however, at the current moment it is the best solution I have found. If you know any tips about linking CoffeeScript to Rails, please comment below!

Defining Custom Commands in LaTeX

\( \LaTeX \) is a very powerful typesetting system. Its power is greatly augmented by the fact that it allows you to define your own commands. In general, a custom command will be placed in your document's preamble (meaning before \begin{document}) and will follow the form:

\newcommand{\command_name}[number_of_arguments]{command_definition}

If your command has no arguments, then you exclude the [number_of_arguments] section. In the {command_definition} section you refer to passed arguments by using  #n where n is the number of the argument you are passing. To pass down multiple arguments, you simply tack on new curly braces for each one. Here are some examples:

Example 1: Automate left and right parenthesis

 

Definition

 

\newcommand{\p}[1]{\left( #1 \right)}

In Use

\p{ 5.0 \times 10^3 } + \p{ 2.1 \times 10^{18} }

Output

 

\( \left( 5.0 \times 10^3 \right) + \left( 2.1 \times 10^{18} \right)\)

---

Example 2: Define Kilohms

 

Definition

\newcommand{\ko}{k \Omega}

In Use

R = 50 \ko

Output

 

\( R = 50 k \Omega \)

---

Example 3: Pythagorean's Hypotenuse

 

Definition

\newcommand{\hyp}[2]{ \sqrt{ #1^2 + #2^2 } }

In Use

\hyp{500}{12}

Output

 

\( \sqrt{ 500^2 + 12^2 }\)

Write ISO Files to USB from Linux Command Line

Here's a command that I use too often not to post about it:

dd if=my_iso_file.iso of=/dev/sdx

This little gem is pretty straight-forward. It uses dd (properly termed "Disk Destroyer") to write your ISO file, block by block, to your USB drive. Of course you have to replace the "x" in "sdx" to whatever your drive letter is.

To discover your drive letter, as a root user (or using sudo), type:

fdisk -l

Which will list the available, block-type partitions on your system. You should be able to conclude (usually from the size of the device) exactly what your USB drive's mount point is named (this will usually just be "sdb"). Be sure not to overwrite your hard-drive!

Once you have written the ISO file, you should run the following to clean the systems writing buffers:

sync

Deploying Aspen Projects with Heroku

Aspen is a very cool and intuitive web framework and server for building Python-powered sites. It is one of those genuine, non-MVC, "what you see is what you get" kinda things.

Heroku is a free (for basic usage) web hosting site.

For my school's math club, we needed something simple and free to post a fund-raising app and I decided that putting up an Aspen site on Heroku would be a good idea. Now that the site's up and I have ironed out those gory details, I am very happy with the results. Here are some of those details:

• To use Heroku and Python in conjunction you need python-virtualenv. So make sure you get it online or run a pip install virtualenv, or a apt-get install python-virtualenv.
• After you create a site using Heroku, you will have to link up git and login to Heroku (this is described on Heroku's site). Next be sure to start up your Python virtualenv. 
• When you're in the virtualenv, run pip install aspen.
• Next, run pip freeze > requirements.txt, which will tell Heroku what Python dependencies are needed server-side.
• Alright, this is the tricky part. You now need to create a file called ProcFile in your Heroku project's root directory. This file's contents should be:
  
       web: aspen -p . -w www -a :$PORT

That line tells Heroku to make the ProcFile's directory the project's root directory and to run Aspen over whatever port Heroku chooses. You now need to make a directory called "www" which will contain all your code files. Of course, you can call this directory whatever you want, you just need to change the contents of the ProcFile (the above line) to match.

Given a successful linking of git and Heroku, and that you are logged into Heroku, you can run git push heroku master which sends your Aspen pages to the web, and foreman start which lets you test your app locally.

 

Adding MathJax to Blogger

What is MathJax?

MathJax is a cool JavaScript program that allows bloggers and other people who edit websites to enter math typesetting text (like \( \LaTeX \)) onto their site. So, if used properly it can make equations and other mathematical formula look cool. Meaning...

Instead of this:

E = mc^2

You get this:
\[
  E = mc^2
\]

Adding MathJax to Blogger

• Navigate to the main Blogger page for your blog and click on the "Template" tab, as highlighted below:

  

• Next, click on the "Edit HTML" button below the little thumbnail of your blog:

• Once the editing window comes up (this should contain raw HTML code), hit Ctrl+F, and then type "</script>" (without the quotations).
• Now, in the editing window you should see the "</script>" text highlighted. Paste the following line of HTML code directly below the "</script>" tag:

<script src='http://cdn.mathjax.org/mathjax/latest/MathJax.js?config=TeX-AMS-MML_HTMLorMML' type='text/javascript'/>

• Here's what mine looked like after I pasted the code:

  

•  If your configuration looks right, then save the template. You should now be able to use math formatting languages in your blog, hurray!

Latest Project: Ultimate Dev. Machine Script

The latest thing I have been working on is pretty cool. It's simply a Python script called udm.py that you toss onto a virtual machine (Debian based) and run using:

sudo ./udm.py

Then, it works its magic and installs compilers, interpreters, IDEs, editors, documentation generators, source control software, and much more! So far, it has been successfully tested on Linux Mint 14.1. Here's a brief view of it:

As it stands, it is very configurable. You can add and remove packages, and even include special installation instructions all with plug-and-play-like ease. Packages are organized by topic, in simple, struct-like objects I call containers. In the udm_script/desired_packages.py script, entire containers can be added or removed from the installation. In the containers, specific packages can be added or removed. If you know of any interesting development packages that I should add, let me know!

All code is available on my github account.

Calculating Standard Deviation

Whenever calculations are made from observed data using some relation there will be an error in these calculations which is known as standard deviation. Now, exactly what this error is varies between the relationship used and the actual data obtained.


The standard deviation is usually represented by the \( \sigma_A \) (sigma) Greek letter, where \( A \) is the thing whose error we are finding. For example, if we calculated some value for gravity (let's call it \( g \)) the standard deviation of the calculated gravity would be represented as \( \sigma_g\). Pretty straight forward, huh?

Equations

Let's first talk about some general equations. For simplicity, let's call our calculated value \( Z \).

If \( Z \) is represented as a sum or difference of terms, \( Z = A_1 + A_2 + ... + A_n\), then \( \sigma_Z = \sqrt{ \sigma_{A_1}^2 + \sigma_{A_2}^2 + ... + \sigma_{A_n}^2 } \).

For example:
\[
  Z = A + B - C \Rightarrow \sigma_Z = \sqrt{ \sigma_A^2 + \sigma_B^2 + \sigma_C^2 }
\]

If \( Z \) is represented as a product or quotient of terms, \( Z = \frac{ A_1 \times A_2 \times ... \times A_n }{ B_1 \times B_2 \times ... \times B_n } \), then its relative standard deviation is given by \( \frac{\sigma_Z}{ Z } = \sqrt{ \left( \frac{\sigma_{A_1}}{A_1} \right)^2 + ... + \left( \frac{\sigma_{A_n}}{A_n} \right)^2 + \left( \frac{\sigma_{B_1}}{B_1} \right)^2 + ... + \left( \frac{\sigma_{B_n}}{B_n} \right)^2} \). Relative standard deviation is just the standard deviation over the calculated value itself. Ergo to get just the standard deviation we just multiply the whole thing by our calculated value.

For example:
\[
  Z = \frac{ A B }{ C } \Rightarrow \sigma_Z = Z \sqrt{ \left( \frac{\sigma_{A}}{A} \right)^2 + \left( \frac{\sigma_{B}}{B} \right)^2 + \left( \frac{\sigma_{C}}{C} \right)^2 }
\]
 If \( Z \) is represented as another variable to a power, \( Z = A^n \), then its relative standard deviation is given by \( \frac{ \sigma_Z }{ Z } = n \frac{ \sigma_A }{ A } \). Like before, to get \( \sigma_Z \), we just multiply by our calculated \( Z \).

For example:
\[
  Z = A^7 \Rightarrow \sigma_Z = 7 Z \frac{ \sigma_A }{ A }

\]


Those are the basic equations that you need to find the standard deviation. For more on techniques, see the following example.

Example

Suppose we want to find the standard deviation of a calculated value, let's call it \( Z\), where:
\[
  Z = A + \frac{ B^2 C}{D}

\]
To make things easier, let \( U = \frac{ B^2 C }{ D } \) and also let \( V = B^2 \). So,
\[
  Z = A + U \Rightarrow \sigma_Z = \sqrt{ \sigma_A^2 + \sigma_U^2 }

\]
So, we need to find \( \sigma_U \), and since \( V = B^2 \),
\[
  U =  \frac{ V C }{ D } \Rightarrow \sigma_U = U \sqrt{ \left( \frac{ \sigma_V }{ V } \right)^2 + \left( \frac{ \sigma_C }{ C } \right)^2 + \left( \frac{ \sigma_D }{ D } \right)^2}

\]
Lastly, we need to find \( \frac{ \sigma_V }{ V } \),
\[
  V = B^2 \Rightarrow \frac { \sigma_V }{ V } = 2 \frac{ \sigma_B }{ B }

\]
Subbing \( 2 \frac{ \sigma_B }{ B } \) in for \( \frac{ \sigma_V }{ V } \), and \(  \frac{B^2 C}{ D } \) for \( U \) we get,
\[
 U =  \frac{ V C }{ D } \Rightarrow \sigma_U = \frac{B^2 C}{ D } \sqrt{ \left( 2 \frac{ \sigma_B }{ B } \right)^2 + \left( \frac{ \sigma_C }{ C } \right)^2 + \left( \frac{ \sigma_D }{ D } \right)^2}
\]
Finally, subbing this new \( \sigma_U \) into the equation for \( \sigma_Z \), we get,
\[
   \sigma_Z = \sqrt{ \sigma_A^2 + \left( \frac{B^2 C}{ D } \sqrt{ \left( 2 \frac{ \sigma_B }{ B } \right)^2 + \left( \frac{ \sigma_C }{ C } \right)^2 + \left( \frac{ \sigma_D }{ D } \right)^2}  \right)^2 }
\]
Which can be more simply written as,
\[
    \sigma_Z = \sqrt{ \sigma_A^2 + \left( \frac{B^2 C}{ D } \right)^2 \left[ \left( 2 \frac{ \sigma_B }{ B } \right)^2 + \left( \frac{ \sigma_C }{ C } \right)^2 + \left( \frac{ \sigma_D }{ D } \right)^2 \right] }
\]

OpenSUSE 12.2 "Mantis" Review

 

I really like OpenSUSE. It's truly its own thing, in a world of Redhat and Debian derivatives. It's important to note that when I tried it out I used GNOME 3; I will try not to let that taint my review of this distro.

What I liked

• Many options for the windowing system (meaning anything but GNOME 3).
• Installation was easy.
• Came with the LibreOffice suite (per opt-in) and some other useful programs.
• The default partitioning scheme makes a partition for /home. This can be great if the OpenSUSE partition crashes and it needs to be re-installed without wiping personal files.
• Unlike the Debian derivatives I am accustomed to, it actually had a recently updated copy of VIM!
•  I think that having root access is a plus (feel free to disagree).

 Didn't Like

• DISCLAIMER: This really could just be a GNOME 3 complaint: Although there are 6 workspaces, they are linear. Unless there is some hotkey that I don't know about, this means that you have to swipe through as many as 5 workspaces to get to the one you're looking for. Plus, because they are in a linear stack, unless your WOI (workspace of interest) is on the top or bottom, it loses some association points (it's hard to tell the PB from the J sometimes).
• Doesn't come with the YUM package manager. Without it, getting some programs can be much more difficult.

 Surprises

• By default, includes the mono C# compiler! I really was not expecting this.

Conclusion

Score: 8/10

As I said earlier, I dig me some OpenSUSE. It's unique, it's helpful -- I have no major complaints. If I made one suggestion it would be to use something other than GNOME as your desktop system.

Information

Distro Name:	OpenSUSE 12.2 "Mantis"
Kernel:	3.4.6-2.10-default
Size After Install:	4.0 GB
Desktop Flavors Available:	GNOME, KDE, XFCD, LXDE, Minimal X Window, Textual
Package Managers:	Aptitude, Yast, RPM, Zypper
Languages/Compliers:	Perl, C#, Python, BASH
Web Broswer(s):	Firefox
Root Access:	True
Has sudo:	True

Latest Project: Email Miner

Just to add to my collection of "data miners" built in Python, I made a (very bare-bones) email miner. Basically all it does is strip emails out of a given URL and save them in some output file. Here's what it looks like (again, forgive my strange windowing system):

So, as you can see it's pretty straightforward. I used a little bit of polymorphism-type classes to make the output formats. Basically, all that needs to happen to add more is the definition of a derived class, the implementation of a writer method and then the new class's name needs to be added to a dictionary of other writer class-names and it's good to go! I love this Python thing...

All code is on my github.

Haskell DSA: Quick Sort

Haskell continues to astound me! I have never implemented the quicksort as simply and, frankly, elegantly as this:

quickSort :: (Ord a) => [a] -> [a]

quickSort [] = []
quickSort (x:xs) = quickSort lesser ++ [x] ++ quickSort greater
 where lesser = [e | e <- xs, e < x]
       greater = [e | e <- xs, e >= x]

Here's a quick, line-by-line for anyone who's interested.

• quickSort :: (Ord a) => [a] -> [a]
  The optional (gotta love that word in programming) function definition. It basically says that quickSort is a function that takes a list of objects, [a] and returns another list of a. Ord a means that a is ordinal, or, as far as we're concerned, sortable
• quickSort [] = []
  The first pattern we're trying to match -- if we're given an empty list, return an empty list!
• quickSort (x:xs) = quickSort lesser ++ [x] ++ quickSort greater
  This line does a few cool things: (1) split up a passed list into a first element and remainder, then (2) return the lower ordered elements and the higher sorted on either sides of the first element!
• where less = [e | e <- xs, e < x]
      greater = [e | e <- xs, e >= x]
  This where clause uses list comprehensions to build and define the lists of lower and higher ordered values. Note that the higher values are also (if the case may be) equal to the head of the list (also know as the pivot).

Heap (Max) in Python

Lately I've been practicing my data structures and algorithms and I came up with this interesting implementation for a max heap:

class Heap(object):
    """ A max heap, parents have two or less equal or smaller children """
    def __init__(self):
        """ Set the count to 0 and it has no root node """
        self.count = 0
        self.root = None

    def heapify(self, iterable):
        """ loops elements in the iterable and adds them to the heap """
        for elem in iterable:
            self.add_item(elem)

    def add_item(self, ordinal):
        """ Adds an ordinal item using priority """
        self.count += 1
        if self.count == 1:
            self.root = Node(ordinal)
            return

        i = self.count
        current_node = self.root
        new_node = Node(ordinal)

        while i != 1:
            if current_node.data < new_node.data:
                current_node.data, new_node.data = new_node.data, current_node.data
            if i%2 == 0:
                if current_node.left:
                    current_node = current_node.left
                else:
                    current_node.left = new_node
            else:
                if current_node.right:
                    current_node = current_node.right
                else:
                    current_node.right = new_node
            i /= 2

class Node(object):
    """ Used to traverse the heap """
    def __init__(self, ordinal):
        """ Require data, make the pointers empty (to None) """
        self.data = ordinal
        self.left = None
        self.right = None 

This design of a heap is pretty interesting because it uses the binary representation of Heap.count (the number of elements in the heap) to determine where the next node should go. The algorithm for this is pretty straight forward:

Increment the `count` by 1         // We're adding a new item 
`i` is `count`
`current node` is `root node`

Check 1: if `new node's value` > `current node's value`,
             then swap(`new node's value`, `current node's value`)

Check 2: if binary(`i`) ends in 0, // AKA is even, (i%2 == 0),
             then `current node` is `current node's left`
         otherwise `current node` is `current node's right`

Check 3: if `current node` is null
             then `current node` is `new node`
         otherwise `i` /= 2 and goto Check 1

The end result is a balanced heap! I also added a __str__ method to the Node class for testing:

    def __str__(self):
        return "[%s <- %s -> %s]" % \
                 (str(self.left) if self.left != None \
                                 else 'END', str(self.data), \
                  str(self.right) if self.right != None \
                                 else 'END')

One Line Fizz Buzz Test in Python

Here it is (in all its ugliness):

print '\n'.join("Fizz"*(i%3==0)+"Buzz"*(i%5==0) or str(i) for i in range(1,101))

Python is pretty astounding. This little bugger was easy to code, it is somewhat readable, and it is even understandable. Pretty cool, eh?

Short explanation:

• '\n'.join(...)
  Every item generated in the join function will be on its own line
• for i in range(1,101)
  Loop from 1 to 101, giving i the value of each
• "Fizz"*(i%3==0)+"Buzz"*(i%5==0) or str(i)
  If i is divisible by 3 then keep "Fizz", do the same for "Buzz" with 5. Add the kept values together. Or it will simply output i as a string if it fails to get "Fizz" or "Buzz"