Category Archives: Algorithms
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.
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 cycle, circuit, circle, 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 cycle, integral 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
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.
Khuram Ali 