Monthly Archives: September 2013
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.
Thoughts on Big Data and Visualization – 1
Big data does not have a fixed definition, but it only means BIG data. I’m not trying to be funny. I meant to say it out loud: “bb-iii-ee-gg” data. The enormous amount of data could mean Terrabytes, Petabytes and nowadays I read papers about moving on to Exabytes. This will be a series of posts that set aside the technicalities (mostly) and describe my perspective on the current progress, and also what experts in the field say about the prospective outlook.
This is a hot topic nowadays among the journalists since it has found its use beyond the borders of science, but the research thrust has been there for more than two decades, dating back to the early days of scientific data analysis and visualization. There are doubts on the capabilities of this field, I met a few Data professors and experts who cast doubt on the current hype, I…
View original post 1,062 more words
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.
Worst case upper bounds is wrong metric to compare algorithms
Prof. Robert Sedgewick Princeton University talks about pit falls of using worst case BigO to compare algorithms
Khuram Ali 