Minimax Algorithm Tutorial

Posted by Farhan Khwaja 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. 

Find the largest sum in an Array Problem

Posted by farhan khwaja 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);
    }
}

Counting Sort Algorithm with Example

Posted by Farhan Khwaja 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. 

Advance I/O Streams in Java

Posted by Farhan Khwaja 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.

Finalize(), Finally and Final in Java

Posted by farhan khwaja 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