1/27/12

Minimax Algorithm Tutorial

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. 



1/26/12

Find the largest sum in an Array Problem

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);
    }
}


1/16/12

Counting Sort Algorithm with Example

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. 

1/12/12

Advance I/O Streams in Java

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.


1/4/12