Tag Archives: algorithms

Maze

Standard

Solving mazes is a great time-pass, if you “too” have nothing to do just try to solve this maze made by me (very easy one, can be solved within few seconds)

New Doc 8_1

Very easy example of maze

Since I am writing about mazes, there must be something mathematical about them. Indeed “solving a maze” is a NP-complete problem [Non-deterministic Polynomial-time solvable problem], one of most popular class of problems in Theoretical Computer Science. But, no surprise here, since lot of puzzles like Minesweeper, sudoku etc. too are NP-complete.

Leonhard Euler was one of the first to analyze plane mazes mathematically, and in doing so made the first significant contributions to the branch of mathematics known as topology.

Mazes containing no loops are known as “standard”, or “perfect” mazes, and are equivalent to a tree in graph theory. Thus many maze solving algorithms are closely related to graph theory. Intuitively, if one pulled and stretched out the paths in the maze in the proper way, the result could be made to resemble a tree (dead ends become the leaves of the tree.).

To make my maze I used “adding walls algorithm” i.e. I laid a set of obstructions within an open area.  Can you tell whether my maze above is “perfect” one??

As it turns out, there are various maze generation as well as maze solving algorithms. A detailed discussion of these can be found at: http://www.astrolog.org/labyrnth/algrithm.htm

Also, there is an interesting article on Maze solving using image analysis: http://www.crisluengo.net/index.php/archives/277

 

 

Layman’s RSA algorithm

Standard

Why a layman should care about RSA: Your all “secure” online transactions are based on RSA encryption!

RSA stands for  the initial letters of the surnames of Ron Rivest, Adi Shamir, and Leonard Adleman, who first publicly described the algorithm of one of the first practical public-key cryptosystems which is widely used for secure data transmission. In this blog post I will try to illustrate the RSA algorithm using a puzzle (that I came across during my summer internship in Delhi):

Suppose there are two scientists, M and F (assume M to be male and F to be female for ease of writing), collaborating on a classified research. Both live far apart and F wants to send a chemical for testing to M. She designs a box with two latches for locking (see photo below), so that two different locks can be used to lock the box. [Assume that if any lock is tried to be broken, the chemical will spill and evaporate].

Two such latches are there

Two such latches are there

Now, F locks one of the latches and keeps the key with herself and sends the box to M. When M receives the box, he locks the other latch and keeps that key with himself. 

M then returns the box to F. When F receives the box, she unlocks her lock and sends the box again to M. When M again receives the box, he unlocks his  lock.

Voilà! the chemical has been securely sent by F to M and that too without exchanging the keys.

If we make the above physical “lock” an abstract entity (i.e. numbers!),  and minimize the possibility of breaking lock (like in above illustration, breaking lock caused loss of chemical), what we get is the RSA encryption.

For Mathematics behind RSA encryption refer: http://blogs.ams.org/mathgradblog/2014/03/30/rsa/#sthash.ce5YIAO6.dpbs