Showing posts from February, 2012

Read values from a file and Sort the numbers using merge sort and quick sort algorithm in Java

Merge sort algorithm
1. The length of the list is 0 or 1, and then it is considered as sorted.
2. Otherwise, divide the unsorted list into 2 lists each about half the size.
3. Sort each sub list recursively. Implement the step 2 until the two sub lists are sorted.
4. As a final step, combine (merge) both the lists back into one sorted list.

FileReader -Java Read File Line by Line in Java

The FileReader class makes it possible to read the contents of a file as a stream of characters. It works much like the FileInputStream except the FileInputStream reads bytes, whereas the FileReader reads characters. The FileReader is intended to read text, in other words. One character may correspond to one or more bytes depending on the character encoding scheme.

An Array of Linear list in java

Linked lists are among the simplest and most common data structures. They can be used to implement several other common abstract data types, including stacks, queues, associative arrays, andsymbolic expressions, though it is not uncommon to implement the other data structures directly without using a list as the basis of implementation. 

Operation and interface on linear list in java

Operations :
isEmpty() - Returns true if the List is empty ,false other wise.size() - Give the number of element in the list.get(theIndex) - Give the element with gives index.indexOf(theElement) - Determines the index of a given element.remove(theIndex) - Removes element with a given index and returns it.add(theIndex,theElement) - Add a given element so that new element has a specified index. 

The n-queens problem in Java

A classic combinatorial problem is to place n queens on an n × n chess board so that no queen threatens any other queen, that is, so that no two queens are on the same row, column, or diagonal. In order to reduce this solution space, it can now be assumed without loss of generality, that the ith queen is placed in the ith row, thereby avoiding those two queens can be in the same row. 

Knapsack Problem in Java

Knapsack problem : The knapsack problem or rucksack problem is a problem in combinatorial optimization: Given a set of items, each with a weight and a value, determine the count of each item to include in a collection so that the total weight is less than or equal to a given limit and the total value is as large as possible. It derives its name from the problem faced by someone who is constrained by a fixed-size knapsack and must fill it with the most useful items.

Maximum and Minimum using Divide and Conquer in Java

Divide-and-Conquer Min-Max
As we are dealing with sub problems, we state each sub problem as computing minimum and maximum of a sub array A[p . . q]. Initially, p = 1 and q = A.length, but these values change as we recursive  through sub problems.To compute minimum and maximum of A[p . . q]: Divide by splitting into two sub arrays A[p . .r] and A[r+1 . . q], where r is the halfway point of A[p . . q]. Conquer by recursively computing minimum and maximum of the two sub arrays A[p . .r] and A[r+1 . . q]. Combine by computing the overall minimum as the min of the two recursively computed minimum, similar for the overall maximum.