Showing posts with label Data structure. Show all posts
Showing posts with label Data structure. Show all posts

## Saturday, 18 July 2015

### HeapSort

Heap sort is very easy to implement and its time complexity is O(n log(n)).

### Heap Basics Extension - Priority Queue

Priority Queue is very commonly used in operating system to schedule task, priority Queue can very easily and very effectively can implement in Heap.

### Insert A new Key in Heap :

Start from end of heap and find appropriate position then insert.

Heap-Insert(A,key)
1. Heap-Size[A] <- Heap-Size[A]+1
2. i=Heap-Size[A]
3. while(i>1 and A[parant(i)]<key)
• A[i]<-A[Parant(i)]
• i=Parent(i)
4. A[i]=Key
Note: If We remove root node then to hepify again we just have to call heapify(A,1)

### Heap Basics

Heap is also called Left Complete binary tree. i.e Binary tree with some of rightmost node removed.
It is very efficient for priority Queue implementation. MaxHeap

#### Heap Type:

1. Minimum Key Heap: Root node is always minimum.
2. Maximum key Heap:  Root node is always maximum.

## Sunday, 5 April 2015

### Factorial of a Large Number

Idea : - we are going to find factorial of a large number number. Factorial of large number

• store num in array such that each element of array is a single digit.
• Decrease num by 1 and multiply num with each element of array and then for each element we store them as the rightmost digit remains at it's location while the remaining part is added to the next element and the last element is again stored as single digit and the remaining is stored on next till remaining part becomes 0.

## Queue:

A queue is a linear list of element in which
è Deletion can take place at one end that is Front .

è Insertion take place at one end that is Rear ..

That's why Also known as FILO :-first in last out

### Queue:

A queue is a linear list of element in which
è Deletion can take place at one end that is Front .

è Insertion take place at one end that is Rear ..

That's why Also known as FILO :-first in last out

## Monday, 10 March 2014

### AMICABLE PAIRS

Two numbers form Amicable Pairs  if sum of proper divisors of  1st is equal to the 2nd and vice-versa.It is assumed that these two numbers should be distinct,

Example : Let two number 220 And 284 ,
Sum of proper Divisor of 220 := 1+2+4+5+10+11+20+22+44+55+110 = 284
Sum of Proper Divisor of 284 :=1+2+\$+71+142=210 .
That's Why 220 & 284 form amicable number pair .

Note : ( 220 , 284 ) smallest Amicable Number Pair .

## Friday, 1 November 2013

### Multidimensional Array

One-Dimensional Array
Two-Dimensional Array
Three-Dimensional Array

Some programming Language allows as many as 7 dimension
\

Two-Dimensional Array
A Two-Dimensional m x n array A is a collection of m . n data elements such that each element is specified by a pair of integer (such as J, K) called subscript with property that
1 ≤ J ≤ m   and 1 ≤ K ≤ n

### Linear  Arrays

A linear array is a list of a finite number of n homogeneous data elements ( that is data elements of the same type) such that
The elements are of the arrays are referenced respectively by an index set consisting of n consecutive numbers
The elements of the arrays are stored respectively in successive memory locations .
The number n of elements is called the length or size of the array.
The index set consists of the integer 1, 2, … n
Length or the number of data elements of the array can be obtained from the index set by
Length = UB – LB + 1 where UB is the largest index called the upper bound and LB is the smallest index called the lower bound of the arrays .

### Data Structure vs Storage Structure

Data Structure : The logical or mathematical model of a particular organization of data

Storage Structure : Representation of a particular data structure in the memory of a computer
There are many possible storage structure to a particular data structure
Ex: there are a number of storage structure for a data structure such as array
It is possible for two DS to represented by the same storage structure

### Search & Delete operation on Binary search tree {BST}

Algorithm
Perform search for value X
If X is a leaf, delete X
Else   // must delete internal node
a) Replace with largest value Y on left subtree
OR smallest value Z on right subtree
b) Delete replacement value (Y or Z) from subtree Observation
O( log(n) ) operation for balanced tree

