Data structure and algorithm -1

 

Need for data structures :

1.Modern day computing problems are complex and large.

2. They need to handle data in large volumes.

3.There is need to store and process information of a variety of types:  character, numeric, audio , video ,graphics, etc. 

4. Data has to be stored such that the logical relationship between the data element is retained. 

ADVANTAGE OF DATA STRUCTURE 

1. Structured data makes it easier to access the manipulate the information as compared to the raw unstructured data.

2. A variety of operation can be performed in structured data. 

3. Related data can be stored together and in the required format. 

4. better algorithm can be used on organized data. This improve program efficiency. 

5. They provide a means to store organize and retrieve data in an efficient manner.

DATA:

Data is a unprocessed input given to an a system or process.

1:ATOMIC DATA :Atomic data is a single elementary piece of data which cannot be further decomposed 

example: character 'a' and number 20etc. 

2:COMPOSITE DATA :Composite data is a grouped data item which consist of subfield each of which atomic 

example: a data like a subfield like day, month, and year.

DATA TYPE :

Data describe the  format in which data is stored and processed by a computer It also refers to the kind of data that variable hold in a programming language.

DATA OBJECT :

Data object refers to a set of element(D) of a specific data type. this  set may be finite or infinite. If the set is infinite we have to advise some mechanism to represent that set in memory because available memory is limited. 

DATA STRUCTURE :

A data structure consist of a data object , their properties and the set of legal operation which may be applied to the element of the data object.

definition:

A data structure is set of domains D a designated domain d belongs to D a set of function F and a set of axioms A. The triple (D F A ) denotes the data structure .

D = denotes the data object that is set of element.

F = denotes the set of operation that can be carried out on the element.

A = describe the properties and rules of operation.\

ABSTRACT DATA TYPE :

An ADT  is a mathematical and conceptual definition of a data structure the data structure i . e the triple DFA is called the abstract data type because it  is simply to conceptual specification off the data structure. 

IMPLEMENTATION OF DATA STRUCTURE :

The ADT is just a abstract data type. To use the data type or data structure it must  be implemented in a programming language. The implementation is concerned with 

1. How the elements are stored in memory.

2. How the operation are performed .

3. How the rules are enforced. 

SPACE COMPLEXITY :

The space complexity of an algorithm/program is the amount of memory is needs to execute. 

COMPONENTS OF SPACE COMPLEXITY :

1. Fixed part : This part is the independent of the characteristics of the input and the output of the memory space for simple variable component variable and constant. 

2.Variable part : It consist of the space needed by variable whose size depend on the particular problem instant being solved the space needed by reference variable and the recursive stack space. 

The space complexity S(P) for an algorithm is written as 

S(P) = C + Sp 

where c is a constant and is the fixed part Sp is the variable part which depend on the instance characteristics i . e. the program instance being run. 

example : float area (float r)

{

return 3.142 *r *r ;

}

the space needed is independent of the input and output of the characteristics it requires space for only one variable r 

Sp= 0, c= 1 .

TIME COMPLEXITY :

The time complexity of a program is the amount of time the program requires to execute however it is difficult to calculate the extract running time also the extract running time depend on the underlaying hardware and software. 

Hence instead of calculating exact running time a rough estimate can be made to do this we have to identify the 'active operation' of the program . The other operation like initialization assignment input and output etc. are called' book keeping operation'. and will not execute any times at the active operation. 

The total number of active operations is defined as frequency count.. 

BEST CASE AVERAGE CASE AND WORST CASE :

1. BEST CASE :

The term best case is analyze an algorithm under optimal conditions. The best case performance is the minimum number of steps that can be executed for the given input values. 

Best case (Tn) = min (Tx1, Tx2, . . . .. . Txn)

2.WORST CASE :

The worst case count the number of steps count the maximum number of steps that can be executed for the given parameter. This is the slowest possible time an algorithm may take an it upper bound. It is important to calculate the worst case behavior because  we know that the running time will execute this limit.

worst case Tn = Max(Tx1,Tx2, . . . .. . . . ,Txn)

3. AVERAGE CASE :

Average case running time assume that all input of a given are equally likely The average case step count is the average number of step executed 

Average case  =   1/  All possible inputs T(x1, x2, . . . . , xn )

 ADT of array :The ADT specifies the data object (D), function (F),axioms (A) of the data structure .

FUNCTIONS :

1. CREAT(array, type, size ): This operation creates the new array . This operation needs information like type of data of data element like a number of data element to be stored .

example : int [10]; 

2. STORE(array , index ,value ): store a value at a particular position. This operation needs the name of array the position in an array and value to be stored at that position. 

example : a[0] = 5; 

3. RETRIEVE (array , index): Retrieve a value at a position This operation requires the array  name and an index and it return to corresponding value .

example : num = a[0];

AXIOMS :

Create : The array name should be valid identifier size should be an integer and type should be a valid type.

Store : The index must be an integer value should be of the same type array .

Retrieve : the index must be an integer.

APPLICATION OF ARRAY :

Most application which handle large volume of data use array to store the element.

1. Searching .

2. Sorting .

3. Matrix operation.

4. Static implementation of data structure like stack , queue , tree, graph , etc.

SEARCHING : It is a process of locating an element with particular key value.

Key: particular element searched is called as key.

Retrieval : A successful search is called retrieval .

Internal searches : searches in which the entire table is stored in the main memory  are called as internal searches.

External searches : In this case most of the table is stored in auxiliary storage devise.

SORTING :

The sorting is a process of arranging the elements in the ascending or descending order.

1. Internal sorting : sorting is done on the data which is stored in the main memory.

2. External sorting : sorting is done on the data which is stored in auxiliary storage device. 

3. Stable sorting technique: A sorting method  is said to stable if the order of key having the same values in the unsorted set is retained in the sorted set. 

4. In place sorting : A sorting algorithm is said to be in place sorting if it does not use a lot of additional memory for sorting. 

Example : bubble sort , insertion sort etc.