Thursday, October 19, 2017

Selection Algorithm implementation in C

How do you find out a median of an array? If someone asks you this question, you will immediately say "First sort it and then find the $\left ( \frac{n}{2}\right)^{th}$ element". Of course, this is correct. But what's the runtime? hmmm... the lower bound of any comparison based sorting algorithm is a ceiling of $\log_2(n!)$ which is in order of $\Theta(n\log_2n)$. No matter what sorting algorithm do you use, the running time is $\Omega(n\log_2n)$. Can we do better? That is, can we find a median of an array in linear time?. The answer is yes. The following code calculates the median of an array in $O(n)$ time. The algorithm is called 'Selection algorithm'. This algorithm calculates the '$k_{th}$' smallest value. Median is, therefore, $\left ( \frac{n}{2}\right)^{th}$' smallest element. The algorithm works as follows: (The code is also available on GitHub)
void swap(int* a, int* b) {
	int temp;
	temp = *a;
	*a = *b;
	*b = temp;
}

int median_1(int a[]) {
	return a[0];
}

int median_2(int a[]) {
	return a[1];
}

int median_3(int a[]) {
	int temp;
	if (a[0] < a[1]) {
		swap(&a[0], &a[1]);
	}
	if (a[0] > a[2]) {
		a[0] = a[1];
		a[1] = a[2];
	} else {
		return a[0];
	}
	if (a[0] > a[1]) {
		return a[0];
	} else {
		return a[1];
	}
}

int median_4(int a[]) {
	int temp1, temp2;
	if (a[0] < a[1]) {
		swap(&a[0], &a[1]);
	}
	if (a[2] > a[3]) {
		swap(&a[1], &a[2]);
	} else {
		temp1 = a[1];
		temp2 = a[2];
		a[1] = a[3];
		a[2] = temp1;
		a[3] = temp2;
	}
	if (a[0] > a[1]) {
		a[0] = a[1];
		a[1] = a[2];
	} else {
		a[1] = a[3];
	}
	if (a[0] > a[1]) {
		return a[0];
	} else {
		return a[1];
	}
}

// six comparisions
int median_5(int a[]) {
	int temp1, temp2;
	if (a[0] < a[1]) {
		swap(&a[0], &a[1]);
	} 
	if (a[2] > a[3]) {
		swap(&a[1], &a[2]);
	} else {
		temp1 = a[1];
		temp2 = a[2];
		a[1] = a[3];
		a[2] = temp1;
		a[3] = temp2;
	}
	if (a[0] > a[1]) {
		a[0] = a[1];
		a[1] = a[3];
		a[3] = a[4];
	} else {
		a[1] = a[2];
		a[2] = a[3];
		a[3] = a[4];
	}
	if (a[2] > a[3]) {
		swap(&a[1], &a[2]);
	} else {
		temp1 = a[1];
		temp2 = a[2];
		a[1] = a[3];
		a[2] = temp1;
		a[3] = temp2;
	}
	if (a[0] > a[1]) {
		a[0] = a[1];
		a[1] = a[2];
	} else {
		a[1] = a[3]; 
	}
	if(a[0] > a[1]) {
		return a[0];
	} else {
		return a[1];
	}
}

int median(int a[], int n){
	switch(n) {
		case 1: 
		return median_1(a);
		break;
		case 2:
		return median_2(a);
		break;
		case 3:
		return median_3(a);
		break;
		case 4:
		return median_4(a);
		break;
		case 5:
		return median_5(a);
		break;
		default:
		break;
	}
	return -1;
}

// select method returns the kth smallest element
// median is the n/2 th smallest element
// This function runs in linear time
int select(int k, int a[], int n) {
	int **subarrays, *medians, *left, *right;
	int i, j, l, m,columns, pivot, len_l = 0, len_r = 0;

	if (n == 1) {
		return a[0];
	}

	columns = ceil(n / 5.0);

	subarrays = (int**)malloc(sizeof(int*)*columns);
	for (i=0;i<columns;i++){
		subarrays[i] = (int*)malloc(sizeof(int)*5);
	}

	medians = (int*) malloc(sizeof(int*) * columns);

	for (i = 0, j = 0; i < n; i = i + 5, j++) {
		if (j == columns) {
			for (l = 0; l < n % 5; l++) {
				subarrays[j][l] = a[i + l];
			}
		} else {
			for (l = 0; l < 5; l++) {	
				subarrays[j][l] = a[i + l];
			}
		}
	}

	// calculate local medians
	for (i = 0; i < columns; i++) {
		if (n % 5 != 0 && i == columns - 1) {
			medians[i] = median(subarrays[i], n % 5);
		} else {
			medians[i] = median(subarrays[i], 5);
		}
	}

	if (columns <= 5) {
		pivot = median(medians, columns);
	} else {
		pivot = select(columns/2, medians, columns);
	}

	// create right and left array
	for (i = 0; i < n; i++) {
		if (a[i] > pivot) {
			len_r++;
		} 
		if (a[i] < pivot) {
			len_l++;
		}
	}

	left = (int*) malloc(sizeof(int*) * len_l);
	right = (int*) malloc(sizeof(int*) * len_r);

	l = 0, m = 0;
	for (i = 0; i < n; i++) {
		if (a[i] > pivot){
			right[l] = a[i];
			l++;
		} 
		if (a[i] < pivot) {
			left[m] = a[i];
			m++;
		}

	}
	if (len_l == k - 1) {
		return a[0];
	}
	if (len_l > k - 1) {
		return select(k, left, len_l);
	} 
	if (len_l < k - 1) {
		return select(k - len_l - 1, right, len_r);
	}
	return -1;
}

