Data

Download as pdf or txt
Download as pdf or txt
You are on page 1of 28

Data and Information

Data:
• Data are simply a value or set of values.
• It can be distinguished in different data types like integers, floating, or character
types.
Example: Total Marks
500 400  Data
Information:
• Information is processed data, or we can say that information is meaningful data or
data with given attributes. Example:
Abstract Data Type
List ADT:
Component – Item
Operations – Insertion, Deletion, Search, Display
• Here item is the component of Abstract Data Type.
• The list can contain several items.
• Operations on these items can be an insertion, deletion, search, and display. There
can be more operations, but only these operations will be with the item
Why do we need Data Structure?
Data structure helps us to understand the relationship of one element with others.
Also, data structures implement and organize in memory. One may question that
memory organization for any data element is quite simple so why make it complicated?
Let us take an example of this, say if we want to store subjects for a computer science
course. We can store it in a simple way using an array, a linear way to store data.
However, if we want to store information about class-wise, subject-wise information
like books, and authors, it will be complex to store linearly.
Classification of Data Structures
There are mainly two types of data structures.
1. Primitive data structures.
2. Non-Primitive data structures.
Primitive Data Structure
These data structures are inbuilt into any programming language. That is, primitive
data structures are defined by the system, not by the user. For example, in a c
programming language, we have int, char, float, and double data types. Primitive data
structures are basic data types of any language that form the basic unit for the user's
data structure. It defines the internal representation of data and storage of data
retrieval from memory. They are called primitive data types. The basic operations that
could be performed on primitive data types are creating, destroying, reading, and
updating
Non-Primitive Data Structure
These data structures are defined by the user using a primitive data structure. These
are the particular kind of logical data types, also known as derived data types. The
nonprimitive data structure is also known as the composite data structure such as
Array, Stack, Queue, Linked list, Graph, and tree.
Operation on Data Structure
The operation generally performed on any data structure includes.
Traversal: Processing each element of the list once.
Insertion: Adding a new element to the list.
Deletion: Removing an element from the list.
Sorting: Arranging the elements in some logical order.
Merging: Combining two lists into a single list
Linear Data Structure
In linear data structures, the items
are arranged in a linear sequence;
the linear arrangement of data is in
terms of a sequence of data, such as
an array, stack, queue, or linked list
where all elements will be arranged
linearly in memory. There is two
fundamental ways of representing
linear data structures in memory.
Non-Linear Data Structure
In this data structure, items are not in
sequence. It means that data elements
will be stored non-linear way, like one
data may have more than two adjacent
data or more. The tree and graph are
known as non-linear data structures
Operation on Data Structure
Four operations can be performed on the data structure.
1. Creation
2. Destroy
3. Select
4. Update
Operation on Data Structure
Creation:
Variable can be created by using a declaration statement. In ‘c’ we can declare a
variable by using the following line. It creates space for "a" in the memory. int a;
Destroy:
In 'C,' the memory area for the created variables using the malloc function will be
destroyed automatically. We have to destroy it using the free() function. While a
destroyed operation is not necessary, it helps in the efficient use of the memory.
Operation on Data Structure
Selection:
It is used to access the data within a data structure. The form of selection depends
upon the types of data structure. To access the element of the array, we have to pass the
index element. In the array, to access the 4th element, we have to pass 3 as an index.
Update:
An assignment operator is an excellent example of an update function. Another
complicated form of update operation like parameter passing operations.
Applications of Data Structure
Some of the real-time applications of Data Structures are:
• To represent a city region telephone network.
• To implement back functionality in the internet web browser.
• To store dynamically growing data, which is accessed very frequently based upon a
key value.
• To implement the undo function in a text editor.
• To store information about the directories and files in a system
Introduction to Algorithms
• The algorithm is a step-by-step procedure, which defines a set of instructions
to be executed in a particular order to get the desired output.
• Algorithms are generally created independent of underlying languages, i.e., an
algorithm can be implemented in more than one programming language.
• In computer terminology, the algorithm is a method that a computer can use to
solve problems.
Characteristics of an Algorithm
An algorithm should have the following characteristics −
• Input: An algorithm should have 0 or more well-defined inputs.
• Output: An algorithm should have one or more well-defined outputs, and should
match the desired output.
• Unambiguous: The algorithm should be clear and unambiguous. Each of its steps
and inputs/outputs should be clear and lead to only one meaning.
• Finiteness: Algorithms must terminate after a finite number of steps.
• Feasibility: Should be feasible with the available resources.
• Language Independence: An algorithm should have step-by-step directions,
which should be independent of any programming code.
Algorithm Notation
Comments:
• Each step may contain a comment in brackets.
• It indicates the primary purpose of the step.
• Comments usually appear at the beginning or the end of the statement.
Variable Names:
• Variable names will use capital letters, such as MAX and DATA.
• Single-letter names of variables used as counters or subscripts will also be
capitalized in the algorithm.
Algorithm Notation
Assignment Statement:
• Assignment statements will use the backward arrow  notation.
Example: MAX  10
This statement assigns the value 10 to MAX.
• If several statements appear in the same step
• Set K  1, LOC  1, and MAX  10, are executed from left to right.
• Some books used the dots equal notation:= or equal = sign for this operation.
Algorithm Notation
Input and Output:
Input:
• Data may be input and assigned to variables using a Read statement with the
following form:
• Read: NAME
Output:
• Data in variable output using a Write or Print statement with the following
form:
• Write: “Hello: ” + NAME
Algorithm Notation
Procedures:
• The term “Procedure” will be used for an independent algorithmic module
that solves a particular problem (Like a function in programming.) Sometimes called
Module.
Steps, Control, Exit:
• The steps of the algorithm are executed one after the other, beginning with Step 1.
• Control may be transferred to Step n of the algorithm by the statement “Goto Step n."
• Goto's statement may be practically eliminated by using specific control structures.
• The algorithm is completed when the statement Exit is encountered.
Algorithm Complexity
The algorithm's time and space are the two main factors, which decide the
efficiency of an algorithm.
• Time Factor
• Space Factor
Algorithm Complexity – Time Factor
• An algorithm's time complexity is the amount of computer time it needs to
run to complexity, such as comparisons in the sorting algorithm.
• Asymptotic analysis of an algorithm refers to defining the mathematical
foundation/framing of its run-time performance. Using asymptotic analysis, we
can very well conclude the best case, average case, and worst-case scenario of
an algorithm.
• Asymptotic analysis is input bound, i.e., if there is no input to the algorithm, it is
concluded to work constantly. Other than the "input," all other factors are
considered constant.
Algorithm Complexity – Time Factor
Usually, the time required by an algorithm falls under three types;
Best Case: This is the scene depicting the least possible execution time of a data
structure operation.
Average Case: This is the scene depicting the average execution time of a data
structure operation.
Worst Case: This is the scenario where a particular data structure operation takes
the maximum time it can take.
Algorithm Complexity – Time Factor
• Example:
• Algorithm to print summation of 1 to N:

