Data : Data are simply values or set of values
Data Items : It refers to single unit of values.
Data items are divided into sub-items called Group items.
Ex: Employee Name may be divided into three subitems
First name, Middle name , Last name.
Data items that are not further divided into sub items are called Elementary items.
Entity: An entity is something that has attributes or properties which may be assigned values. The values may be numeric or non-numeric.
Ex: Attributes Names Age Sex SSN
Values Rohland Gail 34 F 134-34-5533
Entities with similar attributes form entity set. Each attribute of an entity set has range of values the set of all possible values that could be assigned to particular attribute.
Field : is a single elementary unit of information representing an attribute of an entity.
Record : It is a collection of field values of the given entity.
File : is the collection of records of entities in a given entity set.
Each record in a file may contain field items but the value in a certain field may uniquely determine the record in the file. Such a field k is called the primary key and the values k1,k2….kn are called the keys or key values.
Records may also be classified according to length
A file can have fixed-length records or variable length records.
In fixed length records all the records contain the same data items with the same amount of space assigned to each data item.
In variable length records the file records may contain different lengths.
Example:
Student records have variable lengths since different students take different number of courses. Variable length records have a minimum and maximum length
The above organization of data into fields , records and files may not be complex enough to maintain and efficiently process certain collections of data. For this reason data are also organized into more complex types of structures.
Insert operation is to insert one or more data elements into an array. Based on the requirement, a new element can be added at the beginning, end, or any given index of array.
Here, we see a practical implementation of insertion operation, where we add data at the end of the array −
Example
Following is the implementation of the above algorithm −
#include <stdio.h>
main() {
int LA[] = {1,3,5,7,8};
int item = 10, k = 3, n = 5;
int i = 0, j = n;
printf("The original array elements are :\n");
for(i = 0; i<n; i++) {
printf("LA[%d] = %d \n", i, LA[i]);
}
n = n + 1;
while( j >= k) {
LA[j+1] = LA[j];
j = j - 1;
}
LA[k] = item;
printf("The array elements after insertion :\n");
for(i = 0; i<n; i++) {
printf("LA[%d] = %d \n", i, LA[i]);
}
}
When we compile and execute the above program, it produces the following result −
Output
The original array elements are :
LA[0] = 1
LA[1] = 3
LA[2] = 5
LA[3] = 7
LA[4] = 8
The array elements after insertion :
LA[0] = 1
LA[1] = 3
LA[2] = 5
LA[3] = 10
LA[4] = 7
LA[5] = 8
Deletion Operation
Deletion refers to removing an existing element from the array and re-organizing all elements of an array.
Algorithm
Consider LA is a linear array with N elements and K is a positive integer such that K<=N. Following is the algorithm to delete an element available at the Kth position of LA.
1. Start
2. Set J = K
3. Repeat steps 4 and 5 while J < N
4. Set LA[J] = LA[J + 1]
5. Set J = J+1
6. Set N = N-1
7. Stop
Example
Following is the implementation of the above algorithm −
#include <stdio.h>
void main() {
int LA[] = {1,3,5,7,8};
int k = 3, n = 5;
int i, j;
printf("The original array elements are :\n");
for(i = 0; i<n; i++) {
printf("LA[%d] = %d \n", i, LA[i]);
}
j = k;
while( j < n) {
LA[j-1] = LA[j];
j = j + 1;
}
n = n -1;
printf("The array elements after deletion :\n");
for(i = 0; i<n; i++) {
printf("LA[%d] = %d \n", i, LA[i]);
}
}
When we compile and execute the above program, it produces the following result −
Output
The original array elements are :
LA[0] = 1
LA[1] = 3
LA[2] = 5
LA[3] = 7
LA[4] = 8
The array elements after deletion :
LA[0] = 1
LA[1] = 3
LA[2] = 7
LA[3] = 8
Analysis is the theoretical way to study performance of computer program. Analysis of an algorithm is helpful to decide the complexity of an algorithm. There are three ways to analyze an algorithm which are stated as below.
1. Worst case: In worst case analysis of an algorithm, upper bound of an algorithm is calculated. This case considers the maximum number of operation on algorithm. For example if user want to search a word in English dictionary which is not present in the dictionary. In this case user has to check all the words in dictionary for desired word.
2. Best case : In best case analysis of an algorithm, lower bound of an algorithm is calculated. This case considers the minimum number of operation on algorithm. For example if user want to search a word in English dictionary which is found at the first attempt. In this case there is no need to check other words in dictionary.
3. Average case : In average case analysis of an algorithm, all possible inputs are consider and computing time is calculated for all inputs. Average case analysis is performed by summation of all calculated value which is divided by total number of inputs. In average case analysis user must be aware about the all types of input so average case analysis are very rarely used in practical cases.
To express the running time complexity of algorithm three asymptotic notations are available. Asymptotic notations are also called as asymptotic bounds. Notations are used to relate the growth of complex function with the simple function. Asymptotic notations have domain of natural numbers. These notations are as follows
Fig. 3.7
In the above diagram out of two function f(n) and g(n), more complex function is f(n), so need to relate its growth as compare to simple function g(n). More specifically we need one constant function c(n) which bound function f(n) at some point n0. Beyond the point ‘n0’ function c*g(n) is always greater than f(n).
Now f(n)=Og(n)if there is some constant ‘c’ and some initial value ‘n0’. such that f(n)<=c*g(n) for all n>n0
In the above expression ‘n’ represents the input size
f(n) represents the time that algorithm will take
f(n) and g(n) are non-negative functions.
Consider the following example
Fig. 3.8
In the above example g(n) is ‘’n’ and f(n) is ‘2n+1’ and value of constant is 3. The point where c*g(n) and f(n) intersect is ‘’n0’. Beyond ‘n0’ c*g(n) is always greater than f(n) for constant ‘3’. We can write the conclusion as follows
f(n)=O g(n) for constant ‘c’ =3 and ‘n0’=1
such that f(n)<=c*g(n) for all n>n0
Fig. 3.9
In the above diagram out of two function f(n) and g(n), more complex function is f(n), so need to relate its growth as compare to simple function g(n). More specifically we need one constant function c(n) which bound function f(n) at some point n0. Beyond the point ‘n0’ function c*g(n) is always smaller than f(n).
Now f(n)=Ωg(n)if there is some constant ‘c’ and some initial value ‘n0’. such that c*g(n) <= f(n)for all n>n0
In the above expression ‘n’ represents the input size
f(n) represents the time that algorithm will take
f(n) and g(n) are non-negative functions.
Consider the following example
In the above example g(n) is ‘2n’ and f(n) is ‘2n-2’ and value of constant is 0.5. The point where c*g(n) and f(n) intersect is ‘’n0’. Beyond ‘n0’ c*g(n) is always smaller than f(n) for constant ‘0.5’. We can write the conclusion as follows
f(n) = Ω g(n) for constant ‘c’ =0.5 and ‘n0’=2
such that c*g(n)<= f(n) for all n>n0
Fig. 3.10
Fig. 3.11
In the above diagram out of two function f(n) and g(n), more complex function is f(n), so need to relate its growth as compare to simple function g(n). More specifically we need one constant function c1 and c2 which bound function f(n) at some point n0. Beyond the point ‘n0’ function c1*g(n) is always smaller than f(n) and c2*g(n) is always greater than f(n).
Now f(n) = g(n) if there is some constant ‘c1 and c2’ and some initial value ‘n0’. such that c1*g(n) <= f(n)<=c2*g(n)for all n>n0
In the above expression ‘n’ represents the input size
f(n) represents the time that algorithm will take
f(n) and g(n) are non-negative functions.
f(n) = g(n) if and only if f(n)=O g(n) and f(n)=Ω g(n)
Consider the following example
Fig. 3.12
In the above example g(n) is ‘2n’ and f(n) is ‘3n-2’ and value of constant c1 is 0.5 and c2 is 2. The point where c*g(n) and f(n) intersect is ‘’n0’. Beyond ‘n0’ c1*g(n) is always smaller than f(n) for constant ‘0.5’ and c2*g(n) is always greater than f(n) for constant ‘2’. We can write the conclusion as follows
f(n)=Ω g(n) for constant ‘c1’ =0.5 , ‘c2’ = 2 and ‘n0’=2
such that c1*g(n)<= f(n)<=c2*g(n) for all n>n0
Frequency count analysis for this code is as follows
Sr. No. | Instructions | Frequency count |
#include<stdio.h> |
| |
2. | #include<conio.h> |
|
3. | void main() { |
|
4. | int marks; |
|
5. | printf(“enter a marks”); | add 1 to the time count |
6. | scanf(“%d”,&marks); | add 1 to the space count |
7. | printf(“your marks is %d”,marks); | add 1 to the time count |
8. | getch(); } |
|
In the above example, for the first four instructions there is no frequency count. For data declaration and the inclusion of header file there is no frequency count. So, for this example has a frequency count for time is 2 and a frequency count for space is 1. So, total frequency count is 3.
Consider the following example
Sr. No. | Instructions | Frequency count |
#include<stdio.h> |
| |
2. | #include<conio.h> |
|
3. | void main() { |
|
4. | int sum=0; | 1 |
5. | for(i=0;i<5;i++) | 6 |
6. | sum=sum+i; | 5 |
7. | printf(“Addition is %d”,sum); | 1 |
8. | getch(); } |
|
Explanation : In the above example, one is add to frequency count for instruction four and seven after that in fifth instruction is check from zero to five so it will add value six to frequency count. ‘For’ loop executed for five times so for sixth instruction frequency count is five. Total frequency count for above program is 1+6+5+1 =13.
Consider the following example
Sr. No. | Instructions | Frequency count |
1. | #include<stdio.h> |
|
2. | #include<conio.h> |
|
3. | void main() { |
|
4. | int a[2][3],b[2][3],c[2][3]] |
|
5. | for(i=0;i<m;i++) | m+1 |
6. | { |
|
7. | for(j=0;j<n;j++) | m(n+1) |
8. | { |
|
9. | c[i][j]=a[i][j]*b[i][j]; | m.n |
10. | }} |
|
11. | getch(); } |
|
Consider the following example
Sr. No. | Instructions | Frequency count |
1. | #include<stdio.h> |
|
2. | #include<conio.h> |
|
3. | void main() { |
|
4. | int a[2][3],b[2][3],c[2][3]] |
|
5. | for(i=0;i<m;i++) | m+1 |
6. | { |
|
7. | for(j=0;j<n;j++) | m(n+1) |
8. | { |
|
9. | a[i][j]=n; | m.n |
10. | for(k=0;k<n;k++) | mn(n+1) |
11. | c[i][j]=a[i][j]*b[i][j]; | m.n.n |
12. | }} |
|
13. | getch(); } |
|
Explanation : For above program total frequency count
= (m+1)+m(n+1)+mn+mn(n+1)+mn
= m+1+mn+m+mn+mn2 +mn+mn2
= 2 mn2+3mn+2m+1
= mn(2n+3)+2m+1
Consider the following example
Sr. No. | Instructions | Frequency count |
1. | #include<stdio.h> |
|
2. | #include<conio.h> |
|
3. | void main() { |
|
4. | int n=1,m; | 1 |
5. | Do |
|
6. | { |
|
7. | printf(“hi”); | 10 |
8. | if(n==10) | 10 |
9. | break; | 1 |
10. | n++; | 9 |
11. | } |
|
12. | while(n<15); | 10 |
13. | getch(); } |
|
Explanation : the above example, one is add to frequency count for instruction four. The loop will execute till value of n is incremented to 10 from 1, so for loop statements ie instructions seven and eight is execute for tem times. when the value of ‘n’ is ten then ‘break’ statement will execute for one time and it will skip the tenth execution of tenth instruction. Tenth instruction will add value nine to frequency count. Total frequency count for above program is 10+10+1+9+10 = 40.
References:
1. Algorithms, Data Structures, and Problem Solving with C++”, Illustrated Edition by Mark Allen Weiss, Addison-Wesley Publishing Company.
2. “How to Solve it by Computer”, 2nd Impression by R.G. Dromey, Pearson Education.
3. “Fundamentals of Data Structures”, Illustrated Edition by Ellis Horowitz, Sartaj Sahni, Computer Science Press.