Largest and Smallest Element of an Array in C

Calculating largest and smallest element in C is straightforward. All you have to do is scan through the array one element at a time and compare it with current largest or smallest value. Since you scan every element of array, there will be n (number of elements in the array) comparisons. Therefore the running time of this algorithm is $\Theta(n)$.

Calculation of Largest Element
int get_largest(int a[], int n) {
 int i, largest = 0;
 for (i = 0; i < n; i++) {
  if (a[i] > largest) {
   largest = a[i];
  }
 }
 return largest;
}

Calculation of Smallest Element
int get_smallest(int a[], int n) {
 int i, smallest = 2147483647;
 for (i = 0; i < n; i++) {
  if (a[i] < smallest) {
   smallest = a[i];
  }
 }
 return smallest;
}

This code is also available in GitHub.  

Pyramid and Star pattern generation in C

Generating pyramid and other star patterns in C extend your knowledge of using a loop in a program. In the program below I have generated various patterns. You can combine the multiple patterns to generate a new pattern.  All patterns use for loop. The patterns that the code generates are:



























The sample code is also available on Github
#include 
#include 

void pattern_1(int n) {
 int i, j;

 for(i = 0; i < n; i++) {
  for (j = 0; j <= i; j++) {
   printf("*");
  }
  printf("\n");
 }
}

void pattern_2(int n) {
 int i, j;

 for(i = 0; i < n; i++) {
  for(j = 0; j < n - i - 1; j++) {
   printf(" ");
  }
  for (j = 0; j <= i; j++) {
   printf("*");
  }
  printf("\n");
 }
}

void pattern_3(int n) {
 int i, j;

 for(i = 0; i < n; i++) {
  for(j = 0; j < n - i - 1; j++) {
   printf(" ");
  }
  for (j = 0; j <= 2 * i; j++) {
   printf("*");
  }
  printf("\n");
 }
}

void pattern_4(int n) {
 int i, j;
 for(i = n - 1; i >= 0; i--) {
  for (j = 0; j <= i; j++) {
   printf("*");
  }
  printf("\n");
 }
}

void pattern_5(int n) {
 int i, j;
 for(i = n - 1; i >= 0; i--) {
  for(j = 0; j < n - i - 1; j++) {
   printf(" ");
  }
  for (j = 0; j <= i; j++) {
   printf("*");
  }
  printf("\n");
 }
}

void pattern_6(int n) {
 int i, j;

 for(i = n - 1; i >= 0; i--) {
  for(j = 0; j < n - i - 1; j++) {
   printf(" ");
  }
  for (j = 0; j <= 2 * i; j++) {
   printf("*");
  }
  printf("\n");
 }
}

void pattern_7(int n) {
 int i, j;

 for(i = 0; i < n; i++) {
  for(j = 0; j < n - i; j++) {
   printf(" ");
  }
  for (j = 0; j <= 2 * i; j++) {
   printf("*");
  }
  printf("\n");
 }
 for(i = (n - 1) ; i >= 0; i--) {
  for(j = 0; j < n - i; j++) {
   printf(" ");
  }
  for (j = 0; j <= 2 * i; j++) {
   printf("*");
  }
  printf("\n");
 }
}

void pattern_8(int n) {
 int i, j, k;
 for (i = 0; i < n; i++) {
  printf("\n");
  for(k = 0; k < n - i; k++) {
   printf("*");
  }

  for(k = 2*i; k > 0; k--) {
   printf(" ");
  }

  for(k = 0; k < n - i; k++) {
   printf("*");
  }
  

 }
 for (i = 0; i <= n; i++) {
  for(k = 0; k < i; k++) {
   printf("*");
  }

  for(k = 0; k < 2* (n - i); k++) {
   printf(" ");
  }

  for(k = 0; k < i; k++) {
   printf("*");
  }
  printf("\n");
 }
}

int main(int argc, char *argv[]) {
 int n;
 if (argc != 2) {
  printf("Usage: outputfile n\n");
  exit(1);
 }

 n = atoi(argv[1]);

 pattern_1(n);
 printf("\n");
 pattern_2(n);
 printf("\n");
 pattern_3(n);
 printf("\n");
 pattern_4(n);
 printf("\n");
 pattern_5(n);
 printf("\n");
 pattern_6(n);
 printf("\n");
 pattern_7(n);
 printf("\n");
 pattern_8(n);
}

Sunday, March 6, 2016

Difference between exports and module.exports in Node.js

