Pearson's Correlation Coefficient

Pearson's Correlation Coefficient

In statistics, the Pearson product-moment correlation coefficient  is a measure of the linear correlation between two variables X and Y, giving a value between +1 and −1 inclusive, where 1 is total positive correlation, 0 is no correlation, and −1 is total negative correlation. It is widely used in the sciences as a measure of the degree of linear dependence between two variables.

Pearson's correlation coefficient is the covariance of the two variables divided by the product of their standard deviations. 

Pearson's correlation coefficient when applied to a population is commonly represented by the Greek letter ρ (rho) and may be referred to as the population correlation coefficient or the population Pearson correlation coefficient. The formula for ρ^[7] is:

where:

•  is the covariance
•  is the standard deviation of 

The formula for ρ can be expressed in terms of mean and expectation. Since

• ^[7]

Then the formula for ρ can also be written as

where:

•  and  are defined as above
•  is the mean of 
•  is the expectation.

The formula for ρ can be expressed in terms of uncentered moments. Since

• 
• 
• 
• 
• 

Then the formula for ρ can also be written as

 Covariance is a measure of how much two random variables change together. If the greater values of one variable mainly correspond with the greater values of the other variable, and the same holds for the smaller values, i.e., the variables tend to show similar behavior, the covariance is positive.^[1] In the opposite case, when the greater values of one variable mainly correspond to the smaller values of the other, i.e., the variables tend to show opposite behavior, the covariance is negative. The sign of the covariance therefore shows the tendency in the linear relationship between the variables. The magnitude of the covariance is not easy to interpret. The normalized version of the covariance, the correlation coefficient, however, shows by its magnitude the strength of the linear relation.

Correlation is a technique for investigating the relationship between two quantitative, continuous variables, for example, age and blood pressure. Pearson's correlation coefficient (r) is a measure of the strength of the association between the two variables.

The first step in studying the relationship between two continuous variables is to draw a scatter plot of the variables to check for linearity. The correlation coefficient should not be calculated if the relationship is not linear. For correlation only purposes, it does not really matter on which axis the variables are plotted. However, conventionally, the independent (or explanatory) variable is plotted on the x-axis (horizontally) and the dependent (or response) variable is plotted on the y-axis (vertically).

The nearer the scatter of points is to a straight line, the higher the strength of association between the variables. Also, it does not matter what measurement units are used.

Values of Pearson's correlation coefficient

Pearson's correlation coefficient (r) for continuous (interval level) data ranges from -1 to +1:

r = -1		data lie on a perfect straight line with a negative slope
r = 0		no linear relationship between the variables
r = +1		data lie on a perfect straight line with a positive slope

Positive correlation indicates that both variables increase or decrease together, whereas negative correlation indicates that as one variable increases, so the other decreases, and vice versa.

Heap Implementation in JAVA

In computer science, a heap is a specialized tree-based data structure that satisfies the heap property: If A is a parent node of B then the key of node A is ordered with respect to the key of node B with the same ordering applying across the heap. A heap can be classified further as either a "max heap" or a "min heap". In a max heap, the keys of parent nodes are always greater than or equal to those of the children and the highest key is in the root node. In a min heap, the keys of parent nodes are less than or equal to those of the children and the lowest key is in the root node. Heaps are crucial in several efficient graph algorithms such as Dijkstra's algorithm, and in the sorting algorithm heapsort. A common implementation of a heap is the binary heap, in which the tree is a complete binary tree (see figure).

In a heap, the highest (or lowest) priority element is always stored at the root, hence the name heap. A heap is not a sorted structure and can be regarded as partially ordered. As visible from the heap-diagram, there is no particular relationship among nodes on any given level, even among the siblings. When a heap is a complete binary tree, it has a smallest possible height—a heap with N nodes always has log N height. A heap is a useful data structure when you need to remove the object with the highest (or lowest) priority.

