March 18, 2013

Mergesort

One of the divide and conquer types of algo.

Merging: Combine two ordered arrays to make one larger ordered array.

Mergesort:
To sort an array

  • Divide it into two halves
  • Sort the two halves (recursively)
  • Merge the result

Mergesort

MergeSort

Mergesort guarantees to sort an array of N items in time proportional to N log N, no matter what the input. Its prime disadvantage is that it uses extra space proportional to N.

February 17, 2013

Binary Search

Binary search, a simple but yet effective algorithm to search and still used at many places.

Having a complexity of (1+lg N)

Goal: Given a Sorted array and a Key, find the index of the key in an array?

Binary Search:

  • Compare key against middle entry
  • Too Small, Go left.
  • To Big, Go right.
  • Equal, found.

Java Code for the above algorithm is as:

public static int binarySearch(int[] a, int key){
		int lo = 0;
		int hi = a.length - 1;
		while(lo <= hi){
			int mid = lo + (hi-lo)/2;
			if(key < a[mid])		hi = mid - 1;
			else if(key > a[mid])	lo = mid + 1;
			else return mid;
		}
		return -1;
}
December 20, 2012

Why java calls `toString()` on `println()`

I know that calling an println(Object o) actually works as println(o.toString()) thing before but, today Found an implementation of println() at GrepCode for openjdk.

Here is what i found there :

Prints an Object and then terminate the line. This method calls at first String.valueOf(x) to get the printed object’s string value, then behaves as though it invokes print(java.lang.String) and then println().
Parameters:
x The Object to be printed.
819
820 public void println(Object x) {
821 String s = String.valueOf(x);
822 synchronized (this) {
823 print(s);
824 newLine();
825 }
826 }

which lead to String.valueOf(x) :

Returns the string representation of the Object argument.
Parameters:
obj an Object.
Returns:
if the argument is null, then a string equal to “null”; otherwise, the value of obj.toString() is returned.
See also:
Object.toString()

2901 public static String valueOf(Object obj) {
2902 return (obj == null) ? "null" : obj.toString();
2903 }

November 24, 2012

Nth Root

Same as my Previous Post from SQRT Implementation, We can also find Nth Root Using the Newton-Raphson.

Here it Goes,

int n = Integer.parseInt(request.getParameter("times"));
double A = Double.parseDouble(request.getParameter("number"));
double p = .001;

if(A < 0){
      System.err.println("A < 0");// we handle only real positive numbers
}else if(A == 0){
      System.err.println("A = 0");// we handle only real positive numbers
}
double x_prev = A;
double x = A / n;  // starting "guessed" value...

while(Math.abs(x - x_prev) > p)
{
      x_prev = x;
      x = ((n - 1.0) * x + A / Math.pow(x, n - 1.0)) / n;
}
November 19, 2012

Made a High-Low Game of Cards today

Finally Yesterday, after learning Some Array and Some Card Algorithms, Made a High-Low Card Game, which I like most while Playing a Poker. Currently It’s NOT in a GUI form, but I’ll try to give it Some better looking GUI. Hope So… :)

Below is the code for the Game



import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

public class CardGuess {
	String[] suit={"club","dimond","hearts","spades"};
	String[] rank={"2", "3", "4", "5", "6", "7", "8", "9", "10", "Jack", "Queen", "King", "Ace"};
	int SUITS=suit.length;
	int RANKS=rank.length;
	int N=SUITS*RANKS;
	String[] deck;
	public CardGuess(){
		deck=new String[N];
		for(int i=0;i<RANKS;i++){
			for(int j=0;j<SUITS;j++){
				deck[SUITS*i+j]=rank[i]+" of "+suit[j];
			}
		}
	}
	public void suffle(){
		for(int i=0;i<N;i++){
			int r= i+(int) Math.random()*(N-i);
			String t=deck[r];
			deck[r]=deck[i];
			deck[i]=t;
		}
	}
	public void show(){
		for(int i=0;i<N;i++){
			System.out.println(deck[i]);
		}
	}
	public String giveRandomOne(){
		return deck[(int) (Math.random()*N)];
	}
	public int compareCard(String firstCard,String secondCard){
		String[] st=firstCard.split(" ");
		firstCard=st[0];
		st=secondCard.split(" ");
		secondCard=st[0];
		CardGuess cg=new CardGuess();
		if(cg.indexOf(firstCard)>cg.indexOf(secondCard)){
			return 1;
		}
		else if(cg.indexOf(firstCard)<cg.indexOf(secondCard)){
			return -1;
		}
		else{
			return 0;
		}
		
	}
	public int indexOf(String str){
		for(int i=0;i<=RANKS;i++){
			if(str.equalsIgnoreCase(rank[i]))
				return i;
		}
		return 0;
	}
	public static void main(String ar[]){
		int Point=0;
		CardGuess cardGuess=new CardGuess();
		
		String firstCard=cardGuess.giveRandomOne();
		String secondCard=cardGuess.giveRandomOne();
		while(secondCard.equals(firstCard)){
			secondCard=cardGuess.giveRandomOne();
		}
		System.out.println("firstCard: "+firstCard+"\nSecondCard: "+secondCard);
		BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
		String userInput = "";
		while(!(userInput.equalsIgnoreCase("exit"))){
			try {
				System.out.println("Next Card Will Be up OR down?");
				userInput=br.readLine();
			} catch (IOException e) {
				e.printStackTrace();
			}
			
			int i=cardGuess.compareCard(firstCard, secondCard);
//			System.out.println(i);
			if((userInput.equalsIgnoreCase("up")&&i<0)||(userInput.equalsIgnoreCase("down")&&i>0)){
				Point+=10;
//				System.out.println("\n\n"+firstCard);
				System.out.println("Correct, Your Total Point is "+Point);
				firstCard=secondCard;
				System.out.println(firstCard);
				secondCard=cardGuess.giveRandomOne();
				while(secondCard.equals(firstCard)){
					secondCard=cardGuess.giveRandomOne();
				}
//				System.out.println(secondCard);
				continue;
			}
			else{
				
				System.out.println("GAME OVER"+"\nYour Total Point is "+Point);
				System.out.println(secondCard);
				Point=0;
				System.exit(0);
			}
		}
	}
}

