Page Rank Algorithm

Google uses Page Rank Algorithm (PRA) to rank web pages so that finding needle in web's haystack can be accomplished. Here is a good tutorial that explains how it finds our pages in the web.

How Google Finds Your Needle in the Web's Haystack

Fun with mathematics II

We can do multiplication by means of visual ways. I have found both video and article that shows how one can compute the multiplication of ANY DIGIT NUMBERS using visual method.

A. Video
I am hundred percent sure that you will enjoy this video. Watch it first and then we discuss the principle behind this approach.

B. Article

Note: I have copied the following paragraphs and a picture from [1]. If you don't understand here, please go to that site.

Example: Multiply 22 by 13.

Note: This figure is taken from [1]

Draw 2 lines slanted upward to the right, and then move downward to the right a short distance and draw another 2 lines upward to the right (see the magenta lines in Figure 1). Then draw 1 line slanted downward to the right, and then move upward to the right a short distance and draw another 3 lines slanted downward to the right (the cyan lines in Figure 1).

Now count up the number of intersection points in each corner of the figure. The number of intersection points at left (green-shaded region) will be the first digit of the answer. Sum the number of intersection points at the top and bottom of the square (in the blue-shaded region); this will be the middle digit of the answer. The number of intersection points at right (in the yellow-shaded region) will be the last digit of the answer.

This will work to multiply any two two-digit numbers, but if any of the green, blue, gold sums have 10 or more points in them, be sure to carry the tens digit to the left, just as you would if you were adding.

C. Understanding the LOGIC
Below, I've described the way we did the multiplication in our school and if you have noticed, the same thing is happening in the visual method as well. Here it goes:

Ex1
   2 2
x 1 3
-------
   6  6
2 2  x
-------------
2 8 6

Ex2:
1 5 6
3 5 8
---------------------------------------
           8    40   48
     5  25    30   x x
 3 15 18    xx    x x
-------------------------
 5   5  8      4     8 [ while adding , carry should be propagated towards left ]

We know that two non parallel lines always meet exactly at a point. Note that when a number of lines (representing one digit number, e.g. five lines for 5 ) crosses  a number of other lines ( which represents another one digit number), then the number of  points formed by the crossings is equal to their product.

I understood the logic by referring back to my ways of doing the calculation. It may not be clear to you by my explanation. Better visit the website and read the article in such a case.

References:

1. Su, Francis E., et al. "Squaring Quickly." Mudd Math Fun Facts. 

Lexical Similarity Measure

My last post described the Levenshtein's algorithm for finding the differences between two sequences which does so by means of "edit distance" metric.  Recently, I read an algorithm that utilizes the same metric to calculate the lexical similarity measure between two strings Li and Lj:

SM(Li, Lj ) := max(0 , (min( |Li|, |Lj| ) - ed(Li,Lj) ) / min(|Li|, |Lj|))

where

|Li| and |Lj| are the lengths of  Li and Lj ,
ed(Li, Lj) is the edit distance between Li and Lj

This method can be applied for comparing two set of strings as well. Details can be found in the paper: A. Maedche and S. Staab, "Measuring Similarity between Ontologies", Karlsruhe, Germany.