1:  package com.examples.ajay;  
2:  class Heap{  
3:       int[] array;  
4:       int count;  
5:       int capacity;  
6:       int heap_type;  
7:  }  
8:  public class HeapImplementation {  
9:       public static Heap createHeap(int capacity, int heap_type){  
10:            Heap heap = new Heap();  
11:            heap.array = new int[capacity];  
12:            if(heap.array == null) return null;  
13:            heap.heap_type = heap_type;  
14:            heap.count = 0;  
15:            heap.capacity = capacity;  
16:            return heap;  
17:       }  
18:       public static int getParent(Heap heap, int i){  
19:            if(i >= heap.count || i <= 0) return -1; //asking for parent of root or entry outside the amount of elements in heap  
20:            return (i-1)/2;  
21:       }  
22:       public static int leftChild(Heap heap, int i){  
23:            int left = 2*i + 1;  
24:            if(left >= heap.count) return -1;  
25:            else return left;  
26:       }  
27:       public static int rightChild(Heap heap, int i){  
28:            int right = 2*i + 2;  
29:            if(right >= heap.count) return -1;  
30:            else return right;  
31:       }  
32:       public static int getMaximum(Heap heap){  
33:            if(heap.count <= 0) return -1;  
34:            else return heap.array[0];  
35:       }  
36:       public static void heapify(Heap heap , int i){  
37:            int left, right, max;  
38:            left = leftChild(heap, i);  
39:            right = rightChild(heap, i);  
40:            //exchange parent with the maximum among both of left or right children  
41:            if(left != -1 && heap.array[left] > heap.array[i]) max = left;  
42:            else max = i;  
43:            if(right != -1 && heap.array[right] > heap.array[max]) max = right;  
44:            if(max != i){  
45:                 int temp = heap.array[max];  
46:                 heap.array[max] = heap.array[i];  
47:                 heap.array[i] = temp;  
48:                 heapify(heap, max);  
49:            }  
50:       }  
51:       public static int deleteMax(Heap heap){  
52:            int data;  
53:            if(heap.count <= 0) return -1;  
54:            data = heap.array[0];  
55:            heap.array[0] = heap.array[heap.count - 1];  
56:            heap.count--;  
57:            heapify(heap, 0);  
58:            return data;  
59:       }  
60:       public static void insert(Heap heap, int data){  
61:            if(heap.count == heap.capacity) resizeHeap(heap);  
62:            heap.count++;  
63:            int i = heap.count - 1;  
64:            //find location till data is greater than the parent of node which is inserted at count-1  
65:            while(i > 0 && data > heap.array[(i-1)/2]){  
66:                 heap.array[i] = heap.array[(i-1)/2];  
67:                 i = (i-1)/2;  
68:            }  
69:            heap.array[i] = data;  
70:       }  
71:       private static void resizeHeap(Heap heap) {  
72:            // TODO Auto-generated method stub  
73:            int i = 0;  
74:            int[] temp = heap.array;  
75:            heap.array = new int[heap.capacity * 2];  
76:            for (int element : temp) {  
77:                 heap.array[i++] = element;  
78:            }  
79:            heap.capacity *= 2;  
80:       }  
81:       public static void main(String[] args) {  
82:            // TODO Auto-generated method stub  
83:            int[] heapArray = {3, 1, 9, 8, 14, 12, 5, 7, 31, 10, 16};  
84:            Heap heap = createHeap(heapArray.length, 0);  
85:            /*for(int element : heapArray){  
86:                 insert(heap, element);  
87:            }*/  
88:            int i = 0;  
89:            for(int element : heapArray){  
90:                 heap.array[i++] = element;  
91:            }  
92:            heap.count = heapArray.length;  
93:            for(i = (heapArray.length - 1)/2; i >= 0 ; i--) heapify(heap, i);  
94:            System.out.println("Results: ");  
95:            for(i = 0; i < heap.count ; i++){  
96:                 System.out.print(heap.array[i] + " ");  
97:            }  
98:            System.out.println();  
99:            System.out.println("Deleing root ...");  
100:            deleteMax(heap);  
101:            System.out.println("Results: ");  
102:            for(i = 0; i < heap.count ; i++){  
103:                 System.out.print(heap.array[i] + " ");  
104:            }  
105:       }  
106:  }  