November 4, 2012

SQRT Implementation

Newton’s method.

Sqrt.java uses a classic iterative technique that dates back to Heron of Alexandria in the first century. It is a special case of the more general Newton-Raphson method.Newton's method

To compute the square root of a positive number x: Start with an estimate t. If t is equal to x/t (up to machine precision), then t is equal to a square root of x, so the computation is complete. If not, refine the estimate by replacing t with the average of t and x/t. Each time we perform this update, we get closer to the desired answer.

public class SQRT {
  public static void main(String ar[]){
  BufferedReader read=new BufferedReader(new InputStreamReader(System.in));
  try {
   //read the number from user
      System.out.println("Please Enter the Num: ");
      double c=Double.parseDouble(read.readLine());
      double epsilon=1e-15; //relative error tolerance
      double t=c; //estimate of the square root of c

      //Repeatedly apply Newton update step until desired precision is achieved
      while(Math.abs(t - c/t) > epsilon*t){
          t=(c/t+t) / 2.0;
      }
      System.out.println(t);
   } catch (NumberFormatException e) {
   // TODO Auto-generated catch block
     e.printStackTrace();
   } catch (IOException e) {
   // TODO Auto-generated catch block
     e.printStackTrace();
   }

 }
}

July 10, 2012

Selection Sort

The selection sort improves on the bubble sort by reducing the number of swaps necessary from O(N^2) to O(N). Unfortunately, the number of comparisons remains O(N^2). However, the selection sort can still offer a significant improvement for large records that must be physically moved around in memory, causing the swap time to be much more important than the comparison time.


import java.util.Random;

public class SelectionSort {
	static int n=10;
	static int[] array=new int[n];
	public static void main(String ar[]){

		Random rand=new Random();

		for(int i=0;i<n;i++){
			array[i]=rand.nextInt(100);
		}
		System.out.println("Array Before Sorting: \n");
		for(int i=0;i<n;i++){
			System.out.print(array[i]+" ");
		}
		selectionSort(array);
		System.out.println("\n\nArray After Sorting: \n");
		for(int i=0;i<n;i++){
			System.out.print(array[i]+" ");
		}
	}
	private static void selectionSort(int[] array) {
		// TODO Auto-generated method stub
		int out, in, min;
		int nElems=array.length;
		for(out=0; out<nElems-1;out++){
			min = out;
			for(in=out+1; in<nElems; in++){
			        if(array[in] < array[min] )
					min = in;
			swap(out, min);
		}
	}

	private static void swap(int out, int min) {
		// TODO Auto-generated method stub
		int temp;
		temp=array[out];
		array[out]=array[min];
		array[min]=temp;
	}
}

July 6, 2012

Bubble Sort

Bubble Sort is a simple sorting Algorithm that works through repeatedly comparing the each pair of adjacent item and swapping them if they are in the wrong order, It pass through the list until no swaps are needed that means list is sorted. It’s not at all the preferred algorithm as it’s not efficient for sorting large lists.
A simple animation showing Bubble sort might help you to understand better.
Bubble Sort

import java.util.Random;


public class BubbleSort {
	public static void main(String ar[]){
		int n=10;
		Random rand=new Random();
		int[] array=new int[n];
		for(int i=0;i<n;i++){
			array[i]=rand.nextInt(100);
		}
		System.out.println("Array Before Sorting: \n");
		for(int i=0;i<n;i++){
			System.out.print(array[i]+" ");
		}
		bubbleSort(array);
		System.out.println("\n\nArray After Sorting: \n");
		for(int i=0;i<n;i++){
			System.out.print(array[i]+" ");
		}
	}

	private static void bubbleSort(int[] array) {
		for(int i=0;i<array.length;i++){
			for(int j=0;j<array.length-1;j++){
				if(array[j]>array[j+1]){
					int temp=array[j];
					array[j]=array[j+1];
					array[j+1]=temp;
				}
			}
		}
	}
}

April 9, 2012

Algorithms

Just started learning Algorithms, I think that will help to improve my logic.

Resources:

February 23, 2012

Python

Just started learning Python (inspiration: Udacity 101). Looks like a easy for beginners like me.

Let’s try and see what will happen..!! :)

મારા વિચારો, મારી ભાષામાં!

અમારી બીજી કોઇ ટૅગલાઇન નથી!

WordPress.com News

The latest news on WordPress.com and the WordPress community.

Follow

Get every new post delivered to your Inbox.