Statement Frequency count


Algorithm DisplaySum ( a, n ) 0
{ 0
sum = 0; 1
For i = 1 to n n+1
sum=sum + a [i] n
return sum 1
} 0
Total: 2n+3
Algorithm Complexity –Space Factor
• The space complexity of an algorithm is the amount of memory space required by
the algorithm during its execution.
• Space complexity must be taken seriously for multi-user systems and in situations
where limited memory is available.
• Whenever a solution to a problem is written is required to be complete. For any
algorithm, the memory may be used for the following:
• Variables (This includes the constant values and temporary values)
• Program Instruction
• Execution
Algorithm Complexity –Space Factor
Memory usage while execution:
While executing, the algorithm uses memory space for three reasons:
Instruction Space:
It is the space required to store the executable version of the program. This space is fixed
but varies depending upon the number of lines of code in the program.
Data Space:
It is the space required to store all the constants and variables (including temporary
variables) values.
Environment Space:
It is the space required to store the environment information needed to resume the
suspended function.
Constant Space Complexity –Space Factor
For calculating space complexity, we need to know the value of memory used by
different types of datatype variables, which generally vary from different operating
systems. However, the method for calculating the space complexity remains the same.
{
int ans = a + b + c;
return ans;
}
In the above expression, variables a, b, c, and ans are all integer types. Hence, they will
take up 4 bytes each so that the total memory requirement will be 4 (4) + 4 = 20 bytes;
this additional 4 byte is for the return value. And because this space requirement is
fixed for the above example, it is called Constant Space Complexity.
Linear Space Complexity –Space Factor
int sum(int a[], int n) // n is the length of array a[]
{
int x =0; // 4 bytes for variable x
for(int i = 0; i < n; i++) // 4 bytes for variable i
{
x = x + a[i];
}
return(x);
}
• In the above code, 4 * n bytes of space are required to array a[ ] elements.
• 4 bytes requires for x, n, i, and the return value.
• Hence the total memory requirement will be (4n + 12), increasing linearly with the
increase in the input value n; hence it is called Linear Space Complexity.

You might also like