What is ADT ?
Abstract Data Type or ADT is an organized collection of information and set of operations that are used to manage information.
A data structure is an organization of the data to solve a problem in such a way that data can be access efficiently by a progam. The choice of particular data structure depends uponi hte following cnsideration.
• It must be able to represent the inherent relationship of data in the real world.
• It must be simple enough so that it can be proceesed efficiently as and when necessary.
Data Structure consists of 2 elements
Linear Data Structure -The elements form a sequence. For example: Arrays, Stacks, queues, linked list.
Non Linear Data Structure -The elements doesnt form a sequence. For example: Tree, Graph
Algorithm: Outline, the essence of a computational procedure step by step instruction.
Program: An implementation of an algorithm insome programming langugage.
Every algorithm must satisfy the following criteria.
• Input: There are zero or more values which are externally supplied.
• Output: At least one value is produced.
• Definition: Each step must be clear and unambigious.
• Finiteness: If we trace the steps of an algorithm. Then for all the cases, algorithm must terminate after a finite number of steps.
• Effectiveness: Each step must be sufficiently basic that it can in principle be carried out by a person using only paper and pencil.
Algorithm discribes actions on the input instances. Infinitely many correct algorithms for the same algorithmic problem are possible. Any algorithm which is efficient in terms of the following is good for us.
(a) Running time: Good algorithms takes least time.
(b) Space used: Good algorithm occupies least space.
Measuring the Running Time:
Most Algorithms transformer input objects into output objects. The running time of an algorith typically grows with the input size average case running time is often difficult to determine. So, the focus is given an the wrost case running time because it is easier to analyze.
Theoritical Analysis:
It uses a high level discription of the algorithm instead of an implementation and characterizes running time as a function of the input size. It takes into account all possible inputs theoritical analysis allow us to evaluate the speed of an algorithm independent of hardware/software environment.
Pseudocode: A mixture of natural language and high level programming constructs that describes the main ideas behind the generic implementation of data structure or algorithms.
Example: Algorithm ArraysMax(A, n)
Input: The Array A storing n integers.
Output: the maximum element of A.
CurrentMax <— A[0]
For i <— 1 to n–1 do
If current max < A [i] then
Current max <— A[i]
return CurrentMax.
Primitive operations: These are the basic computation performed by an algorithm identifiable in psueod code. They are independent of the programming language for example.
• Evaluating an expression.
• Returning from a method.
• Indexing into an array.
• Arithmetic and logical operation.
By inspecting the pseudo code we can count the total number of primitive operations executed by an algorithms.
For example:
Algorithm ArrayMax (A, n) Operations
Current max <— A[0] . ………………. 1
For i <—- 1 to n–1 do ……………….
If (A[i] > current max) then ……………….
Current Max <—- A[i] ……………….. (n–1)
return currentmax ______________ Total (n+1)
Syllabus covered in this section is-
This Section covers Data Structures Questions Answers using C language .
Who can benefit –
Various Search Terms used for this section are