Data Structures and Algorithms 2068
Section (A)
Attempt any two questions:(10x2=20)
1. Define Queue as an ADT. Write a program for basic operations in Linear queue in array implementation.
A Queue is an ordered collection of items from which items may be deleted at one end (called the front of the queue) and into which items may be inserted at the other end (the rear of the queue).
Queue follows First-In-First-Out (FIFO) methodology, i.e. the first element inserted into the queue is the first element to be removed.
A queue q of type T is a finite sequence of elements with the operations:
- MakeEmpty(q): To make q as an empty queue
- IsEmpty(q): To check whether the queue q is empty. Return true if q is empty, return false otherwise.
- IsFull(q): To check whether the queue q is full. Return true in q is full, return false otherwise.
- Enqueue(q, x): To insert an item x at the rear of the queue, if and only if q is not full.
- Dequeue(q): To delete an item from the front of the queue q. if and only if q is not empty.
- Traverse (q): To read entire queue that is display the content of the queue.
#include<stdio.h>
#include<conio.h>
#define
SIZE 10
void
enQueue(int);
void
deQueue();
void
display();
int
queue[SIZE], front = -1, rear = -1;
void
main()
{
int value, choice;
clrscr();
while(1){
printf("\\n\\n***** MENU
*****\\n");
printf("1. Insertion\\n2.
Deletion\\n3. Display\\n4. Exit");
printf("\\nEnter your choice:
");
scanf("%d",&choice);
switch(choice){
case
1: printf("Enter the value to be insert: ");
scanf("%d",&value);
enQueue(value);
break;
case 2: deQueue();
break;
case 3: display();
break;
case 4: exit(0);
default: printf("\\nWrong selection!!! Try
again!!!");
}
}
}
void
enQueue(int value){
if(rear == SIZE-1)
printf("\\nQueue is Full!!! Insertion
is not possible!!!");
else{
if(front == -1)
front = 0;
rear++;
queue[rear] = value;
printf("\\nInsertion
success!!!");
}
}
void
deQueue(){
if(front == rear)
printf("\\nQueue is Empty!!! Deletion
is not possible!!!");
else{
printf("\\nDeleted : %d",
queue[front]);
front++;
if(front == rear)
front = rear = -1;
}
}
void
display(){
if(rear == -1)
printf("\\nQueue is Empty!!!");
else{
int i;
printf("\\nQueue elements
are:\\n");
for(i=front; i<=rear; i++)
printf("%d\\t",queue[i]);
}
}
2. Why recursion is required? Explain with Tower-of-Hanoi example. How recursive algorithm makes program effective? Write the merits and demerits of recursion in Programming.
Recursion is a process by which a function calls itself repeatedly, until some specified condition has been satisfied. The process is used for repetitive computations in which each action is stated in terms of a previous result.
Recursion is required because there are problems to solve which are recursive by nature. Non-recursive solutions to those problems are
- Complicated (because of the mismatch between the problem and the code) Fragile (be
- cause complicated)
- Harder to maintain and analyse (because of points 1 and 2)
- Potentially less efficient
Tower of Hanoi (TOH) is a mathematical puzzle which consists of three pegs named as origin, intermediate and destination and more than one disks. These disks are of different sizes and the smaller one sits over the larger one.
In this problem we transfer all disks from origin peg to destination peg using intermediate peg for temporary storage and move only one disk at a time.
Algorithm for TOH problem:
Let’s consider move ‘n’ disks from source peg (A) to destination peg (C), using intermediate peg (B) as auxiliary.
1. Assign three pegs A, B & C
2. If n==1
Move the single disk from A to C and stop.
3. If n>1
a) Move the top (n-1) disks from A to B.
b) Move the remaining disks from A to C
c) Move the (n-1) disks from B to C
4. Terminate
Example for 3 disks: 7 moves
Merits of recursion
1. The code may be easier to write.
2. To solve such problems which are naturally recursive such as tower of Hanoi.
3. Reduce unnecessary calling of function.
4. Extremely useful when applying the same solution.
5. Recursion reduce the length of code.
6. It is very useful in solving the data structure problem.
7. Stacks evolutions and infix, prefix, postfix evaluations etc.
Demerits of recursion
1. Recursive functions are generally slower than non-recursive function.
2. It may require a lot of memory space to hold intermediate results on the system stacks.
3. Hard to analyze or understand the code.
4. It is not more efficient in terms of space and time complexity.
5. The computer may run out of memory if the recursive calls are not properly checked.
3. Explain In-fix to Postfix Conversion Algorithm. Illustrate it with an example. What changes should be made for converting postfix to prefix.
Algorithm to convert infix to postfix expression
1. Scan the infix string from left to right.
2. Initialize an empty stack.
3. If the scanned character is an operand, add it to postfix sting
4. If the scanned character is an operator, PUSH the character to stack.
5. If the top operator in stack has equal or higher precedence than scanned operator then POP the operator present in stack and add it to postfix string else PUSH the scanned character to stack.
6. If the scanned character is a left parenthesis ‘(‘, PUSH it to stack.
7. If the scanned character is a right parenthesis ‘)’, POP and add to postfix string from stack until an ‘(‘ is encountered. Ignore both '(' and ')'.
8. Repeat step 3-7 till all the characters are scanned.
9. After all character are scanned POP the characters and add to postfix string from the stack until it is not empty.
Example:
Infix expression: A*B+C
characters | stacks | Postfix expression |
A | A | |
* | * | A |
B | * | AB |
+ | + | AB* |
C | + | AB*C |
AB*C+ |
Postfix expression: AB*C+
Now,
To convert postfix to prefix we use following algorithm:
1. Read the Postfix expression from left to right
2. If the symbol is an operand, then push it onto the Stack
3. If the symbol is an operator, then pop two operands from the Stack
Create a string by concatenating the two operands and the operator before them.
string = operator + operand2 + operand1
And push the resultant string back to Stack
4. Repeat the above steps until end of Prefix expression.
Section B
Attempt any eight questions: (8x5=40)
4. Explain Kruskal’s algorithm with example.
Kruskal's Algorithm is used to find the minimum spanning tree for a connected weighted graph. The main target of the algorithm is to find the subset of edges by using which, we can traverse every vertex of the graph.
The Kruskal's algorithm is given as follows:
1. List all the edges of G with non-decreasing order of their weights.
2. Select an edge of minimum weight. This will be the first edge of T.
3. At each stage, select an edge of minimum weights from all remaining edges of G if it doesn’t form a cycle with previously selected edges in T. Then add the edge to T.
4. Repeat step 3 until n-1 edges have been selected.
(1, 6) | (4, 3) | (2, 7) | (2, 3) | (7, 4) | (4, 5) | (5, 7) | (5, 6) | (1, 2) |
7 | 8 | 9 | 10 | 11 | 13 | 15 | 17 | 18 |
Pick edge (1, 6): No cycle is formed, include it.
Pick edge (4,3): No cycle is formed, include it.
Pick edge (2,7): No cycle is formed, include it.
Pick edge (2,3): No cycle is formed, include it.
Pick edge (7,4): Since including this edge results in cycle, discard it.
Pick edge (4,5): No cycle is formed, include it.
Pick edge (5,7): Since including this edge results in cycle, discard it.
Pick edge (5,6): No cycle is formed, include it.
Since the number of edges included equals (n– 1), the algorithm stops here.
5. Write a program in C for bubble sorting.
#include<stdio.h>
int main()
{
int a[10],i,j,temp,n;
printf("\\n Enter the max no.of Elements to Sort: \\n");
scanf("%d",&n);
printf("\\n Enter the Elements : \\n");
for(i=0; i<n; i++)
{
scanf("%d",&a[i]);
}
for(i=0; i<n; i++)
{
for(j=0; j<n-i-1; j++)
{
if(a[j]>a[j+1])
{
temp=a[j];
a[j]=a[j+1];
a[j+1]=temp;
}
}
}
printf("The sorted array is: \\n");
for(i=0; i<n; i++)
{
printf("%d\\t",a[i]);
}
return 0;
}
6. Differentiate between contiguous list and linked list with examples.
Different between contiguous list (array) and linked list
Array (Contiguous List) | Linked list |
1. Array is a collection of elements having same data type with common name. 2. In array, elements are stored in consecutive manner in memory. 3. Insertion & deletion takes more time in array as elements are stored in consecutive memory locations. 4. In array, memory is allocated at compile time i.e. Static Memory Allocation. 5. Array can be single dimensional, two dimension or multidimensional. 6. In array, each element is independent, no connection with previous element or with its location. | 1. Linked list is an ordered collection of elements which are connected by links/pointers. 2. In linked list, elements can be stored at any available place as address of node is stored in previous node. 3. Insertion & deletion are fast & easy in linked list as only value of pointer is needed to change. 4. In linked list, memory is allocated at run time i.e. Dynamic Memory Allocation. 5. Linked list can be singly, doubly or circular linked list. 6. In Linked list, location or address of elements is stored in the link part of previous element/node |
7. Explain binary search. Illustrate it with example.
Binary
search is an extremely efficient search technique that searches the given item
in minimum possible comparisons in the already sorted list of given elements.
The logic behind the technique is:
1. First
find the middle element of the list
2. Compare
the mid-element with searched item.
There are three cases:
a. If
it is a desired element then search is successful.
b. If it is less than desired item then search only in the first half of the list.
c. If it is greater than desired item then search in the second half of the list.
Algorithm:
BinarySearch(A,l,r, key)
{
if(l= = r)
{
if(key = = A[l])
return l+1; //index starts from 0
else
return 0;
}
else
{
m = (l + r) /2 ;
if(key = = A[m])
return m+1;
else if (key < A[m])
return BinarySearch(l, m-1, key) ;
else
return BinarySearch(m+1, r, key) ;
}
}
Example:
Consider an array of data:
21, 36, 56, 79, 101, 123, 142, 203
Now,
Tracing binary search for above data;
Set L=0, R=7, key=123 (search for 123)
S.No. | L | R | Mid=(L+R)/2 | Remarks |
1. 2. | 0 4 | 7 7 | (0+7)/2=3 (4+7)/2=5 | Key>a[3] Key==a[5] |
Therefore, search successful and key(123) is at position (Mid+1)=5+1=6.
8. Explain hashing with example.
Hashing is a well-known technique to search any particular element among several elements. It minimizes the number of comparisons while performing the search.
In hashing, an array data structure called as Hash table is used to store the data items. Hash table is a data structure used for storing and retrieving data very quickly. Insertion of data in the hash table is based on the key value. Hence every entry in the hash table is associated with some key. Using the hash key the required piece of data can be searched in the hash table by few or more key comparisons.
Fig: Hashing Mechanism
Hash function is a function which is used to put the data in the hash table. Hence one can use the same hash function to retrieve the data from the hash table. Thus hash function is used to implement the hash table. The integer returned by the hash function is called hash key.
E.g. Division Hash Function
The division hash function depends upon the remainder of division. Typically the divisor is table length. For e.g. If the record 54, 72, 89, 37 is placed in the hash table and if the table size is 10 then the hash function is:
h(key) = record % table size
and key obtained by hash function is called hash key.
54%10=4
72%10=2
89%10=9
37%10=7
9. Explain why linked list is called dynamic list? Write the algorithm for deleting a new node before a node.
A linked list is called a dynamic list because it can be used with a data collection that grows and shrinks during program execution. The exact amount of memory space required by a program depends on the data being processed and so this requirement cannot be found in advance. Linked list uses runtime allocation of memory resulting in no wastage of memory space.
Algorithm for deleting the node at the specified position of the singly linked list:
let *head be the pointer to first node in the current list 1. Read position of a node which to be deleted, let it be pos. 2. if head==NULL print “void deletion” and exit 3. Enter position of a node at which you want to delete a new node. Let this position is pos. 4. Set temp=head declare a pointer of a structure let it be *p 5. if (head ==NULL)then print “void ideletion” and exit otherwise;. 6. for(i=1; i<pos-1; i++) temp=temp->next; 7. print deleted item is temp->next->info 8. Set p=temp->next; 9. Set temp->next =temp->next->next; 10. free(p); 11. End |
10. Explain the characteristics of Huffman’s algorithm and its application.
11. Write merits and demerits of recursive function over non-recursive function.
Merits of recursive function
1. The code may be easier to write.
2. To solve such problems which are naturally recursive such as tower of Hanoi.
3. Reduce unnecessary calling of function.
4. Extremely useful when applying the same solution.
5. Recursion reduce the length of code.
6. It is very useful in solving the data structure problem.
7. Stacks evolutions and infix, prefix, postfix evaluations etc.
Demerits of recursive function
1. Recursive functions are generally slower than non-recursive function.
2. It may require a lot of memory space to hold intermediate results on the system stacks.
3. Hard to analyze or understand the code.
4. It is not more efficient in terms of space and time complexity.
5. The computer may run out of memory if the recursive calls are not properly checked.
12. Write the steps involved in deleting a node in a Binary search tree.
Algorithm to delete the node in BST
struct bnode *delete(struct bnode *root, int item)
{
struct bnode *temp;
if(root==NULL)
{
printf(“Empty tree”);
return;
}
else if(item<root->info)
root->left=delete(root->left, item);
else if(item>root->info)
root->right=delete(root->right, item);
else if(root->left!=NULL &&root->right!=NULL) //node has two child
{
temp=find_min(root->right);
root->info=temp->info;
root->right=delete(root->right, root->info);
}
else
{
temp=root;
if(root->left==NULL)
root=root->right;
else if(root->right==NULL)
root=root->left;
free(temp);
}
return(temp);
}
Finding minimum element function:
struct bnode *find_min(struct bnode *root)
{
if(root==NULL)
return0;
else if(root->left==NULL)
return root;
else
return(find_min(root->left));
}
E.g.
1. Deleting leaf Node
2. Deleting node with right child
3. Deleting node with left child
4. Deleting a node having both right and left child
13. Discuss merge sort. How you rate this sorting from selection sort?
The basic concept of merge sort is divides the list into two smaller sub-lists of approximately equal size. Recursively repeat this procedure till only one element is left in the sub-list. After this, various sorted sub-lists are merged to form sorted parent list. This process goes on recursively till the original sorted list arrived.
Procedure
To sort A[l………….r]
1. Divide step: If a given array A has zero or one element, simply return; it is already sorted. Otherwise split A[l……….r] into two sub-arrays A[l………q] and A[q+1…………r] each containing about half of the element A[l…….r]. that is q is the half of way point of A[l…….r].
2. Conquer step: Sorting the two sub-arrays A[l………q] and A[q+1…………r] recursively. When the size of sequence of is 1 there is nothing more to do.
3. Combine step: combine the two sub-arrays A[l……q] and A[q+1…………r] into a sorted sequence.
C function
MergeSort(A, l, r)
{
If ( l < r)
{
m = (l + r)/2
MergeSort(A, l, m)
MergeSort(A, m + 1, r)
Merge(A, l, m+1, r)
}
}
Merge(A, B, l, m, r)
{
x=l, y=m;
k=l;
while(x<m && y<r)
{
if(A[x] < A[y])
{
B[k]= A[x];
k++;
x++;
}
else
{
B[k] = A[y];
k++;
y++;
}