Finding Document Similarity

If you need to find how similar a document is we can use vector algebra to our advantage. If we have 2 document d1 and d2 then

Let D1 be a vector of the word-frequency of the document d1
Let D2 be a vector of the word-frequency of the document d2

then the deviation of the 2 documents can be calculated by

using the fact that

cos(theta) = (D1 * D2)/(N(D1) * N(D2))

where N(D) is the normalized vector represented by

N(D) = sqrt(D * D)

Looking back at mergesort

For mergesort the recurrence relation is

T(N) = 1 if N == 1
T(N) = cn + 2T(N/2) if N != 1

so if we draw the recursion tree for such a recurrence relation we get
Height of tree = lg N
Number of leaves = N
--------------
Leaves at level 0 -> 1
Leaves at level 1 -> 2
Leaves at level 2 -> 4
Leaves at level 3 -> 8
...
Leaves at level lg N -> N

Total Work Done
----------------
Work done at level 0 -> cn
Work done at level 1 -> cn
Work done at level 2 -> cn
....
Work done at level lg N -> cn

So total work done => cn * lg N => O(n lg n)

Similarity between objects

Lets say we need to find the similarity between people based on how they rank different items. Based on the that collected data we need to recommend some new
items to the users.People who are similar to each other have a higher likelihood of
liking things that we recommend them.

Now lets consider a Set of Users.A Set of Items and a set of Rankings which users give to these Items.

Given this information how can we find the similarity between 2 Users.

Approach 1)
------------
Take user A and user B
Calculate union of items chosen by user A & B , call it A_UNION_B
Calculate the intersection of the items chosen between A & b, call it A_INT_B
then the value A_INT_B/A_UNION_B represents the similarity of the 2 users A and B

Approach 2)
------------
For every item that is common between A & B we can calculate the Euclidean distance between the rankings of the 2 items.
D = RA (ranking A gave to an item) - RB (ranking B gave to an item)
Sum = Sum + D^2

The once we have the sum we can call it Similarity Sum and use a formula
like

Similarity = 1/(1 + Sum)

The 1 is added to prevent the 1/0 off case, where our magic factor factor is 1
we can choose an arbitrary magic factor say N

Then Similarity = N/(N + Sum)

Approach 3)
-----------
Use the Sum that we got in Approach 2 above
Similarity = Sum / N where N is the number of items common between A and B that have the same rating
Similarity = Sqrt(Similarity)
then to make Similarity fall between the range 0 and 1

Similarity = 1 - tanh(Similarity)

Approach 4)
-----------
Use the Similarity that we calculated in Approach 3
NN = Number of items common between A and B
Similarity = Similarity * (N / NN)

Little Sugar: Writing an oscillator function

Say you need to transform values v1, v2 in such a way that they lie between lowerlimit L and upper limit U

then u can use an oscillator function

new value = U - (L + (U * (1 / (1 + value))))

this new value will be between L and U, if u omit L then new value
would be between 0 - U

QuickSort : C++

i was having a re look at quick sort.

Here is the code in c++ :

template< class T >
int partition(T a[], int p, int r){
 T x = a[r];
 int i = p - 1;
 for(int j = p;j < r;j++){
  if(a[j] <= x){
   i++;
   swap(a[i],a[j]);
  }
 }
 swap(a[i+1] , a[r]);
 return i + 1;
}


template< class T >
void quickSort(T a[], int p, int r){
 if(p < r){
  int q = partition(a, p , r);
  quickSort(a, p , q-1);
  quickSort(a, q+1 , r);
 }
}

The idea of quicksort is to take an array and divide it into partitions .
First a key is chosen . That is called the pivot . Here 'x' is the pivot .
Based on the value of 'x' other values in an array are put in 2 partitions .
One partition that contains values less than 'x' and other partition contains values greater than x .

Here i and j are used to mark the extent of these 2 partitions .

The beauty of the algorithm lies in the fact , how integers are used to manipulate partitions . 'i' is initially set to value that precedes a real boundary . 'j' is set to the first location in the array . Now as values are compared with 'x' ( the key)
if value is less than 'x' the partition extent marked by 'i' are increased , else the partition extent marked by 'j' is increased . In the first case where values of 'i' is less than 'x' and since 'i' now occupies what 'j' occupied the values at those indices are swapped .

