# Category Archives: Algorithms

## The Simpler the Better

This week’s That’s Maths in The Irish Times ( TM030 ) is about Linear Programming (LP) and about how it saves millions of Euros every day through optimising efficiency.

A Berkeley graduate student, George Dantzig, was late for class. He scribbled down two problems written on the blackboard and handed in solutions a few days later. But the problems on the board were not homework assignments; they were two famous unsolved problems in statistics. The solutions earned Dantzig his Ph.D.

View original post 440 more words

## Graph Search (Depth Search)

Depth Search is an algorithm that traverses a graph to find an item, the logic behinds this search is this, Let’s assume that the first node be A, and I am looking at the neighbour of A node and there are 3 neighbours, B,C,E are the nodes alphabeticaly in order.

The first node to be visited in this list is B, after, I am going to visit the neighbour of B’s node, and it has only one neighbour, and that is D, now the turn is D’s neighbour and that is only one, final node is G.

Then, the tour is A, B, D, G and if the item being searched has been found on this stage, then we terminate the process, if we can not find it, then we should backtrack from G to the previous node, and that is D and now I am searching D’s neighbours except G…

View original post 111 more words

## Hash Table and Magic (Relatively Primes) Numbers

Today, let’s talk about hash tables. Or, more precisely, one type of secondary probing technique, one that uses some number theory—but not quadratic residues, just relatively prime numbers.

I don’t know if you’re like me, but it often bugs me when I read something in a textbook that seems to make sense, but is claimed without proof nor demonstration (oh, I think I said that before). That seems to happen particularly often when I read stuff about data structures, and this time I decided to explore one of those claims.

View original post 1,093 more words

## z-algorithm for pattern matching

String algorithms are a traditional area of study in computer science and there is a wide variety of standard algorithms available. The more algorithms you know, the more easier it gets to work with them 🙂 As the title of the post says, we will try to explore the z-algorithm today. Lets first formulate the problem statement and a couple of definitions. To start with lets look at the below mentioned question (from interviewstreet):

QUESTION

For two strings A and B, we define the similarity of the strings to be the length of the longest prefix common to both strings. For example, the similarity of strings “abc” and “abd” is 2, while the similarity of strings “aaa” and “aaab” is 3.

Calculate the sum of similarities of a string S with each of it’s suffixes.

Sample Input:
2
ababaa
aa

Sample Output:
11
3

Explanation:
For the first…

View original post 366 more words

## XOR swap algorithm

http://en.wikipedia.org/wiki/XOR_swap_algorithm

Conventional swapping requires the use of a temporary storage variable. Using the XOR swap algorithm, however, no temporary storage is needed. The algorithm is as follows:

X := X XOR Y
Y := X XOR Y
X := X XOR Y

To understand it, think about the PLUS swap algorithm
a = a + b
b = a – b
a = a -b

interpret XOR: it is a binary PLUS operation without carry.

View original post

## Cycle Detection in Graphs

In graph theory, the term cycle may refer to a closed path. If repeated vertices are allowed, it is more often called a closed walk. If the path is a simple path, with no repeated vertices or edges other than the starting and ending vertices, it may also be called a simple cyclecircuitcircle, or polygon; see Cycle graph. A cycle in a directed graph is called a directed cycle.

The term cycle may also refer to:

• An element of the binary or integral (or real, complex, etc.) cycle space of a graph. This is the usage closest to that in the rest of mathematics, in particular algebraic topology. Such a cycle may be called a binary cycleintegral cycle, etc.
• An edge set that has even degree at every vertex; also called an even edge set or…

View original post 539 more words

## Algorithms of algorithms

Suppose that N equals 1 million. Approximately how much faster is an algorithm that performs Nlg⁡N operations versus one that performs N2 operations? Recall that lg is the base-2 logarithm function.

Ans:

N2/(Nlg⁡N)=N/lg⁡N=1,000,000/lg⁡(1,000,000). Since 220 is approximately 1 million, we obtain approximately 50,000.

View original post

## Expert Knowledge Modelling in Unreal Tournament presented in CEDI 2013

The title of the paper is “Modelling Human Expert Behaviour in an Unreal Tournament 2004 Bot”. It has presented in the Primer Simposio Español en Entretenimiento Digital (SEED 2013) track, inside CEDI 2013.

Abstract:

This paper presents a deep description of the design of an autonomous agent (bot) for playing 1 vs. 1 dead match mode in the first person shooter Unreal Tournament 2004 (UT2K4).
The bot models most of the behaviour (actions and tricks) of an expert human player in this mode, who has participated in international UT2K4 championships.
The Artificial Intelligence engine is based on two levels of states, and it relies on an auxiliary database for learning about the fighting arena. Thus, it will store weapons and items locations once the player has discovered them, as a human player could do.
This so-called expert bot yields excellent results, beating the game default bots in the hardest…

View original post 30 more words

## Hashing – a programmer prospective

As a programmer, I would say this is one of the best and most important techniques which I came across so far.

## What is hashing?

To understand this, let us look at some of the definitions from the dictionary.

• Hash (noun) – a dish of diced or chopped vegetables, a jumble
• Hash (verb) – to chop into small pieces; make into hash
• Hashing (Computers) – a technique for locating data in a file by applying a transformation, usually arithmetic, to a key

In simple words, it is a technique to transform a bigger data into a small key (word or number) and then using this key to identify that data whenever it is required. Let us take an example to understand this.

A simple example is the phone book. When we want to call a person named Sada, what exactly we do, go to phone book click on “S”…

View original post 1,453 more words

## Algorithms + Machines = Awesome Athleticism

Raffaello D’Andrea gives this demonstration of their amazing work with applying mathematics and algorithms to some quadrocopters.

It’s an amazing presentation and these guys are destined for huge things. I can’t wait to see what the future brings.

View original post