Showing posts with label

**Data structure**. Show all postsShowing posts with label

**Data structure**. Show all posts## Saturday, 18 July 2015

### 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)**

**Heap-Size[A] <- Heap-Size[A]+1****i=Heap-Size[A]****while(i>1 and A[parant(i)]<key)****A[i]<-A[Parant(i)]****i=Parent(i)****A[i]=Key**

**Note: If We remove root node then to hepify again we just have to call heapify(A,1)**

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

## Friday, 25 July 2014

## 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 .**

###
*C Code to find Amicable Number in GIven Range : *

## 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 structure : Array

### 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

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

## Tuesday, 29 October 2013

### Sparse Matrix in C

## 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

2)Using Linklist

It can be created by two ways

1)Using array

2)Using Linklist

**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**- choose a no in the list a pivote
- now sort list such that no less then pivote no. come on left of it & other on right
- In above steps list break in two part . let left list as brand new list and repeat all steps(1,2,3).
- do similar operation on right list as on left.

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

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[1], A[2], … A[N]. Then interchange A[LOC] and A[1]. Then: A[1] is sorted

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

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

### Insertion Sort (concept & algorithm)

insertion like cards |

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

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

Pass 1: A[1] by itself is trivially sorted

Pass 2: A[2] is inserted either before or after A[1] so that A[1], A[2] is sorted

Pass 3: A[3] is inserted in its proper place in A[1], A[2], that is before A[1], between A[1] and A[2] or after A[2] so that A[1], A[2], A[3] is sorted

Pass 4: A[4] is inserted in its proper place in A[1], A[2], A[3] so that A[1], A[2], A[3], A[4] is sorted.

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

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

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

Complexity of Sorting Algorithm

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.

Subscribe to:
Posts (Atom)