the partition method does in place sorting of the array and the quickSort method is responsible for choosing partitons .

Remove from Array : Java Quickie

lets say you have a problem . You have an array of N numbers . You want to remove the i th number . Then you need a new array not containing the j th number . You are using java . How can you do it ??

Here 's a quickie:

int[] result = null;

result = new int[n-1];
if(i > 0 ) System.arraycopy(array,0,result,0,i);
if(i+1 < n ) System.arraycopy(array,i+1,result,i,n-1-i);

}

This is quick way of removing the element you need and getting a new array devoid of the removed number .

Thnking in Heaps : Algorithms

An interative version of max-Heap :

void iter_maxHeapify(int * a,int rootIndex,int heapLength){
int largest = rootIndex;
int leftIndex = left(rootIndex);
int rightIndex = left(rootIndex);

for(int largest = rootIndex;
(leftIndex < heapLength) || (rightIndex < heapLength);
leftIndex = left(rootIndex),rightIndex = right(rootIndex)){

if(leftIndex < heapLength && a[rootIndex] < a[leftIndex]){
largest = leftIndex;
}
if(rightIndex < heapLength && a[largest] < a[rightIndex]){
largest = rightIndex;
}
if(rootIndex != largest){
swap(a[largest],a[rootIndex]);
rootIndex = largest;
}
}

}

Building the Heap:

void buildMaxHeap(int * a,int heapLength){
for(int i = heapLength/2;i >=0;i--){
maxHeapify(a,i,heapLength);
}
}


Sorting a heap:

void heapSort(int * a ,int heapLength){
buildMaxHeap(a,heapLength);
for(int i = 0;i < heapLength;i++){
swap(a[i],a[heapLength-1]);
maxHeapify(a,1,heapLength-i-1);
}
}

Little Sugar (Trees : relations)

A complete binary tree has odd number of nodes .

Number of leaves + number of internal nodes ( both even) +
1 = number of nodes in a tree

The number of internal nodes + 1 = number of leaves

number of internal nodes = number of leaves - 1

n = number of nodes

n = number of leaves + number of internal nodes

n +1 = 2 * number of leaves

number of leaves = (n+1)/2

The number of total nodes upto height h :

= pow(2,h+1) - 1

The number of nodes for any binary tree at height (h) :

= ceil(n / pow(2,h+1))

Little Sugar (Trees : relations)

A complete binary tree has odd number of nodes .

Number of leaves + number of internal nodes ( both even) +
1 = number of nodes in a tree

The number of internal nodes + 1 = number of leaves

number of internal nodes = number of leaves - 1

n = number of nodes

n = number of leaves + number of internal nodes

n +1 = 2 * number of leaves

number of leaves = (n+1)/2

Floating in a Tree

If you have a priority queue setup of many nodes. Lets say we want to bring the node with the highest value to the top . IN orther words if i have given a heap than how do i modify the heap so that the biggest element is always present at the root.

One simple logic can be . Given a root node of a subtree .

• Assume the root node is the largest node .
  
• Now compare the value of root node with left child and mark the one with the bigger value as biggest
• Then compare biggest with the right child now and make the bigger of the two as the new biggest.
• now repeat the above mentioned steps with the new largest node

In terms of code this looks like :

void maxHeapify(int * a,int rootIndex, int heapLength){
int largest = rootIndex;
int leftIndex = left(rootIndex);
int rightIndex = right(rootIndex);

if(leftIndex < heapLength && a[rootIndex] < a[leftIndex]){
largest = leftIndex;
}
if(rightIndex < heapLength && a[largest] < a[rightIndex]){
largest = rightIndex;
}
if(largest != rootIndex){
swap(a[largest],a[rootIndex]);
maxHeapify(a,largest,heapLength);
}
}

