Multiset data structure implementation in java

Multiset  is a generalized version set structure.Similar to set, multiset only stores data values without  guarantee of any particular ordering of its contents. On the other hand, it allows storing of multiple items with the same value (ie. supports non-unique keys).

It can be implemented using list but for optimal result i.e O(1) hash table structure should be used. Otherwise it  takes steps, where is number of distinct elements stored.

Source Code (JAVA)
01. /**

02.* Multiset implemented using two lists (list of values, list of occurrences)

03.* @author Pavel Micka

04.* @param <ENTITY> type parameter of the contained value

05.*/

06.public class Multiset<VALUE> {

07. 

08.private List<VALUE> values;

09.private List<Integer> occurences;

10. 

set data structure implementation in java

Set refers an abstract data structure used for storing data elements. Analogy with the mathematical term set, it does not guarantee any particular order of the stored elements and contains every value at most once (i.e. contains only unique values).

Similarly we can define multiset (bag) – a set, which may contain each value more than once. we can implement disjoint,union and difference of these set like in set theory of mathematics.

Source Code(JAVA)

/**
 * Set implemented as a list (using ArrayList)
 * @author Pavel Micka
 * @param <ENTITY> Type parameter of the contained value
 */
public class Set<ENTITY> {
    private List<ENTITY> list;
    /**
     * Constructor
     * @param initialCapacity initial capacity of the underlying ArrayList
     */
    public Set(int initialCapacity){
        list = new ArrayList<ENTITY>(initialCapacity);
    }

Prune and Search Alogrithm and implemetation in java

Prune and search is a method for finding an optimal value by iteratively dividing a search space into two parts – the promising one, which contains the optimal value and is recursively searched and the second part without optimal value, which is pruned (thrown away). This paradigm is very similar to well know divide and conquer algorithms.




* Prune and search

* @param array array to be searched in

* @param index order of the searched value (indexed starting at 0)

.* @param left first elemenent, which can be touched

* @param right first element, which cant be touched

* @return n-th largest value

*/

public static int pruneAndSearch(int[] array, int index, int left, int right) {

int boundary = left;

for (int i = left + 1; i < right; i++) {

if (array[i] > array[left]) {

 //place after the pivot every value, which is larger than the pivot

swap(array, i, ++boundary);

}

}

Interpolation Search implementation in java

The interpolation search is an improvement of the binary search for instances, where the values in the array are ordered and uniformly distributed.

The difference between the binary and the interpolation sort is that the binary search always splits the the array in half and inspects the middle element. Interpolation search calculates a position , where the value should be placed in accordance to the distribution of values a splits the array at . If the array contains numbers and we are looking for 9 the binary search needs three steps – split at 5, split at 8, split at 9 (found). The interpolation search calculates the probable position (index 9) and immediately finds the value. The expected complexity of the interpolation search in .




/* Interpolation search

* @param array array with uniformly distributed values in ascending order

* @param value searched value

* @param from first index that might be touched

* @param to last index that might be touched

* @return index index of the searched value in the array, -1 if not found

*/

public static int interpolationSearch(int[] array, int value, int from, int to){

if(array[from] == value) return from;

else if(from == to || array[from] ==  array[to]) return -1; //not found

//probable position of the searched value

int index = from + ((to - from)/(array[to] - array[from])) * (value - array[from]);

if(array[index] == value) return index;//found

//continue in the right part of the array

else if(array[index] < value) return interpolationSearch(array, value, index + 1, to);

//continue in the left part of the array

else return interpolationSearch(array, value, from, index - 1);

}

"Hello World " servlet in Net Beans

By default there is no web application in Net Beans 7.1 so you have to install plugin of web application.In order to do that, go to tool>plugin.A window will pop-up where all updates,available plugins,downloaded, installed  plugins option are available.In order to install these plugins you must be connected to internet.

In available plugins,click reload catalog which will update available plugins.From the list select 

--web application

--Glassfish

--Css preview

 and install, it make take few minutes .After installation you need to restart Net beans IDE.

Now you are done. Go File>new project ,now you have option for JAVA web in category then select web application in project.click next,then give name for project and location for project to save.Then in next, select server from drop down list which is Glassfish that we installed before,you can add other server like tomcat instead.Select java EE version as java EE 6  and click finish.

connecting and using MySQL database in netbeans

1.Download and install MySQL server
2.Run MySQL server
3.Run NetBeans
4.Connect MySQL with NetBeans
5.Edit database in Net Beans MySQL editor

1.Download and install MySQL server
   First step  is easy and simple ,just  download MySQL server from http://dev.mysql.com/downloads/mysql/  as per your system platform (e.g. 32-bit or 64-bit or mac or Ubuntu ) and install.After installation you have to configure MySQL server,leave all as default ,you just set password.

2.Run MySQL server

   Now for test  run installed  MySQL server console(command line client ).Enter password and you will see welcome secren.Type " SHOW  databases; " as command which give output of table of  inbuilt databases and table name is Databases.