Chapter 1:

Introduction

Elementary Data organisation

In computers - the information is generally representated by the states of '0' or '1',
'1' being the 'ON' state and
'0' being the 'OFF' state.

Information = Instruction + Data

Data is part of an information and a value of set of values if temporarily stored in the program data or stored permanently on a file in storage devices.

Values are generally either character or numeric

The different data values in the record are inter related to each other.
In orderto make use of these relationships by the program , It is necessary to represent the data values in the organizes form.

This oranization of data is known as data structures.

Data Structures = Oraganized data + operations

So it can also be defined as logical or mathematical model of a particular organization of data.

Applications of Data Structure

Retrieve the individual data element
To solve the relationship between the data elements that are relevant to the solution of the problem
Describe the operations that must be performed on the logically relateddata elements,
The operations such as Creating, Displaying , Inserting , Deleting , Retrieving etc.
Devise methos of representing the data elements in the memroy of the computers,
that will reduce the loss of fragmentation and also allows to select the memory configuration or storage structures
Unambiguours-gives freedom to the programmer to choice any type of language that best suits for a particular program
Improve the efficiency of the algorithm

There are two main types of data structure -

Primitive data structure
Non primitive data strucure
- Linear data structure
- Non Linear data structure

Primitive Data Structure

int , float , char , double , long , boolean

Non primitive data structure

Linear Data Structure

A data structure that establishes adjacency between the elements, where all the elements are stored in the memeory linearly or sequentially
Arrays, linked list, Stack, Queues, Heap

Non Linear Data Structure

Any data structure that establishes a relation ship other than adjacency relationship is called non-linear relationship
In trees children , parent , grandparent relationship can be established.

Arrays:: are a finite ordered set of homogeneous elements, which are stored in adjacent cells in memeory.

The data is represented by a single name identified by a subscript

Arrays can be two dimensional that is 2-D,3-D,4-D and N-D
Stacks:: are a linear data structures where the data is inserted and deleted from one end which is called as the top

Data is stores and retrieved in last in first out order
Linked list:: A list is a linear sequence of data objects of the same type.

The list maybe singly,doubly,circular

The linked list is a linear collection of data items called as nodes

A node is divided into two parts - (1)Information / data field (2) Link field [a pointer to the next node of the list]
Trees:: A tree is a finite set of vertices that has a vertex called as root and remaining vertices are called as sub-trees

Operations on data structures

Some of the common operations on data structures are :

Insertion
Deletion
Traversing: accessing each element exactly once is called traversing
Sorting
Merging

Abstract Data Type [ADT]

is a specification of set of data and set of operations that can performed on the data.
This is oranized in such a way that the specification of values and operations on those values are separated from the representation of the values and the implementation of the operation.
An abstract data type is a data type with associated operations, but whose representation is hidden.
for example: Lists,sets,graphs
This is mainly done so that the implementation of these operations are written once in the program. And any other part of the program that needs to perform that operation on the ADT can do so by calling the appropriate functions
To manage the complexity of progblems and the problem-solving process,computer scientists use abstraction to alow them to focus on the "big-picture"
without getting lost in the details

Typically input , output, pre-conditions , post-conditions and assumptions to the ADT are specified as well

Examples

String ADT
List ADT
Stack ADT [LIFO]
Queue ADT [FIFO]
Binary Search Tree ADT
Priority Queue ADT

Private functions are accessible to the public functions and public functions are accessible by the application programs

Algorithm

An algorithm is a step by step procedure for performing some task in a finite amount of time
COMPLEXITY: of an algorithm is the measure ofthe amount of time and/or space requried by an algorithm for an input of a given size(n).
Space complexity:It indicates the amount of storage [ memory ] required for running the algorithm
Time complexity:of an algorithm is the amount of time it needs in order to run to completion

Keeping this in mind - there are two thing to consider in computer prgramming :

Appropriate Data Structure
Appropriate [efficient] Algorithm

Use space-time tradeoff to increase the efficiency of whatever attribute is required.
Math