The worst case time for floating a node to any another node depending on your optimization would be approximately equal to the height of the tree , which would generally result in something like ~ lg(N) . To give a counter example for a max Heap operating in a heap . lets give a value of 0 to the root , and let all the other nodes be 1 . In that case the program would go all the way down the heap till the last leaf .

Little Sugar : Sequences

Given a sequence , the sum of elements from the i th position to the j th position can be easily found by adding the elements from the i th location to the j th location . A better optimization over this is generally to do a cumulative sum of all the elements upto the j th element . Then the
sum of any sub sequence can be found by taking the starting i th location and the ending j th location and subtracting the result of the element at the i th place from the element at the j th place .

All About Heap Sort -- Part 1

HeapSort is a sorting algorithm . It performs in place sorting . Its complexity it O(n lg n).
It makes use of a data structure called heap. The heap data structure is like an array which looks like a complete binary tree.If you imagine the heap array as a tree then each node in the tree will have left and right children . Each of the nodes in the tree map on to elements in the array . Every parent at index (i) will have a left child at index (2 * i ) and a right child at index (2 *i +1 ) in the array . Nodes in the heap follow the heap property . Heaps can be a max heap or a min heap.
In a max heap every Parent will have a higher value than any of its children . Its the opposite in the case of min heap. For the heap sort algorithm a max heap is used , generally a min heap is used for a priority queue.

Since a heap of (n) elements is like a complete binary tree its height is (lg n ) and all basic operations run in a time proportional to the height of the tree . Heap is a complete binary tree filled with elements at all levels except the last one . So the max number of elements in a heap of height (h) is (pow(2,h+1) - 1) . The minimum number of elements is equal to the number of elements in a heap of height (h-1) + 1 element. We add the extra one element because in the actual heap there would be at least one element on the last row containing leaves.
So the minimum number of elements = (pow(2,h) -1 ) + 1

The height of a heap is actually = floor(lg n ) . Since , a heap with height h will have elements (n) = pow(2,h) <= n <= pow(2,h+1)-1 < pow(2,h-1) and hence
h <= lg n < 1 =""> height = floor ( lg n )

Little Sugar (Heaps)

• Heap is a data structure whcih satisfies the MAX-HEAP or MIN-HEAP property
• All basic operations on a heap run in a time proportional to the height of the heap (lg n ) where n being the total number of nodes in a heap
• A heap is generally a complete tree
• IN an array represenation of an N-element heap the leaves nodes are indexed by n/2+1 , n/2 + 2 ... n
• In an N element heap , the number of nodes of height H are n/pow(2,h+1)
  

Little Sugar (Algorithm)

I came across an interesting property about numbers . If u have a number a and you consider multiples of the number , then for some number a the sum of the digits of the multiple is divisible by the number a

More than this , if you just check till the first 4 digit number , in that base then you get to know that for all multiple of the number the above mentioned property holds.

given a sequence [1 .. N] and a base ( b) , and number a . generating the multiples is as simple as doing 1 + a , 2 + a ....

finding the sum of the digits is a given base (b) is same as finding the sum of digits for base 10 that except for base 10 , base (b) is used

in code that looks like

while(n){
sum += n % base;
n = n/base;
}

the maximum 3 digit number is a given base is
base * base * base

Dividing a Sequence into K ranges

Problem Statement:
Say you have a sequence of N numbers and you want to partition the sequence into K groups such that after applying a cost function c(i) for each group the sum of all cost functions over all groups is minimized or maximized?

Approach:
To divide the sequence into ranges , we will use K keys . The key used to divide the group can be indices or values . If its values then numbers in the
sequence can be used along with values in the sequence to partition values into groups whose key is K.

One way to do this is to use K-for loops , if the key is value based then probable something like this would work:

for i = 1 to n
 for j = 1 to n
  for k = 1 to n
   for l = 1 to n{
    key1 = seq[i]
    key2 = seq[j]
    key3 = seq[k]
    key4 = seq[l]

 }

After dividing the sequence into keys, use the keys to apply and aggregate the result of individual cost functions . Depending upon the requirement reduce the cost functions using functions like min , max depending upon if you want to minimize or maximize your result.

There you go , now u have 1 simple way of dividing a sequence into groups