PageRank Algorithm Using Mapreduce

Description  -  http://en.wikipedia.org/wiki/PageRank


Examples of pagerank calculation - http://pagerank.suchmaschinen-doktor.de/index/examples.html

Formula for pagerank calculation:

PR(A) = (1 - d) + d * SUM ((PR(I->A)/C(I))

Where:

• PR(A) is the PageRank of your page A.
• d is the damping factor, usually set to 0,85.
• PR(I->A) is the PageRank of page I containing a link to page A.
• C(I) is the number of links off page I.
• PR(I->A)/C(I) is a PR-value page A receives from page I.
• SUM (PR(I->A)/C(I)) is the sum of all PR-values page A receives from pages with links to page A..

 Inputs and Outputs of Mapper and Reducer - https://wiki.umiacs.umd.edu/ccc/images/e/ea/CLuE-Jagannathan.pdf 







Video lecture

Factorization of a Number is in NP. Why?

Factoring a number seems to be trivial. The fact is that factorization when done in binary takes non-polynomial time.

For more information check http://en.wikipedia.org/wiki/Integer_factorization

Polynomial Reduction Example

Show that WRITE_ONE_TM = {M : M is a Turing machine that writes a 1 on its tape } is undecidable.

Let us assume that WRITE_ONE_TM is decidable. Then there exists a Turing machine WRITE_ONE_TM,  which can tell you if a given Turing Machine M will write a 1 on its tape on input z.

Let us look at how WRITE_ONE_TM  works.

M is the input to WRITE_ONE_{TM .}

If M writes a 1 on its tape , WRITE_ONE_TM  accepts.  – Yes instance

If M does not write a 1 on its tape, WRITE_ONE_TM  rejects. – No instance.

If M writes a 1 on its tape at any time of its computation, WRITE_ONE_TM decides yes. It does not matter what M does before it writes 1 on its tape.

 M might have 10000 transitions before it writes 1 on its tape. Still WRITE_ONE_TM should be able to decide whether M will write 1 on its tape.

M might compute what is 5+7 before it writes 1 on its tape. Still WRITE_ONE_TM should be able to decide whether M will write 1 on its tape.

M can watch a youtube video and then write a 1 on its tape. Still WRITE_ONE_TM should be able to decide whether M will write 1 on its tape.

( just kidding)

M might simulate another Turing Machine and then write a 1 on its tape. Still WRITE_ONE_TM should be able to decide whether M will write a1 on its tape.

Suppose M is simulating another machine T on input w on M’s tapes and if T accepts w, M is writing a 1 on its tape. Still WRITE_ONE_TM should be able to decide whether M will write a1 on its tape.

Did you hear that?

Isn’t that a solution to decidability of A_TM. Whenever you have to decide if a TM T will accept or reject w, all you have to do is:

Construct a new TM, M such that

·        It simulates T on input w on M’s tape

·        If T accepts w, write a 1 on M’s tape.

·        Feed M to WRITE_ONE_TM

·        If WRITE_ONE_TM decides yes, T accepts w.

    

But we already know that A_TM is undecidable. So it is not possible that WRITE_ONE_TM  can be decidable if it can solve A_TM.

Hence WRITE_ONE_TM  is undecidable.

    

  

Number of full nodes in a binary tree c++

A FULL node in a binary tree is a node that has exactly two non-null children. Write a RECURSIVE function that returns the number of full nodes in a binary tree.



# include <iostream >
#include  <stdio.h >

using namespace std;

struct TreeNode{
    int value;
    TreeNode* left;
    TreeNode* right;
};


int FullNodes(TreeNode* root){
   

    if(root == NULL)        //if tree is empty
        return 0;
    if(root->left == NULL && root->right == NULL)         //leaf nodes
        return 0;
    if(root->left!=NULL && root->right != NULL)             // Full Nodes
        return 1 + FullNodes(root->left) + FullNodes(root->right);

    if(root->left==NULL && root->right != NULL)           //Nodes with no left child
        return FullNodes(root->right);

    if(root->left!=NULL && root->right == NULL)          // Nodes with no right child
        return FullNodes(root->left);

}
/*---------------------------------TEST---------------------------------*/

//Function to insert into binary tree
void insert(TreeNode*& root, int num){
       
    if(root == NULL){
        root = new TreeNode();
        root->value = num;
        root->left = NULL;
        root->right = NULL;   
       
    }
    else if(num < root->value){
        insert(root->left,num);
    }
    else
        insert(root->right,num);
}


int main(){


//creates a tree
    TreeNode* tree = NULL;
    insert(tree, 8);
    insert(tree, 5);
    insert(tree,10);
    insert(tree, 3);
    insert(tree, 9);
    insert(tree, 6);
   


//Full Node count test
    cout << FullNodes(tree); //8 and 5 are full nodes . So output is 2

    return 0;
}