Algorithm optimization notes

Today I was working on optimizing an alpha-beta gaming algorithm, and I found a few things along the way:

• Object creation can be time consuming and dragging down your algorithm performance. So, think twice when object creation can be avoided.
• When you are implementing an algorithm, the first thing is to make it work correctly, the second thing is to spot the heavy-weight routine or code sections that requires dense computation.
• Think twice about the use of data structure. Often times it is the wrong data structure you use that slows down the program execution.

Played with python module

while I was solving problems in Project Euler. I also implemented an elegant algorithm to find prime numbers - Sieve of Eratosthenes. Kind of fun.

Prime factoring problem

The prime factors of 13195 are 5, 7, 13 and 29. What is the largest prime factor of the number 600851475143 ?

An intriguing programming problem

http://tinyurl.com/3a3xebj

This problem is from Euler Project (http://projecteuler.net/) problem 67. How would you write an efficient program to solve it?

I will post my solution once I solve it.

A google interview question

http://batiste.dosimple.ch/blog/2008-04-25-1/

Take a look and review about it. It also appeared in my past homework assignment. What a great school training.

B-Tree

Or some variants of B-tree: B+ - tree.

http://en.wikipedia.org/wiki/B-tree

It is particularly useful for database systems or file systems. The purpose of using B-trees is it can minimize the frequency of disk accesses. Apple's HFS+ and Microsoft's NTFS filesystem use B-trees.

Floyd-Warshall Algorithm

A powerful algorithm to compute all-pairs shortest path.

The Math background of this problem is related to Relations. Specifically, it is related to transitive closure problem. Floyd-Warshall algorithm can be used to compute the transitive closure of a graph efficiently (O(n^3)).

In addition, Floyd-Warshall algorithm is very easy to implement.