Unit - 1

Introduction

Q1) Explain the basic terminologies of data structure?

A1)

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.

Q2) Explain data structure operations?

A2)

Insertion Operation

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

Q3) Explain the analysis of an algorithm?

A3)

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.

Q4) Explain Big-oh notation?

A4)

Big-oh notation: Big-oh notations can be express by using ‘o’ symbol. This notation indicates the maximum number of steps required to solve the problem. This notation expresses the worst case growth of an algorithm. Consider the following diagram in which there are two functions f(x) and g(x). f(x) is more complex than the function g(x).

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

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

Q5) Explain Big-omega notation?

A5)

Big-omega notation: Big-omega notations can be express by using ‘Ω’ symbol. This notation indicates the minimum number of steps required to solve the problem. This notation expresses the best case growth of an algorithm. Consider the following diagram in which there are two functions f(n) and g(n). f(n) is more complex than the function g(n).

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

Q6) Explain Big-theta notation?

A6)

Big-theta notation: Big-theta notations can be express by using ‘Ɵ’ symbol. This notation indicates the exact number of steps required to solve the problem. This notation expresses the average case growth of an algorithm. Consider the following diagram in which there are two functions f(n) and g(n). f(n) is more complex than the function g(n).

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

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

Q7) What is complexity?

A7)

Complexity of an algorithm is the function which gives the running time and space requirement of an algorithm in terms of size of input data. Frequency count refers to the number of times particular instructions executed in a block of code. Frequency count plays important role in the performance analysis of an algorithm. Each instruction in algorithm is incremented by one as its execution. Frequency count analysis is the form of priori analysis. Frequency count analysis produces output in terms of time complexity and space complexity.

Q8) What are the types of complexity?

A8)

Time complexity: Time complexity is about to number of times compiler execute basic operations in instruction. That is because basic operations are so defined that the time for the other operations is much less than or at most proportional to the time for the basic operations. To determine time complexity user need to calculate frequency count and express it in terms of notations. Total time taken by program is the summation of compile time and running time. Out of these two main point to take care about is running time as it depends upon the number and magnitude of input and output.

Space complexity: Space complexity is about to maximum amount of memory required for algorithm. To determine space complexity user need to calculate frequency count and express it in terms of notations.

Q9) Explain frequency count analysis?

A9)

Frequency count analysis for this code is as follows

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.

Q10) Find the frequency count for the following program?

A10)

In the above example, in instruction five value of ‘i’ is check from 0 to ‘m’ so frequency count is ‘m+1’ for fifth instruction. In instruction five value of ‘j’ is check from 0 to ‘n’ so frequency count is ‘n+1’ but this instruction is in the for loop which execute for ‘m’ times, so for seventh instruction is m*(n+1). Ninth instruction is in the two for loops, out of which first for loop execute for m times and second ‘for’ loop execute for ‘n’ times. So for ninth instruction frequency count is m*n. The total frequency count for the above program is

(m+1)+m(n+1)+mn=2m+2mn+1=2m(1+n)+1.

Q11) Explain the algorithm for linear search?

A11)

Algorithm for Linear Search is

1. Start at one end of the list

2. If the current element is not equal to the search target, move to the next element,

3. Stop when a match is found or the opposite end of the list is reached.

Function for Linear search is

Find(values, target)

{

For( i = 0; i < values.length; i++)

 {

If (values[i] == target)

{ return i; }

}

Return –1;

}

If element is found this function returns index of that element otherwise it returns –1.

Example: we have an array of integers, like the following:

Let’s search for the number 7. According to function for linear search index for element 7 should be returned. We start at the beginning and check the first element in the array.

First element is 9. Match is not found and hence we move to next element i.e 6.

Again match is not found so move to next element i.e.7.

We found the match at the index position 2. Hence output is 2.

If we try to find element 10 in above array, it will return –1,as 10 is not present in the array.

Q12) Explain the complexity of linear search

A12)

Let us assume element x is to be searched in array A of size n.

An algorithm can be analyzed using following three cases.

1.Worst case

2.Average case

3.Best case

1. Worst case: In Linear search worst case happens when element to be searched is not present. When x is not present, the linear search function compares it with all the elements of A one by one. The size of A is n and hence x is to be compared with all n elements. Thus, the worst case time complexity of linear search would be O(n).

2. Average case: In average case analysis, we take all possible inputs and calculate computing time for all of the inputs. Sum all the calculated values and divide the sum by total number of inputs. Following is the value of average case time complexity.

Average Case Time =

= O (n)

3. Best Case: In linear search, the best case occurs when x is present at the first location. So time complexity in the best case would be O(1).

Q13) Write a program for linear search?

A13)

#include<stdio.h>

#include<conio.h>

Int search(int [],int, int);

Void main()

{

Int a[20],k,i,n,m;

Clrscr();

Printf(“\n\n ENTER THE SIZE OF ARRAY”);

Scanf(“%d”,&n);

Printf(“\n\nENTER THE ARRAY ELEMENTS\n\n”);

For(i=0;i<n;i++)

{

Scanf(“%d”,&a[i]);

}

Printf(“\n\nENTER THE ELEMENT FOR SEARCH\n”);

Scanf(“%d”,&k);

m=search(a,n,k);

If(m==–1)

{

Printf(“\n\nELEMENT IS NOT FOUND IN LIST”);

}

Else

{

Printf(“\n\nELEMENT IS FOUND AT LOCATION %d”,m);

}

}

Getch();

}

Int search(int a[],int n,int k)

{

Int i;

For(i=0;i<n;i++)

{

If(a[i]==k)

{

Return i;

}

}

If(i==n)

{

Return –1;

}

}

Q14) Write a program for binary search?

A14)

#include<stdio.h>

#include<conio.h>

Void main()

{

Int n,i,search,f=0,low,high,mid,a[20];

Clrscr();

Printf("Enter the number of elements:");

Scanf("%d",&n);

For(i=1;i<=n;i++)

{

Printf("Enter the number in ascending order a[%d]=",i);

Scanf("%d",&a[i]);

}

Printf("Enter the element to be searched:");

Scanf("%d",&search);

Low=0;

High=n–1;

While(low<=high)

{

Mid=(low+high)/2;

If(search<a[mid])

{

High=mid–1;

}

Else if(search>a[mid])

{

Low=mid+1;

}

Else

{

f=1;

Printf("Element is found at the position %d:",mid);

Exit();

}

}

If(f==0)

{

Printf("Element not found");

}

Getch();

}