Active In SP
Joined: Sep 2010
29-12-2010, 04:43 PM
WORST CASE ANALYSIS OF SHELL SHORT
Although shell sort is simple to code, the analysis of its running time is quite another story.
The running time of shellsort depends on the choice of increment sequence.
worst case analysis of shell sort.ppt (Size: 2.1 MB / Downloads: 119)
Active In SP
Joined: Jan 2012
09-01-2012, 10:42 AM
Data may be organized in many different ways.
The logical or mathematical model of a particular organization is called a data structure.
It can also be defined as the choice of representation of data.
The choice of a data model depends on two considerations :
It must be rich enough to mirror the actual relationship of data in the real world.
It should be simple enough that one can effectively process the data when necessary
Data structures can be classified as :
A data structure is said to be linear if its elements form a sequence.
Examples for linear structure include arrays and linked lists.
Trees and graphs are examples of nonlinear structures.
Linear Data structures
The operations performed on linear structures are :
The simplest type of data structure is a one-dimensional array or list or linear array.
Linear array is a list of finite number (n) of similar data elements referenced respectively by a set of n consecutive numbers , usually 1,2…..n.
If we choose a name A for the array , then the elements of A are denoted by subscript notation
or by the parenthesis notation
or by the bracket notation
A,A………. , A[n]
The value K in A[K] is called a subscript and A[K] is called a subscripted variable.
The elements of an array are stored in consecutive memory locations.
A linear array LA can be pictured as
2 1 2 3 4 5
LB :- Lower Bound
UB :- Upper Bound
Length of an array :- UB – LB + 1
LOC(LA[K]) :- Address of the element LA[K] of the array LA
Base (LA) :- Address of the first element of LA.
LOC (LA [K]) =Base (LA) + w (K-lower bound) ,where w is the number of words per memory cell for the array LA.
Traversing Linear Arrays
Let LA be a collection of elements stored in memory of the computer. Suppose we want to print the contents of the array or to count the number of elements of LA with a given property. This can be accomplished by traversing LA ,that is by accessing and processing each element of exactly once.
Here LA is a linear array with lower bound LB and upper bound UB. This algorithm traverses LA applying an operation to each element of LA.
[Initialize counter] Set K = LB.
Repeat steps 3 and 4 while K<=UB
[Visit Element] Apply process to LA[K].
[Increment counter.] K = K+1.
End of step 2 loop.
Suppose LA is an array containing 5 names in alphabetical order
(Inserting into a Linear Array) INSERT(LA,N,K,ITEM)
Here LA is a linear array with N elements and K is a positive integer such that K<=N. this algorithm inserts an element ITEM into the Kth position in LA.
[Initialize counter.] Set J=N.
Repeat steps 3 and 4 while J>=K.
[Move Jth element downward.] Set LA[J+1] = LA[J].
[Decrease Counter.] Set J = J-1.
[End of step 2 loop.]
[Insert element.] set LA[K] = ITEM.
[Reset N] Set N= N + 1.
Suppose we want to delete an element “smith” from the array.
(Deleting from a Linear array)DELETE(LA,N,K,ITEM)
Here LA is a linear array with N elements and K is a positive integer such that K<=N. This algorithm deletes the Kth element from LA.
Set ITEM = LA[K]
Repeat for J=K to N-1:
[Move J+1 th element upward] Set LA[J] = LA[J+1].
[End of loop.]
[Reset the number N of elements in LA.] Set N=N-1
Let A be a collection of data elements in memory and suppose a specific ITEM of information is given. Searching refers to the operation of finding the location LOC of ITEM in A or printing some message that ITEM does not appear there.
The search is said to be successful if ITEM does appear in A and unsuccessful otherwise.
There are different searching techniques
Binary search is more efficient than linear search. It take lesser time for execution.
The complexity of searching algorithms is measured in terms of the number of comparisons required to find ITEM in array .
Suppose A is an array with N elements.
To search for a given item in A , compare ITEM with each element of A one by one.
This method , which traverses A sequentially to locate ITEM , is called linear search or sequential search.
(Linear search) LINEAR(A,N,ITEM,LOC)
Here A is a linear array with N elements, and ITEM is a given item of information. This algorithm finds the location LOC of ITEM in DATA , or sets LOC=0 if search is unsuccessful.
[Insert ITEM at the end of A]. Set A[N+1]=ITEM.
[Initialize Counter] Set LOC=1.
[Search for ITEM]
Repeat while A[LOC] != ITEM
[End of loop]
[Successful?] If LOC=N+1 , then Set LOC=0.
Suppose A is an array which is sorted in increasing numerical order or alphabetically.
Then there is an extremely efficient searching algorithm, called binary search.
The algorithm compares ITEM with the middle element A[MID] where MID is obtained by
If A[MID]=ITEM , then search is successful and set LOC=MID. Otherwise a new segment of A is obtained as follows:
If ITEM<A[MID], then ITEM can appear only in the left half of the segment : A[BEG],A[BEG+1],…….A[MID-1]
So reset END = MID-1 and search again.
If ITEM>A[MID], then ITEM can appear only in the right half of the segment : A[MID+1],A[MID+2]……..A[END].
So reset BEG=MID+1 and search again.
(Binary search) BINARY(A,LB,UB,ITEM,LOC)
Here A is a sorted array with a lower bound LB and upper bound UB, and ITEM is a given ITEM of information. The variables BEG,MID and END denote, respectively the beginning, end and middle locations of a segment of elements of A. This algorithm finds the location Loc of ITEM in A or sets LOC=NULL.
[Initialize segment variables.]
Set BEG=LB,END=UB AND MID = INT((BEG+END)/2)
Repeat Steps 3 and 4 while BEG<= END and A[MID]!=ITEM
If ITEM<A[MID], then:
Set END= MID – 1
Set BEG = MID + 1
[End of If.]
Set MID = INT((BEG+END)/2)
[End of step2 loop.]
If A[MID]=ITEM , then
Set LOC= MID
[End of If]
Consider an array with 5 elements :
Let ITEM= 76
12 , 15 , 20 , 23 , 32 , 45 , 54 , 76 , 98 beg=1,end=9 ,mid=5
Limitations of Binary Search
Even if the binary search algorithm is so efficient it requires two conditions :
The list must be sorted and
One must have direct access to the middle element in any sub list .
This means that one must essentially use a sorted array to hold data.
But keeping data in sorted array is normally very expensive when there are many insertions and deletions.
Let A be a list of n numbers. Sorting A refers to the operation of rearranging the elements of A so that they are in increasing order. A<A…..<A[N]
Compare A and A and arrange them in desired order, so that A<A. Then compare A and A and arrange them so that A<A.Continue until we compare A[N-1] with A[N]. This step involve N-1 comparisons.
Repeat step 1 with one less comparison .That is ,now we stop after we compare and rearrange A[N-2] and A[N-1]
Step N-1. Compare A with A and arrange them so that A<A
After N-1 steps , the list will be in sorted order.
(Bubble Sort) BUBBLE (A,N)
Here A is an array with N elements. This algorithm sorts the elements in A.
Repeat steps 2 and 3 for K=1 to N-1.
Set PTR=1[Initializes a pointer PTR.]
Repeat while PTR<=N-K [Executes pass]
If A[PTR]>A[PTR+1], then :
Interchange A[PTR] and A[PTR+1].
[End of If]
[End of inner loop]
[End of outer loop]
32 , 27 , 51 ,66 , 23, 13,85,57
Complexity of Algorithms
An algorithm is a well-defined list of steps for solving a particular problem.
The time and space it uses are two major measures of the efficiency of the algorithm.
The complexity of an algorithm is the function which gives the running time or space in terms of the input size.
Complexity of Linear Search
In linear search we read each item in the list one at a time and compare it with the item to be searched.
The time required to execute this algorithm is proportional to the number of comparisons.
The average number of comparisons required
in a list of n elements = n/2.
=> complexity of linear search , C (n)=n/2.
Linear arrays in which each element is referenced by a single subscript is called a one – dimensional array.
Arrays in which elements are referenced by more than one subscript is called multi-dimensional arrays.
A two-dimensional array A is a collection of m*n elements such that each element is specified by a pair of subscripts A [i][j]
Representation of 2-D arrays
A 2-D array is stored in memory by a block of m*n sequential memory locations.
The programming language will store the array A either
Column by column (column-major order)
Row by row (row-major order)
For a one-dimensional array computer uses the formula
LOC(A[K])=Base (A) +w(K-1)
to find the address of A[K].
For a 2-D array the address of A[J,K] is found out using the formula
(Column major order)
LOC(A[J,K] = Base (A)+[N(J-1)+(K-1)]
Stacks and Queues
The linear lists and arrays allow one to insert and delete elements at any place in the list : at the beginning , at the end or in the middle.
But there are certain situations in computer science when one wants to restrict insertions and deletions so that they can take place only at the beginning or the end of the list , not in the middle.
Two of the data structures that are useful in such situations are stacks and queues.
A Stack is a linear structure in which items may be added or removed only at one end.
A stack is a homogeneous collection of items of any one type, arranged linearly with access at one end only, called the top.
Formally this type of stack is called a Last In, First Out (LIFO) stack.
Data is added to the stack using the Push operation, and removed using the Pop operation.
Consider the following example :
Operations on Stack
Two basic operations associated with stack include :
Push :- term used to indicate insertion.
Pop :- term used to indicate deletion.
Suppose the following 5 elements are to be inserted or pushed on to the stack:
a, b ,c ,d ,e
Operations on Stack
The elements from a stack are poped in the reverse order.
Elements are poped in the following order.
Array Representation of Stack
Stacks may be represented in the computer in various ways ,usually by means of a one-way list or a linear array.
Stack can be maintained by a linear array STACK, a variable TOP , which contains the location of the top element of the stack and a variable MAXSTK which gives the maximum number of elements that can be held by the stack.
The condition TOP=0 or TOP=NULL will indicate that the stack is empty.
This procedure pushes an ITEM onto stack.
[Stack already filled?]
if TOP=MAXSTK ,then Print : OVERFLOW , and Return
set TOP=TOP+1[Increases TOP by 1.]
Set STACK[TOP] =ITEM. [Inserts ITEM in new TOP position.]
This procedure deletes the top element of the stack and assigns it to the variable ITEM
[Stack has an item to be removed?]
if TOP=0 , then print UNDERFLOW and Return.
Set ITEM = STACK[TOP].[ Assigns TOP element to ITEM]
Set TOP= TOP – 1 .[Decrease TOP by 1]
How do we use lists?
In many cases, we want to use a list, but we only want a limited subset of its operations
example: Use a list to store a waiting line of customers for a bookstore. As each customer arrives, place him/her at the end of the line. Serve customers in the order that they arrived.
Which list methods do we need here, and which do we not need?
Common idiom: "FIFO"
Many times, we will use a list in a way where we always add to the end, and always remove from the front (like the previous example)
The first element put into the list will be the first element we take out of the list
First-In, First-Out ("FIFO")
Let's create a new type of collection which is a limited version of List, tailored to this type of usage: a Queue
A queue is a linear list in which items may be added at one end and items may be removed only at the other end.
Deletions can take place only at one end , called the front , and insertions can take place only at the other end , called the rear.
Queues are also called first-in-first-out lists , since the first element in a queue will be the first element out of the queue. In other words , the order in which elements enter a queue is the order in which they leave.
Representation of Queues
Queues may be represented in various ways , usually by means of one-way lists or linear arrays.
Queues will be maintained by an array QUEUE and two pointer variables , FRONT, containing the location of the front element and REAR , containing the location of the rear element of the queue.
The condition FRONT=NULL indicates that the queue is empty.
offer or enqueue: add an element to the back
remove or dequeue: remove and return the element at the front
peek: return (but not remove) front element
peek on an empty queue returns null
We can treat the array holding the queue elements as circular (joined at the ends)
Elements were added to this queue in the order 11, 22, 33, 44, 55, and will be removed in the same order
Use: front = (front + 1) % Queue.length;and: rear = (rear + 1) % Queue.length;
Full and empty queues
If the queue were to become completely full, it would look like this:
If we were then to remove all eight elements, making the queue completely empty, it would look like this:
This procedure inserts an element ITEM into a queue.
[ Queue already filled?]
If FRONT=1 and REAR=N , or if FRONT=REAR+1, then:
Write : OVERFLOW AND Return.
[ Find new value of REAR]
if FRONT=NULL , then [Queue initially empty]
set FRONT=1 and REAR=1.
Else if REAR=N then :
[ End of if structure.]
Set QUEUE[REAR]=ITEM. [This inserts new element]
Joined: Jul 2011
01-02-2012, 12:03 PM
Data structre.pptx (Size: 46.62 KB / Downloads: 50)
Types of data structures
1. According to nature of Size:
(i) Static data structure
(ii) Dynamic data structure
2. According to occurrence:
(i) Linear data structure
(ii) Non-linear data structure
3. Primitive and Non-primitive data structure
According to nature of Size
2. Dynamic data structure:
Allow to change its size during program execution(add or delete elements at run time)
Example: Link list, tree, graph etc.
Primitive and Non-primitive data structure
1. Primitive Data Structure:
Basic data structure and directly operated upon by the machine instructions.
Example: integer , float, character.
2.Non-primitive Data Structure:
Derived from primitive data structure.
Emphasising on structuring of a group of homogeneous or heterogeneous data items.
Example: Array , List , Tree , Graph.
Active In SP
Joined: Feb 2012
03-03-2012, 03:55 PM
data-struct.doc (Size: 100 KB / Downloads: 23)
1. What is data structure?
A data structure is a way of organizing data that considers not only the items stored, but also their relationship to each other. Advance knowledge about the relationship between data items allows designing of efficient algorithms for the manipulation of data.
2. List out the areas in which data structures are applied extensively?
Database Management System,
Statistical analysis package,
3. What are the major data structures used in the following areas : RDBMS, Network data model & Hierarchical data model.
RDBMS – Array (i.e. Array of structures)
Network data model – Graph
Hierarchical data model – Trees
4. If you are using C language to implement the heterogeneous linked list, what pointer type will you use?
The heterogeneous linked list contains different data types in its nodes and we need a link, pointer to connect them. It is not possible to use ordinary pointers for this. So we go for void pointer. Void pointer is capable of storing pointer to any type as it is a generic pointer type.
5. Minimum number of queues needed to implement the priority queue?
Two. One queue is used for actual storing of data and another for storing priorities.
6. What is the data structures used to perform recursion?
Stack. Because of its LIFO (Last In First Out) property it remembers its ‘caller’ so knows whom to return when the function has to return. Recursion makes use of system stack for storing the return addresses of the function calls.
Every recursive function has its equivalent iterative (non-recursive) function. Even when such equivalent iterative procedures are written, explicit stack is to be used.
Joined: Apr 2012
04-08-2012, 10:17 AM
to get information about the topic " structures" full report ppt and related topic refer the link bellow
seminar and presentationproject and implimentationsattachment.php?aid=29417