Friday, January 27, 2012

Minimax Algorithm Tutorial

Posted by on Friday, January 27, 2012
There are plenty of application in AI but games are the most important thing in today's world and nowadays every OS comes with two player games like chess, checkers etc. So there are algorithm that help to design these games. These algorithm not only just help in making games but they also help in making the life of the player(i.e. user) tough in the game-play. So Minimax Algorithm is one such kind of algorithm. 


Thursday, January 26, 2012

Find the largest sum in an Array Problem

Posted by on Thursday, January 26, 2012
You are given an array of integers (both positive and negative). Find the continuous sequence with the largest sum. Return the sum.

EXAMPLE

input: {2, -8, 3, -2, 4, -10}
output: 5 [ eg, {3, -2, 4} ]
Answer  :


You might have identified that dynamic programming is appropriate for this problem. Let’s write down the recurrence:

sum(i,j) = max_k sum(i,k) + sum(k+1, j)

This will give an O(N^3) solution. A brute force summing of the sequences will give the same time.

A simple linear algorithm will work by keep track of the current subsequence sum. If that sum ever drops below zero, that subsequence will not contribute to the subsequent maximal subsequence since it would reduce it by adding the negative sum.




public class SumArr {

    public static void main(String[] args) {
        int a[] = {6,-8, 3, -2, 4};
        int maxsum = 0;
        int sum = 0;
        for (int i = 0; i < a.length; i++) {
        sum += a[i];
        if (maxsum < sum) {
        maxsum = sum;
        } else if (sum < 0) {
        sum = 0;
        }
        }
        System.out.println(maxsum);
    }
}

Monday, January 16, 2012

Counting Sort Algorithm with Example

Posted by on Monday, January 16, 2012
After a long interval of time I am writing a post on ALGORITHMS. After writing posts on Heap Sort, Merge Sort and Insertion Sort, I decided to write on Counting Sort.

Counting sort is an algorithm for sorting a collection of objects according to keys that are small integers; that is, it is an integer sorting algorithm. It is a linear time sorting algorithm used to sort items when they belong to a fixed and finite set. 

Thursday, January 12, 2012

Advance I/O Streams in Java

Posted by on Thursday, January 12, 2012
A Stream is a flow of data from the source to a sink. Source and sink are also called input and output streams, respectively. 

The I/O Streams are of two Kinds :
1. Byte Streams 
2. Character Streams

Normally the term stream refers to the byte stream and the terms  reader and writer refer to the character stream.

Thursday, January 5, 2012

Finalize(), Finally and Final in Java

Posted by on Thursday, January 5, 2012
There's some confusion in the mind of an intermediate level programmer about finalize(),finally and final in java. So to remove that confusion from each and everyone's mind I thought of writing a post on it.

finalize() :  A Method
finally : A Clause in Try-Catch
final :  Keyword in java

© 2010 Code 2 Learn