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

}

}

Depth First Search Algorithm and implementation in c++

DFS is the basic tree search technique in which goal,data is searched by moving downward until a leaf,end node, is reached.Then it backtrack and repeat the moving down to leaf process.This process is repeated until the searching data is found.

Algorithm

An algorithm for the depth – first search is the same as that for breadth first search except in the ordering of the nodes.

1. Place the starting node s on the top of the stack.
2. If the stack is empty, return failure and stop.
3. If the element on the stack is goal node g, return success and stop. Otherwise,
4. Remove and expand the first element , and place the children at the top of the stack.
5. Return to step 2.
    
   #include <iostream>

   #include <ctime>

   #include <malloc.h>

   using namespace std;

   struct node{

       int info;

       struct node *next;

   };

    

Breadth-First Search Algorithm and implementation in c++

BFS is most useful searching technique in database.In this technique,form the tree of data, corresponding child nodes of current state node is selected first during the searching process.Then in next step the childrens' of these selected child nodes will be searched.In this way exploring all nodes at a given depth before proceeding to the next level this searching method is implemented.

Algorithm

BFS uses a queue structure to hold all generate but still unexplored nodes. The order in which nodes are placed on the queue for removal and exploration determines the type of search. The BFS algorithm proceeds as follows.

1. Place the starting node s on the queue.
2. If the queue is empty, return failure and stop.
3. If the first element on the queue is a goal node g, return success and stop Otherwise,
4. Remove and expand the first element from the queue and place all the children at the end of the queue in any order.
5. Return to step 2.
   Source Code 
   #include <iostream>

   #include <ctime>

   using namespace std;

   struct node {

       int info;

       node *next;

   };

   
   

Very Important Sorting Algorithms

Selection  Sort

Insertion Sort

Shell Sort

Merge Sort

Radix sort

Selection  Sort

      i)Declare and initialize necessary variables such as array [ ] , i, j , large, n .
      ii)For ( i=n-1 ; i > 0 ; i -- )  repeat following steps
               large=x[ 0 ]
               index=0
              ii.a  For ( j=1;j<=i ; j++)
                 IF (x[ j ]>large)
                         large=x[ j ]
                         index=j
             ii.b x[index] =x[ i ]
                          x[ i ]=large
      iii)Display the sorted array'

Insertion Sort

    i) i)Declare and initialize necessary variables such as array [ ] , i, j , large, n 
    ii)Insert each x[ ] into sorted file i.e.
           for  k=1 to k<n ,repeat
                temp=x[ k ]
                ii.a Move down one position all elements greater than temp i.e.
                      for ( i=k-1 ; j>=0  && temp<x [ i ] ; i ++)
                             x[i+1]=x[ i ]
                 ii.b   x[i+1]=temp
     iii)Display the sorted array
note:: in above algorithm we take x[0] as sorted file initially.

What is Hufffman Algorithm?

 Huffman Algorithm is an encoding technique for symbols where most frequently occurring symbols are represented with short length bit strings and least frequently occurring symbols are represented with long bit strings.


Algorithm
 Huffman(c: symbols a[i] with frequencies w[i]=1,2,3.......n)

F: forest of n rooted trees,each consisting of the single vertex a[i] and assigned weight w[i] in ascending order of w[i] while F is not a tree.

i)Start
  Replace the rooted trees T and T ' of least weight from F with w(T ) >= w(T ') with a tree hvaing a new root that has T as its left sub tree and T ' as its right sub tree label new edge to T with 0 and new edge to T ' with 1
Assign w(T) + w(T ') as weight of new tree.

Binary Tree and its Implementation in Database

A binary tree is a finite set of elements that is either empty or is partitioned into three disjoint subset of tree.The first subset contains a single element called the root and other two are left and right sub trees which

can be also empty.Each element of a binary tree is called nodes of the tree.

A rooted tree is called binary tree if every internal vertex has no more than two children.

Types of Binary tree:_

a)Strictly / fully binary tree

b)complete binary tree

c)almost complete binary tree

what TREE refers to in DataBase

Tree is a non-linear data structure which consists of non-empty set of vertices(or nodes) and a set of edges where each nodes are connected to each other with no multiple edges or loops(i.e. no simple circuits)


Terminologies on tree:

Implementation of Linked List

Linked list is the special list of data elements linked to one another.Logical ordering is represented by having each elements pointing to next element.Each element in called node which has two fields-info to store data and next to point next node.It can be easily implemented to grow or shrink depending upon operation mode.Entire lined list is accessed from an external  pointer that contains the address of first node but it is not included in the linked list.The next address of last node contains special value called NULL represented by electrical ground symbol.Linked  list with no node is called EMPTY linked list.

In c,we can create  a node using structure as
                 struct node{
                               int info;
                              node *next;
                              }list;

Following operation can be done to linked list
1)Inserting Nodes to the front of  the Linked-List

2)Inserting  Nodes at end of the Linked-List

3)Inserting node after the given Node

4)Inserting node before the given node

5)Deleting the first Node

6)Deleting the last Node

7)Deleting the node after given node

8)Deletion the node before given node

Data Structure and Algorithm of QUEUE

A queue is an ordered collection of items from which items may be deleted at one end(called front and head of the queue) and into which items may be inserted at the other end (called the rear end on tail of the queue). It is First-In-First-Out(FIFO).There are two types of queue-Linear Queue and Circular Queue.

En-queue is the process of appending data to queue.

De-queue is the process of removing data from queue.

Algorithms for Linear Queue

What are STACK in DataBase and its alogrithms

A stack is an ordered collection of items into which new items may be inserted and from which items can be deleted at one end,called top of stack.It is First In Last Out(FILO) type of data structure.
Stack can be thought as pile of plates one on other.One which is put first stay at last or bottom of pile and one that is pile last is always on top.Also to take out a plate form it one which is  on top is remove first and other later.That's why it is called FILO. 

Push is the process of adding data on top of stack.
Pop  is the process of removing data from top of stack.

Stack Algorithms:

There are basically two methods implement stack:-

"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.