Halvor Strand

Diverse

Halvor Strand — Tue, 30 Jun 2009 23:00:40 +0000

Personlig:

Facebook (Halvor Strand)
LinkedIn (Halvor Strand)
Skype (Ondkloss)
Twitter (Ondkloss)
Flickr (Ondkloss)

Teknologi:

TopCoder (Shrug)
SPOJ (Shrug)
Project Euler (Shrug)

Fritid:

Squash (NTNUI)
Trening (NTNUI)

levenshteinDistance

Halvor Strand — Fri, 13 Nov 2009 11:58:35 +0000

	public static int levenshteinDistance(String a, String b)
	{
		int[][] c = new int[a.length()+1][b.length()+1];

		for(int i = 0; i <= a.length(); i++)
			c[i][0] = i;

		for(int j = 0; j <= b.length(); j++)
			c[0][j] = j;

		for (int i = 1; i <= a.length(); i++)
            for (int j = 1; j <= b.length(); j++)
                    if (a.charAt(i-1) == b.charAt(j-1))
                    	c[i][j] = c[i-1][j-1];
                    else
                    	c[i][j] = Math.min(c[i-1][j] + 1, Math.min(c[i][j-1] + 1, c[i-1][j-1] + 1));

		return c[a.length()][b.length()];
	}

XKCD, Exploits of a Mom

Halvor Strand — Fri, 13 Nov 2009 01:37:51 +0000

XKCD

lcs

Halvor Strand — Fri, 13 Nov 2009 01:31:17 +0000

	// time: Ο(length(a)*length(b))
	// space: Θ(length(a)*length(b))
	public static int lcs(String a, String b)
	{
		int[][] c = new int[a.length()+1][b.length()+1];

		for (int i = 1; i <= a.length(); i++)
            for (int j = 1; j <= b.length(); j++)
                    if (a.charAt(i-1) == b.charAt(j-1))
                    	c[i][j] = c[i-1][j-1] + 1;
                    else
                    	c[i][j] = Math.max(c[i-1][j], c[i][j-1]);

		return c[a.length()][b.length()];
	}

gcd lcm

Halvor Strand — Sat, 24 Oct 2009 08:45:15 +0000

public static int gcd(int a, int b)
{
	if(b == 0) return a;
	return gcd(b, a%b);
}

public static int lcm(int a, int b)
{
	return Math.abs(a*b)/gcd(a,b);
}

isPowerOfTwo

Halvor Strand — Sat, 17 Oct 2009 02:30:36 +0000

public static boolean isPowerOfTwo(int x)
{
	return ((x & (x-1)) == 0);
}

primeFactorize

Halvor Strand — Sat, 17 Oct 2009 02:23:23 +0000

public static Vector primeFactorize(int x)
{
	Vector factors = new Vector();

	for(int i = 2; i <= Math.sqrt(x); i++)
	{
		while(x%i == 0)
		{
			factors.add(i);
			x /= i;
		}
	}

	if(x > 1)
		factors.add(x);

	return factors;
}

isPrime

Halvor Strand — Wed, 22 Jul 2009 19:46:01 +0000

	public static boolean isPrime(int x)
	{
		if(x < 3)
			return (x == 2);

		for(int i = 3; i <= Math.sqrt(x); i++)
			if(x % i == 0)
				return false;

		return true;
	}

XKCD, Compiling

Halvor Strand — Mon, 06 Jul 2009 11:18:23 +0000

XKCD