Archive for category Algorithms
Math behind a world sunlight map
Posted by Jurgen in Algorithms, Image processing, Simulation on May 14th, 2009
My neighbour has a map of the world on the wall. You can see it from the street in front of his house. It has a backlight but that only illuminates half of the map. The transition from day to night is shaped like a sine wave most of the time. It actually is a physical world sunlight map. Of course, you can simulate this with a computer too. There even is an instance using Google maps.
As many roads lead to Rome multiple ways are possible to this simulation. One could model the sun, earth, maybe more and start ray tracing. This approach would include solar eclipses but is quite heavy by means of the load on the processor. Because of the number of calculations involved in ray tracing is quite high. The way I choose to describe fully in this article is one close to it. Using vectors pointing from a sphere (earth) to a point (sun) I map a Mercator projected map of the world on the sphere. The challenges included are the yearly orbit of earth around the sun and it’s 23.5° tilted 24 hour spin. Read the rest of this entry »
Textual difference detector
Posted by Jurgen in Algorithms, Text processing on May 7th, 2009
Today I uploaded my textual difference detector to the eDesign examples. This is an example application demonstrating the theory of applying the Levenshtein algorithm to detect differences between two versions of the same text. Also, the ‘Find the differences‘ post is updated with a link to this example.
This example takes two texts as input and outputs one merged text marked with what was deleted and what was added. Take a look and feel free to download the source code. This also inlcludes the Levenshtein algorithm source code.
Challenge Hash
Posted by Jurgen in Algorithms, Security on May 5th, 2009
The Internet is a crowd and everybody in it can potentially hear what you say. Methods have been developed to prevent this and ensure identity, integrity and authenticity. Often these three can be seen as properties of encryption. Encryption implies the possibility of decryption. Passwords are precious things you don’t want others to decrypt and read. With a technique called challenge hashing you don’t need to have any worries about it. Challenge hashing is a technique used to verify a password on site B which was sent from site A without sending the password in plain text. This article covers how. Read the rest of this entry »
Sudoku Logic – part I
Posted by Jurgen in Algorithms on May 1st, 2009
If you haven’t heard of Sudoku puzzles (数独, sūdoku) you’ve either been sleeping under a rock or been space traveling for quite a while. These 9×9 square puzzles originating from around 1900 became an international hit in 2005. Sudokus appear in newspapers, online and special sudoku puzzle books all-over-the-world. And as if that is not yet enough Sudoku TV shows and all kinds of variants of the puzzle are made. One can solve a sudoku using logic only. Because of this computational algorithms to solve every possible Sudoku must exist. This is part one in the series on such algorithms. Read the rest of this entry »
Find the differences
Posted by Jurgen in Algorithms, Text processing on April 12th, 2009
Comparing files is something developers do every once in a while. For example, comparing configuration files to see what is different in the other environment or compare programming files to see what has changed in the source code. Implementations of text comparison algorithms are therefore widespread and used in several fields. For instance, in blogs and content managements systems, one might need to know what was altered in an update of a text (in cms like systems) or a programmer in a team would like to see what changed in the source code (svn). Also a lot of (combined) search, spell checking, speech recognition and plagiarism detection software compare texts (strings) in a certain way. This article covers the Levenshtein distance algorithm and how to use it to indicate alterations to texts. Read the rest of this entry »