Output :

Results: 

31 16 12 9 14 3 5 1 7 8 10 

Deleting root ...

Results: 

16 14 12 9 10 3 5 1 7 8 

Sort elements by frequency

Print the elements of an array in the decreasing frequency if 2 numbers have same frequency then print the one which came first.

Examples:

Input:  arr[] = {2, 5, 2, 8, 5, 6, 8, 8}
Output: arr[] = {8, 8, 8, 2, 2, 5, 5, 6}

Input: arr[] = {2, 5, 2, 6, -1, 9999999, 5, 8, 8, 8}
Output: arr[] = {8, 8, 8, 2, 2, 5, 5, 6, -1, 9999999}

 Input 5  2  2  8  5  6  8  8

  After sorting we get
  Element 2 2 5 5 6 8 8 8
  Index   1 2 0 4 5 3 6 7

  Now construct the 2D array as
  Index, Count
  1,      2
  0,      2
  5,      1
  3,      3

  Sort by count (consider indexes in case of tie)
  3, 3
  0, 2
  1, 2
  5, 1
  
  Print the elements using indexes in the above 2D array.

=================================================

JAVA IMPLEMENTATION

=================================================

import java.util.ArrayList;

import java.util.Collections;

import java.util.Comparator;

import java.util.HashMap;

import java.util.List;

import java.util.Map;

import java.util.Set;

class Element{

int value;

int index;

int count;

public Element(int value, int index, int count){

this.value = value;

this.index = index;

this.count = count;

}

}

public class SortElementByFrequency {

public static void main(String[] args) {

int array[] = {2, 5, 2, 6, -1, 999999, 5, 8, 8, 8};

int index = 0;

Map<Integer, Element> map = new HashMap<Integer , Element>();

for (int value : array) {

Element element = new Element(value, index, 1);

index++;

if(map.get(element.value) != null){

Element newelement = map.get(element.value);

newelement.count += 1;

map.put(element.value, newelement);

}else{

map.put(element.value, element);

}

}

Set<Integer> keys = map.keySet();

List<Element> list = new ArrayList<Element>();

for (Integer key : keys) {

list.add(map.get(key));

}

Collections.sort(list, new Comparator<Element>() {

@Override

public int compare(Element e1, Element e2) {

// TODO Auto-generated method stub

if(e2.count-e1.count != 0){

return e2.count-e1.count;

}else{

return e1.index-e2.index;

}

}

});

for (Element element : list) {

int count = element.count;

while(count > 0){

System.out.print(element.value + "  ");

count--;

}

}

}

}

Maximum sum such that no two elements are adjacent

Question: Given an array of positive numbers, find the maximum sum of a subsequence with the constraint that no 2 numbers in the sequence should be adjacent in the array. So 3 2 7 10 should return 13 (sum of 3 and 10) or 3 2 5 10 7 should return 15 (sum of 3, 5 and 7).Answer the question in most efficient way.

Algorithm:
Loop for all elements in arr[] and maintain two sums incl and excl where incl = Max sum including the previous element and excl = Max sum excluding the previous element.

Max sum excluding the current element will be max(incl, excl) and max sum including the current element will be excl + current element (Note that only excl is considered because elements cannot be adjacent).

At the end of the loop return max of incl and excl.

package com.examples.ajay;

public class MaxSumNoAdjacentElement {

