data structure with algoritham vtu 2 module 1st sem 2023.pptx

its helps for vtu students

1. Module-2 Recursion By: Prathap D L (Ph.D.) Research scholar VTU CPGS center Mysuru

2. syllabus Recursion - Factorial, GCD, Fibonacci Sequence, Tower of Hanoi. Queue: Definition, Representation, Queue Variants: Circular Queue, Priority Queue, Double Ended Queue; Applications of Queues. Programming Examples 2

3. Definition of recursion 3 “Recursion is a process in which a function calls itself directly or indirectly.” For Example: int fun() { ……. fun(); } //Here fun() is calling Itself int fun(int n) { if (n==1) return 1; else return 1+ fun(n-1); } int main () { int n=3; printf(“%d”, fun(n) ); return 0; } Program : Base case Recursive procedure

4. 4 How it works ? int fun(int n) { if (n==1) return 1; else return 1+fun(n-1); } int main() { int n=3; printf(“%d”, fun(n)); return 0; } Output: 3 fun(3) return 1 + fun(n-1) means fun(2) return 1 + fun(n-1) means fun(1) return 1; fun(3)=3 return 1 + 2=3 return 1 +1=2 return 1; Returning back to the caller

5. 5 What is the output ? int fun(int n) { if ( n==0) return 1; else return 7+fun(n-2); } int main() { int n=4; printf(“%d”, fun(n)); return 0; } 2 4 15 8

6. How to write Recursive functions: 6 1. Divide the problem into smaller sub-problems. 2. Specify the base condition to stop the recursion. Divide the problem into smaller sub-problems: This involves breaking down the larger problem into smaller, more manageable instances of the same problem. These sub-problems should be similar to the original problem but simpler to solve. Ex: Calculate Fact(4) Fact(1)=1 Fact(2)=2*1= 2*Fact(1) Fact(3)=3*2*1= 3*Fact(2) Fact(4)=4*3*2*1= 4*Fact(3) Fact(n)=n* Fact(n-1)

7. 7 Specify the base condition to stop the recursion: This is the termination condition that tells the function when to stop calling itself recursively. It's essentially a condition that can be evaluated directly without needing further recursion. Without a base case, a recursive function would call itself indefinitely, leading to a stack overflow error. Ex: int fact(int n) { if(n==1) return 1; else return n*fact(n-1); } Base case Recursive procedure 1 2

8. 8 Factorial program with tracing: #include<stdio.h> int fact(int n) { if(n==1) return 1; else return n*fact(n-1); } int main() { int n; printf("enter the number:"); scanf("% d",&n ); printf(" Fcatorial of %d is %d", n,fact (n)); } Step1: n=4 Result =fact(24) fact(4) if(4==1) #False else return 4*fact(3)=4*6=24 Step2:n=3 fact(3) if(3==1) #False else return 3*fact(2) =3*2=6 Step3: n=2 fact(2) if(2==1) #False else return 2*fact(1) =2*1=2 Step4: n=1 fact(1) if(1==1) #True return 1

9. Types of recursion 9 Direct recursion Indirect recursion Tail recursion Non-tail recursion In direct recursion , a function calls itself directly within its own definition Ex: int fun() { ……. fun(); } In indirect recursion , two or more functions call each other in a circular manner. it means A function ( fun ) is called indirect recursive if it calls another function ( fun2 ) and then fun2 calls fun directly or indirectly