Deletions may unbalance tree

Example Deletion (Leaf)
Delete ( 25 )

### Binary Search Tree (BST)

Suppose T is a binary tree
Then T is called binary search tree if each node N of T  has the following property

The value at N is greater than every value in the left sub-tree of N and is less than every value in the right sub-tree of N

## If a matrix contains lots of ZEROS , then to save time & space,we use a special type of matrix ,known as SPARSE MATRIX.....

It stores only the NON-ZERO Elements only....
It can be created by two ways
1)Using array

Simple e.g-

Let's write a c programe to get the sparse matrix of a given matix [In array]

## Saturday, 26 October 2013

### Quick sort Recursive Approch

There are many way to sort a list using quick sort concept .i.e recursive way & iterative way. quick sort
Recursive Approach
1. choose a no in the list a pivote
2. now sort list such that no less then pivote no. come on left of it & other on right
3. In above steps list break in two part . let left list as brand new list and repeat all steps(1,2,3).
4. do similar operation on right list as on left.
Now how to do Steps 2. there are many ways I did mention few of them..

## Tuesday, 22 October 2013

### Selection Sort (concept & algorithm)

Suppose an array A with N elements is in memory. Selection sort works as follows

First find the smallest element in the list and put it in the first position. Then, find the second smallest element in the list and put it in the second position  and so on.

Pass 1: Find the location LOC  of the smallest element in the list A, A, … A[N]. Then interchange A[LOC] and A. Then: A is sorted
Pass 2: Find the location LOC  of the smallest element in the sublist A, A, … A[N]. Then interchange A[LOC] and A. Then: A,A  is sorted since A <= A.
Pass 3: Find the location LOC  of the smallest element in the sublist A, A, … A[N]. Then interchange A[LOC] and A. Then: A, A,A  is sorted, since A <= A.

### Insertion Sort (concept & algorithm) insertion like cards

An array A with N elements A, A … A[N] is in memory

Insertion Sort scan A from A to A[N] inserting each elements A[k] into its proper position in the previously sorted subarray A, A, …. A[K-1]

Pass 1: A by itself is trivially sorted
Pass 2: A is inserted either before or after A so that A, A is sorted
Pass 3: A is inserted in its proper place in A, A, that is before A, between A and A or after A so that A, A, A is sorted

Pass 4: A is inserted in its proper place in A, A, A so that A, A, A, A  is sorted.

### Quick Sort (concept & algorithm )

Quick sort is an algorithm of the divide-and-conquer type

The problem of sorting a set  is reduced to the problem of sorting two smaller sets.

## Quick Sort Approach :

### Bubble Sort ( concept & algorithm )

The oldest and simplest sort in use.

Unfortunately, also the slowest.

Works by comparing each item in the list with the item next to it, and swapping them if required.

The algorithm repeats this process until it makes a pass all the way through the list without swapping any items.

This causes larger values to "bubble" to the end of the list while smaller values "sink" towards the beginning of the list.

### Sorting

Sorting refers to the operation of arranging data in some order such as increasing or decreasing with numerical data or alphabetically with character data

Complexity of Sorting Algorithm

The complexity of a sorting algorithm measures the running time as a function of the number on n of items to be sorted .

Each sorting algorithm S will be made up of the following operations, where A1, A2 , ……, An  contain the items to be sorted and B is an auxiliary location:
(a) Comparisons : which test whether Ai < Aj  or test Ai < B
(b) Interchange, which switch the content of Ai and  Aj  or of Ai  and B
(c) Assignments, which set B := Ai  and then set Aj  := B or Set Aj   := Ai

## Monday, 21 October 2013

### Search & Deletion in Binary search Tree ( BST )

In previous discussion we discus about Binary search tree Now we have to do some basic operation on binary search tree.

#### Searching a element : it is not a tough job in BST .follow simple algorithm

>> compare root node data with require data if equal search complete otherwise if less that root node move to left else move to right child.
follow this steps for all nodes until NULL encounter it is condition for unsuccessful search.

Blogger Widgets