  private static int max(int i, int j) {

// TODO Auto-generated method stub

if(i < j) return j;

else return i;

}

private static void findSum(int[] array) {

// TODO Auto-generated method stub

int inclusive = array[0]; 
  // Max sum including current element. (If current included, prev     have to be excluded)

int exclusive = 0;
  // Max sum excluding current element : max (prev-incl, prev-excl) 

for(int i = 1; i< array.length; i++){

int temp = inclusive;

inclusive = exclusive + array[i];

exclusive = max(exclusive, temp);

}

System.out.println("Result : "+ max(inclusive, exclusive));

}

public static void main(String[] args) {

// TODO Auto-generated method stub

int array[] = {5, 5, 10, 40, 50, 35};

findSum(array);

}

}

Program for array rotation

Write a function rotate(ar[], d, n) that rotates arr[] of size n by d elements.

Rotation of the above array by 2 will make array

METHOD 1 (Use temp array)

Input arr[] = [1, 2, 3, 4, 5, 6, 7], d = 2, n =7
1) Store d elements in a temp array
   temp[] = [1, 2]
2) Shift rest of the arr[]
   arr[] = [3, 4, 5, 6, 7, 6, 7]
3) Store back the d elements
   arr[] = [3, 4, 5, 6, 7, 1, 2]

Time complexity O(n)
Auxiliary Space: O(d)

METHOD 2 (Rotate one by one)

leftRotate(arr[], d, n)
start
  For i = 0 to i < d
    Left rotate all elements of arr[] by one
endTime complexity: O(n*d)

Auxiliary Space: O(1)

METHOD 3 (A Juggling Algorithm)
This is an extension of method 2. Instead of moving one by one, divide the array in different sets
where number of sets is equal to GCD of n and d and move the elements within sets.
If GCD is 1 as is for the above example array (n = 7 and d =2), then elements will be moved within one set only, we just start with temp = arr[0] and keep moving arr[I+d] to arr[I] and finally store temp at the right place.

Here is an example for n =12 and d = 3. GCD is 3 and

Let arr[] be {1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12}

a) Elements are first moved in first set – (See below diagram for this movement)



          arr[] after this step --> {4 2 3 7 5 6 10 8 9 1 11 12}

b) Then in second set.
          arr[] after this step --> {4 5 3 7 8 6 10 11 9 1 2 12}

c) Finally in third set.
          arr[] after this step --> {4 5 6 7 8 9 10 11 12 1 2 3}

Java Code for Juggler Algorithm :

package com.examples.ajay;


public class RotateArrrayJugglerWay {

 private static int findGCD(int n, int d){
  if(n % d == 0) return d;
  else return findGCD(d, n % d);
 }
 private static void leftRotate(int[] array, int dist, int length) {
  // TODO Auto-generated method stub
  int gcd = findGCD(length, dist);
  int set_number = length / gcd;
  for(int i =0; i< gcd; i++){
   int temp = array[i];
   int j = i;
   while((j+gcd) < length){
    array[j] = array[j + gcd];
    j = j + gcd;
   }
   array[j] = temp;
  }
  for (int element : array) {
   System.out.print(element + " ");
  }
 }
 public static void main(String[] args) {
  int array[] = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12};
  leftRotate(array, 11, array.length);
 }
}

Time complexity: O(n)
Auxiliary Space: O(1)

Method 4(The Reversal Algorithm)
Please read this for first three methods of array rotation.

Algorithm:
rotate(arr[], d, n)
  reverse(arr[], 1, d) ;
  reverse(arr[], d + 1, n);
  reverse(arr[], l, n);


Let AB are the two parts of the input array where A = arr[0..d-1] and B = arr[d..n-1]. The idea of the algorithm is:
Reverse A to get ArB. /* Ar is reverse of A */
Reverse B to get ArBr. /* Br is reverse of B */
Reverse all to get (ArBr) r = BA.

For arr[] = [1, 2, 3, 4, 5, 6, 7], d =2 and n = 7
A = [1, 2] and B = [3, 4, 5, 6, 7]
Reverse A, we get ArB = [2, 1, 3, 4, 5, 6, 7]
Reverse B, we get ArBr = [2, 1, 7, 6, 5, 4, 3]
Reverse all, we get (ArBr)r = [3, 4, 5, 6, 7, 1, 2]