When you have large javascript file, you want to break that file into independent modules so that you can reuse each module in different files.  Node.js follows CommonJS module system in which modules are imported using require method available in global scope. For example, lets say you have two files, person.js and main.js. To import person.js functionality into main.js, you would do this

var Person = require('person');

Now you can use methods defined in person.js in main.js using Person variable. To be able to get the Person variable from person.js file, we should have return statement inside the person.js file so that require method assigns return value to the Person variable.  person.js would look like this

Saturday, March 5, 2016

Sorting Java objects based on property

In Java, sorting of group of  primitive type is simple. That is, sorting of group of integers, floats, doubles or strings is one step process (if you don't use your own algorithm for sorting).  java.util provides various methods for sorting these kind of group. Two of them are :
  1. Arrays.sort()
  2. Collections.sort()
Why sorting of group of primitive type is simple?

The answer is Java knows what exactly are those types and how to compare those types to each other. For example, comparing two integers is simply using the logical <, = and > operator. Similar for float, double and strings.

But, if you have your custom type (i.e. class) of data, then Java doesn't know what to do with them.  Lets say you have group of people with different properties like height, weight, age, name, religion and so on,  and you want Java to sort these people in increasing order. When Java tries to compare two people, it gets confused. It doesn't know which parameter to consider for sorting. Sorting can be done based on height, weight, age etc but which one to take as a parameter to decide?

To solve this problem, you need to explicitly specify the property. Based on the property, comparison should be carried out i.e. if you want to sort people based on their height, you need to tell Java explicitly that I want to sort people based on their height.

Programatically, this can be accomplished using Comparator interface as follows.

Collections.sort(persons, new Comparator () {
        @Override
 public int compare(Person p1, Person p2) {
  return Integer.compare(p1.height, p2.height);
 }
});

Passing implementation of Comparator interface as a second argument to Collection.sort method helps Java to make decision while comparing between two objects.

In above code snippet, you see that you need to implement one method i.e. compare , to carry out this operation.  If you closely observe the code you can see we  have explicitly specified that sorting needs to be carried out based on height. The compare method returns 3 possible values

  1. A negative integer -> means first argument is less than second argument
  2. Zero -> means both arguments are equal
  3. A positive integer -> means first argument is greater than second argument
A runnable example for sorting is given bellow.

import java.util.*;
class Person {
 // height in cm
 public int height; 
 public String name;
 public Person(int height, String name) {
  this.height = height;
  this.name = name;
 }
}
class CustomSort {
 static void sort(List persons) {
  Collections.sort(persons, new Comparator () {
   @Override
   public int compare(Person p1, Person p2) {
    return Integer.compare(p1.height, p2.height);
   }
  });
 }
 public static void main(String [] args) {
  List persons = new ArrayList<>();
  // add some persons to arraylist
  persons.add(new Person(154, "John"));
  persons.add(new Person(150, "Henry"));
  persons.add(new Person(160, "Smith"));
  persons.add(new Person(162, "Bob"));
  persons.add(new Person(155, "Rubina"));
  persons.add(new Person(170, "Stiva"));
  persons.add(new Person(178, "Bijay"));
  CustomSort.sort(persons);
  System.out.println("Sorted persons based on height");
  System.out.println();
  for (Person person: persons) {
   System.out.println(person.name);
  }
 }
}

Wednesday, September 30, 2015

Retrofit 2.0 tutorial with sample application

Retrofit is a HTTP client library in Android and Java. It has great performance compares to AsyncTask and other android networking libraries. Retrofit 2.0 has been released few months back with major update. In this tutorial I am going to talk about how to create a simple REST client  in Android that communicates with REST endpoint to perform the READ and WRITE operations. This tutorial is intended for retrofit 2.0 beginner who are using retrofit for first time and getting their hand dirty with retrofit 2.0.

The overview of application that we are creating is as follows. The application has two main components 1) REST client in Android 2) REST server in Node.js. We will focus on REST client as this writing is for retrofit which is client library. We will create REST endpoints that creates and list User. User has two properties., username and name. The program  (Client) has two methods; one for creating user and other for listing all the users. Final android application has two fragments in pager view, one has interface for creating new user and another for listing the user. In backend, the program uses Mongodb as database.

Friday, February 7, 2014

Discrete Cosine Transform and JPEG compression : Image Processing

JPEG is well known standard for image compression and Discrete Cosine Transform (DCT) is the mathematical tool used by JPEG for achieving the compression. JPEG is lossy compression meaning some information is lost during the compression. Lets dig deeper into the JPEG standard starting from the block diagram.

Above diagram shows the encoder part of JPEG. The decoder is the reverse of encoder except it doesn't contains the reverse part of Quantizer block and this is the main reason why JPEG is lossy compression. We cannot recover data lost during the quantization step. The operations performed by each block is presented below

Thursday, January 9, 2014

Google Cloud Messaging (GCM) in Android using PHP Server

GCM for android is a service which is basically used to send the data from server to the android devices. One use of this GCM is a push notification service. In this tutorial, I am going through all the steps needed to setup the GCM and build a simple but complete android  application in Eclipse.