10. 10 Ex: fun() { //some code fun2(); //some code } fun2() { //some code fun(); // some code } Write a program to print numbers from 1 to 10 in such a way that when number is odd, add 1 and when number is even ,subtract 1 void odd(); void even(); int n=1; void odd() { if(n<=10) { printf(“%d”,n+1); n++; even(); } return; } void even() { if(n<=10) { printf(“%d”,n-1); n++; odd(); } return; } int main() { odd(); }

11. 11 Tail recursion : A recursive function is said to be tail-recursive if the recursive call is the last thing done by the function. There is no need to keep record of the previous state Non-tail recursion : A recursive function is said to be non-tail-recursive if the recursive call is not the last thing done by the function. After returning back, there is something left to evaluate. Ex: void fun(int n) { if(n==0) return ; else printf(“%d”, n); return fun(n-1); } int main() { fun(3); return 0; } Output: 321 Ex: void fun(int n) { if(n==0) return ; fun(n-1); printf(“%d”, n); } int main() { fun(3); return 0; } Output: 123

12. 12 #include <stdio.h> int gcd(int a, int b) { if (b == 0) { return a; // Base case } else { return gcd(b, a % b); } } int main() { int num1, num2; printf("Enter two integers: "); scanf("%d %d", &num1, &num2); int result = gcd(num1, num2); printf("The GCD of %d and %d is %d\n", num1, num2, result); return 0; } GCD program with tracing: Step 1:gcd(48, 18) i.e. a=48, b=18 if(18==0) False (b, a % b)=> (18, 48 % 18 =12) Step 2: gcd(18, 12) i.e. a=18, b=12 if(12==0) False (b, a % b)=>(12, 18 % 12 =6) Step 3: gcd(12, 6) i.e. a=12, b=6 if(6==0) False (b, a % b)=> (6,12 % 6 =0) Step 4: gcd(6, 0) i.e. a=6, b=0 if(0==0) True (return a) (b, a % b)=>(0, 6 % 0 = 6) // Step 5: gcd(0, 6) => return 6 (since b == 0)

13. 13 Fibonacci Sequence with tracing ( next term is obtained by taking sum of previous two terms) #include <stdio.h> int fib(int n) { if (n <= 1) { return n; } else { return fib(n - 1) + fib(n - 2); } } int main() { int num; printf("Enter the number of terms: "); scanf("%d", &num); //num =6 printf("Fibonacci Series: "); for (int i = 0; i < num; ++i) { printf("%d ", fib(i)); } printf("\n"); return 0; } Step 1: i=0; 0<6 fib(i)=fib(0) i=n=0 if(0<=1) #True Result = 0 Step 2: i=1; 1<6 fib(i)=fib(1) i=n=1 if(1<=1) #True Result = 1 Step 3:i=2; 2<6 fib(i)=fib(2) i=n=2 if(2<=1) #Flase else fib(n-1)+fib(n-2) fib(1) + fib(0) =1+0= 1 Result = 1 Step 4:i=3; 3<6 fib(i)=fib(3) i=n=3 if(3<=1) #Flase else fib(n-1)+fib(n-2) fib(2) + fib(1) =1+1= 2 Result = 2 Step 5:i=4; 4<6 fib(i)=fib(4) i=n=4 if(4<=1) #Flase else fib(n-1)+fib(n-2) fib(3) + fib(2) =2+1= 3 Result = 3 Step 6:i=5; 5<6 fib(i)=fib(5) i=n=5 if(5<=1) #Flase else fib(n-1)+fib(n-2) fib(4) + fib(3) =3+2= 5 Result = 5 Step 7:i=6 ;6<6 #False

14. Tower of Hanoi Problem In the problem of Tower of Hanoi, there will be three poles, viz. A, B and C. Pole A (source pole) contains ‘n’ discs of different diameters and are placed one above the other such that larger disc is placed below the smaller disc. Now, all the discs from source (A) must be transferred to destination (C) using the pole B as temporary storage. Conditions are: Only one disc must be moved at a time smaller disc is on the top of larger disc at every step Algorithm to move n discs from source to destination is as follows – (i) move n-1 discs from source to temporary (ii) move nth disc from source to destination (iii) move n-1 disc from temporary to destination

15. 20XX 15 #include<stdio.h> int count=0; void tower(int n, char s, char t, char d) { if(n==1) { printf(“Move disc 1 from %c to %c “, s, d); count ++; return; } tower(n-1, s, d, t); printf(“Move disc %d from %c to %c”, n, s, d); count ++; tower(n-1, t, s, d); } void main() { int n; printf(“Enter the number of discs”); scanf(“%d”, &n); tower(n, ‘A’,’B’,’C’); printf("Total number of moves: %d\n", count); return 0; }

16. 16

17. 17 Tracing (if no of disc is 3) N S T D Tower ( 3 A B C) if (3==1) F Tower ( n-1,s,d,t) Tower ( 2 A C B) if (2==1) F Tower ( n-1,s,d,t) Tower ( 1 A B C) if(1==1) T Move disc 1 from A to C count=1 Tower ( 2 A C B) if (2==1) F Move disc 2 from A to B count =2 Tower ( n-1,t,s,d) Tower ( 1 C A B) if(1==1) T Move disc 1 from C to B count =3 Tower ( 3 A B C) if (3==1) F Move disc 3 from A to C count =4 Tower ( n-1,t,s,d) Tower ( 2 B A C) if (2==1) F Tower ( n-1,s,d,t) Tower ( 1 B C A) if(1==1) T Move disc 1 from B to A count=5 Tower ( 2 B A C) if (2==1) F Move disc 2 from B to C count =6 Tower ( n-1,t,s,d) Tower ( 1 A B C) if(1==1) T Move disc 1 from A to C count =7

18. 18 What is Abstract data types? In computer science, an abstract data type (ADT) is basically a blueprint for how data should be handled. It defines the data that can be stored and the operations that can be performed on that data, without going into the specifics of how the data is actually stored in memory . Some common examples of abstract data types : Stack ,Queues ,List etc.

19. 19 Queue Definition: Queue is also an abstract data type or a linear data structure in which insertions are done at one end (rear/tail) and deletions are done at other end (front/head) .The first element to be inserted is the first one to be deleted . Hence, it is called First in First out (FIFO) or Last in Last out(LILO). Basic Operations in a Queue: 1.enqueue(): Add an element to the end of the queue. 2.dequeue():Remove an element from the front of the queue. 3.is_full():Check if the queue is full. 4.is_empty():Check if the queue is empty. 5.peek():Get the value of the front of the queue without removing it.

20. 20 Algorithm for Dequeue: 1. START 2. Check if the queue is empty. 3. If the queue is empty, produce underflow error and exit. 4. If the queue is not empty, access the data where front is pointing. 5. Increment front pointer to point to the next available data element. 6. Return success. 7. END Algorithm for Enqueue: 1. START 2. Check if the queue is full. 3. If the queue is full, produce overflow error and exit. 4. If the queue is not full, increment rear pointer to point the next empty space. 5. Add data element to the queue location, where the rear is pointing. 6. return success. 7. END

21. 21 Algorithm for is_full(): 1. START 2. If the rear of queue elements equals the queue size, return true 3. Otherwise, return false 4. END Algorithm for is_empty(): 1. START 2. If the rear and front equals to -1, return true 3. Otherwise, return false 4. END Algorithm for peek(): START If the rear and front equals to -1, return queue empty 3. Return the element at the front of the queue 4. END

22. 22 Applications of Queues Process scheduling in operating systems: Operating systems use queues to manage processes waiting for CPU resources. Breadth-first search (BFS) algorithm: Queues are essential for traversing graphs and trees level by level. Level order traversal in trees: Similar to BFS, level order traversal in trees visits nodes level by level. Implementing FIFO buffers: Queues excel at maintaining the order of elements Task management systems: Queues are perfect for managing a sequence of tasks Real-time systems (e.g., handling network traffic)

23. 20XX 23 Queue Representation Using Array Queues can be easily represented using linear arrays. Every queue has front and rear variables that point to the position from where deletions and insertions can be done, respectively. Here, front=0 and rear=5 If we want to add one more value in the list ,then rear would be incremented by 1 and the value would be stored at the position pointed by rear Queue can be represented in two ways : Using Array Using Linked List

24. 24 Note: An attempt to insert an element into a full queue is called as Queue overflow. Trying to delete an element from an empty queue is known as Queue underflow.

25. 25 Queue using Linked list: If we implement the queue using an array, we need to specify the array size at the beginning(at compile time). We can't change the size of an array at runtime. So, the queue will only work for a fixed number of elements. Solution: We can implement the queue data structure using the linked list. In the linked list, we can change its size at runtime. The linked queue looks as shown in figure:

26. 26 Queue Variants Linear Queue: Linear queues are the simplest type of queues, where elements are stored in a linear manner. They follow the First In First Out (FIFO) principle. Linear queues can be implemented using arrays or linked lists. In linear queues, both enqueue (addition) and dequeue (removal) operations occur at opposite ends of the queue. Circular Queue: Circular queues are similar to linear queues but with the added feature of wrapping around when the rear or front reaches the end of the queue. This allows efficient utilization of memory space and avoids wastage of space. Circular queues can also be implemented using arrays or linked lists. They are particularly useful in scenarios where a fixed-size buffer is needed, such as in operating systems for managing processes or in networking for managing data packets.

27. 27 Priority Queue: Priority queues are queues where each element has an associated priority. Elements with higher priority are dequeued before elements with lower priority, regardless of the order in which they were enqueued. Priority queues can be implemented using various data structures like heaps, binary search trees, or arrays. They are used in various applications like task scheduling, Dijkstra's algorithm for shortest path finding, etc. Double-ended Queue (Deque): A double-ended queue, or deque, is a queue where elements can be added or removed from both ends. It supports operations like enqueue and dequeue from both front and rear ends. Deques can be implemented using arrays or linked lists with pointers to both ends. They are useful in scenarios where elements need to be added or removed from both ends efficiently, such as implementing a queue in a concurrent environment.

28. 28 A circular queue is an extended version of a linear queue as it follows the First In First Out principle with the exception that it connects the last node of a queue to its first by forming a circular link. The last node is connected to the first node. Also known as a Ring Buffer , the nodes are connected end to end. Insertion takes place at the front of the queue, and deletion at the end of the queue Circular queue Operations: Front - Used to get the starting element of the Circular Queue. Rear - Used to get the end element of the Circular Queue. enQueue (value) - Used to insert a new value in the Circular Queue. This operation takes place from the end of the Queue. deQueue () - Used to delete a value from the Circular Queue. This operation takes place from the front of the Queue.

29. 29 Representation of Circular Queue using Arrays and a Linked List Here we can implement the circular queue using both the 1-D array and the Linked list. However, implementing a circular link is a new addition that we need to execute. Additionally, this queue works by the process of circular incrementation . That is, when you reach the end of a queue, you start from the beginning of a queue. The circular incrementation is achievable with the help of the modulo division.(%) Here, the MaxSize of queue is 5, and the rear pointer has already reached the end of a queue. There is one empty space at the beginning of a queue, which means that the front pointer is pointing to location 1. (Rear + 1) = 4 + 1 = 5 (Overflow Error) Rear = (Rear + 1)% MaxSize =5%5= 0

30. 30 Enqueue Algorithm The following steps should be taken to enqueue(insert)data into a queue Step 1: checking queue overflow if (rear+1)%size =front Return overflow Step 2: within else if condition front equals to -1 set front=0 Step 3: rear =(rear+1)% size insert element into the queue[rear] Step 4: end else condition Step 5: exit Dequeue Algorithm The following steps should be taken to dequeue data into a queue Step 1: if front =-1 return underflow Step 2: within else set q[front] into item print delete item Step 3: if front==rear set front=rear=-1; Step 4 : else front=(front+1)%max Step 5:end else Step 6: exit

31. 31 void Enqueue() { int item; if ((rear + 1) % max == front) { printf("Overflow Error\n"); } else { if (front == -1) front = 0; rear = (rear + 1) % max; printf("Enter the element for Insertion: "); scanf("%d", &item); Q[rear] = item; } }

32. 32 void Dequeue() { int item; if (front == -1) { printf("Underflow\n"); return; } else { item = Q[front]; printf("\n Deleted item=%d\n", item); if (front == rear) front = rear = -1; else front = (front + 1) % max; } } void display() { int i; if (front == -1) { printf("Queue is empty\n"); } else { printf("Queue elements are:\n"); i = front; while (i != rear) { printf("%d\n", Q[i]); i = (i + 1) % max; } printf("%d\n", Q[rear]); } }

33. 33 Priority Queue A priority queue is another special type of Queue data structure in which each element has some priority associated with it .Based on the priority, the elements are arranged in a priority queue. If the elements occur with same priority, then they are served according to the FIFO principle . In priority Queue, the insertion takes place based on the arrival while the deletion occurs based on the priority queue can be shown as

34. 34 The priority queue can be implemented in four ways that include Arrays, Linked list, Heap data structure and binary search tree . The heap data structure is the most efficient way of implementing the priority queue , so we will implement the priority queue using a heap data structure . Now ,first we understand the reason why heap is the most efficient way among all the other data structures

35. 35 What is heap? A heap is a tree based data structure with the following properties: It is a complete binary tree that is ,each level of the tree is completely filles ,expect possibly the bottom level. At this level, it is filled from left to right. It satisfies the heap-order property: The data item stored in each node is greater than or equal to the data items stored in its children Complete Incomplete

36. 36 Types of Heap Min heap : The value of the parent node should be less than or equal to either of its children. Max Heap : The value of the parent node is greater than or equal to its children.

37. 37

38. Applications of Priority Queue: A priority queue is useful in the following cases: 1. It helps in the implementation of heapsort. 2. It helps in the implementation of the Huffman code. 3. It is used for finding the shortest path in Dijkstra’s algorithm. 4. It is used in Prim’s algorithm. 5. It helps in the implementation of priority scheduling algorithms in the operating system.

39. 39 Dequeue(Double ended Queue) A dequeue (double-ended queue) is an abstract data type. In deque, we can perform deletion and insertion operations from both ends. Dequeues are often pronounced "deck" and are sometimes referred to as "head-tail" linked lists . There are two types of deques based on the restrictions imposed: 1. Input-restricted queue : In input restricted queue, insertion operation can be performed at only one end, while deletion can be performed from both ends.

40. 40 2. Output restricted Queue : In output restricted queue, deletion operation can be performed at only one end, while insertion can be performed from both ends. Operations on Deque: 1. Insertion at front 2. Deletion from front 3. Insertion at rear 4. Deletion from rear 5. isFull ( ) 6. isEmpty ( )

41. 41 void insert_at_Front (int value) { if ((Front == 0 && Rear == SIZE - 1) || (Front == (Rear + 1) % SIZE)) { Printf(“Overflow”); return } if(Front==-1 && Rear==-1) { Front = Rear = 0; deque[Front] = value; } else if(Front == 0) { Front = SIZE-1; deque[Front] = value; } else { Front = (Front - 1 + SIZE) % SIZE; deque[Front]= value; } } deque = [-1, -1, -1, -1, -1] (all elements are -1) deque = [10, -1, -1, -1, -1] deque = [10, -1, -1, -1, 20] deque = [10, -1, -1, 30, 20]

42. 42 void delete_at_Front () { if(Front==-1 && Rear==-1) { printf("Underflow"); return; } else if(Front == Rear) { printf( “%d\n”, deque[Front]); Front=-1; Rear=-1; } else if(Front == SIZE-1) { printf(“%d\n”, deque[Front]); Front = 0; } else { printf(“%d\n”, deque[Front]); Front = Front+1; } } deque = [10, 20, 30, 40, 50]

43. 43 void inseret_at_Rear (int value) { if ((Front == 0 && Rear == SIZE - 1) || (Front == Rear + 1)) { Printf(“Overflow”); return; } if(Front==-1 && rear==-1) { Front=Rear=0; deque[Rear] = value; } else if(Rear == SIZE-1) { Rear = 0; deque[Rear] = value; } else { Rear++; deque[Rear] = value; } } deque = [-1, -1, -1, -1, -1] (all elements are -1) deque = [10, -1, -1, -1, -1] deque = [10, 20, -1, -1, -1] deque = [10, 20, 30, 40, 50]

44. 44 void delete_at_Rear () { if(Front==-1 && Rear==-1) { printf("Underflow"); return; } else if(Front == Rear) { printf(deque[Rear]); Front = -1; Rear = -1; } else if(Rear == 0) { printf(deque[Rear]); Rear = SIZE-1; } else { printf(deque[Rear]); Rear = Rear-1; } } deque = [10, 20, 30, 40, 50] f=0 , r=4

45. 45 “A small aim is a crime.” Dr. APJ Abdul Kalam Thank you