Note : Examples and description have been taken from geeksforgeeks.org.

Find Majority Element in an Array : Occurrence more than n/2

import java.util.Scanner;
//Method 1
/*The basic solution is to have two loops and keep track of maximum count for all different elements. If maximum count becomes greater than n/2 then break
the loops and return the element having maximum count. If maximum count doesn’t become more than n/2 then majority element doesn’t exist.
Time Complexity: O(n*n).
Auxiliary Space : O(1)

//Method 2
Insert elements in BST one by one and if an element is already present then increment the count of the node. At any stage, if count of a node becomes more than n/2 then return.
The method works well for the cases where n/2+1 occurrences of the majority element is present in the starting of the array, for example {1, 1, 1, 1, 1, 2, 3, 4}.

Time Complexity: If a binary search tree is used then time complexity will be O(n^2). If a self-balancing-binary-search tree is used then O(nlogn)
Auxiliary Space: O(n)


//Method 3  Moore’s Voting Algorithm
This is a two step process.
1. Get an element occurring most of the time in the array. This phase will make sure that if there is a majority element then it will return that only.
2. Check if the element obtained from above step is majority element.
1. Finding a Candidate:
The algorithm for first phase that works in O(n) is known as Moore’s Voting Algorithm. Basic idea of the algorithm is if we cancel out each occurrence of an element
e with all the other elements that are different from e then e will exist till end if it is a majority element.

*/

public class FindMajority {
private static int findMajority(int[] array){
int majorityCand = array[0];
int count = 0;
for(int i = 0; i< array.length; i++){
if(array[i] == majorityCand) count++;
else count--;
if(count == 0){
majorityCand = array[i];
count = 1;
}
}
count = 0;
for(int i = 0; i< array.length; i++){
if(array[i] == majorityCand) count++;
}
if(count > array.length/2) System.out.println("Majoirty element :" + majorityCand);
else System.out.println("No majority element !!");
return 0;
}
public static void main(String[] args) {
Scanner in = new Scanner(System.in);
int N = in.nextInt();
int[] array = new int[N];
for(int i = 0; i< N; i++){
array[i] = in.nextInt();
}
findMajority(array);
}
}

Game of Thrones - I

Problem Statement

Dothraki are planning an attack to usurp King Robert's throne. King Robert learns of this conspiracy from Raven and plans to lock the single door through which the enemy can enter his kingdom.

But, to lock the door he needs a key that is an anagram of a certain palindrome string.

The king has a string composed of lowercase English letters. Help him figure out whether any anagram of the string can be a palindrome or not.

Input Format 
A single line which contains the input string.

Constraints 
1≤ length of string ≤105 
Each character of the string is a lowercase English letter.

Output Format 
A single line which contains YES or NO in uppercase.

Sample Input : 01

aaabbbb

Sample Output : 01

YES

Explanation 
A palindrome permutation of the given string is bbaaabb. 

Sample Input : 02

cdefghmnopqrstuvw

Sample Output : 02

NO

Explanation 
You can verify that the given string has no palindrome permutation. 

Sample Input : 03

cdcdcdcdeeeef

Sample Output : 03

YES

Explanation 
A palindrome permutation of the given string is ddcceefeeccdd

import java.io.*;
import java.util.*;

public class Solution {

    public static void main(String[] args) {
        /* Enter your code here. Read input from STDIN. Print output to STDOUT. Your class should be named Solution. */
        Scanner in = new Scanner(System.in);
        String entry = in.next();
        int[] frequency = new int[26];
        for(int i =0; i<entry.length(); i++){
            char ch = entry.charAt(i);
            frequency[ch - 'a']++;
        }
        int countOdd = 0;
        for(int i = 0; i < 26 ; i++){
            if(frequency[i] % 2 != 0){
                countOdd++;
            }
        }
        if(countOdd > 1) System.out.println("NO");
        else System.out.println("YES");
    }
}