University of Science and Technology Data Structures and Algorithms Lab Manual PDF

**University of Science and Technology** **Faculty of Computer Science and Information Technology** **Data Structures and Algorithms** **Lab Manual** **Prepared By** **Prof. Noureldien A.Noureldien** **October 2024** **Table of Contents** **Weak \#** **Lab Topics**...

**University of Science and Technology** **Faculty of Computer Science and Information Technology** **Data Structures and Algorithms** **Lab Manual** **Prepared By** **Prof. Noureldien A.Noureldien** **October 2024** **Table of Contents** **Weak \#** **Lab Topics** **Page No** ------------- --------------------------------------- ------------- 1 Linked Lists - Singly linked list 3 2 Linked Lists -- Circular Linked Lists 14 3 Stacks 24 4 Queues 35 5 Priority Queues 46 6 Searching 57 7 Bubble Sort 69 8 Insertion and Selection Sort 78 9 Hashing 92 10 Programming Problems 108 **Lab (1): Linked Lists - Singly linked list** **Description** This lab is to demonstrate to students how to use linked lists to solve problems. **Lab (1): Learning Outcomes** By the end of this lab the student must be able to: - Define what linked lists are? - Compare linked lists to arrays - Differentiate between different types of linked lists - Write C codes that create and manipulate different types of linked lists. **Lab (1): What Instructor has to do** The instructor has to: - Follow the steps below to demonstrate to the students how to use C to implement linked lists - Explain to the students the stated linked lists concepts and definitions. - Supervise students while they write and run the C codes in this lab. **1.1 Definition of Linked List** ***Definition:* A linked list is a linear ordered collection of finite homogeneous data elements called node, where the linear order is maintained by means of links or pointers.** **[A linked list allocates space for each element separately in its own block of memory called a \"linked list element\" or \"node\".]** **[The list structure is created by the use of pointers to connect all its nodes together like the links in a chain.]** In an array if the address of one element is known, addresses of all other elements become automatically known. Since, in a linked list, there is no relationship between the addresses of elements, **[each element of a linked list must store explicitly the address of the element next to it]**. **1.2 Representation of a Linked list** Linked list can be represented as the connection of nodes in which each node points to the next node of the list. The representation of the linked list is shown below - Linked list **1.3 Why use linked list over array?** Linked list is a data structure that overcomes the limitations of arrays. Let\'s first see some of the limitations of arrays - - The size of the array must be known in advance before using it in the program. - Increasing the size of the array is a time taking process. It is almost impossible to expand the size of the array at run time. - All the elements in the array need to be contiguously stored in the memory. Inserting an element in the array needs shifting of all its predecessors. **Linked list is useful because -** - It allocates the memory dynamically. All the nodes of the linked list are non-contiguously stored in the memory and linked together with the help of pointers. - In linked list, size is no longer a problem since we do not need to define its size at the time of declaration. List grows as per the program\'s demand and limited to the available memory space. **1.4 Applications of Linked list** The applications of the Linked list are given as follows - - With the help of a linked list, the polynomials can be represented as well as we can perform the operations on the polynomial. - A linked list can be used to represent the sparse matrix. - The various operations like student\'s details, employee\'s details, or product details can be implemented using the linked list as the linked list uses the structure data type that can hold different data types. - Using linked list, we can implement stack, queue, tree, and other various data structures. - If we want to represent the graph as an adjacency list, then it can be implemented as a linked list. - A linked list can be used to implement dynamic memory allocation. The dynamic memory allocation is the memory allocation done at the run-time. **1.5 Operations performed on Linked list** The basic operations that are supported by a list are mentioned as follows - - **Insertion -** This operation is performed to add an element into the list. - **Deletion -** It is performed to delete an operation from the list. - **Display -** It is performed to display the elements of the list. - **Search -** It is performed to search an element from the list using the given key. **1.6 Types of Linked list** There are different types of linked list. We can put linked lists into the following four types: \(1) Singly linked list \(2) Circular Linked list \(3) Doubly Linked list \(4) Circular Doubly linked list **1.6.1 Singly linked list** An element in a linked list is specially termed as a node. **In a singly linked list, each node consists of two fields:** **(1) DATA field that contains the actual information of the element.** **(2) Next field, contains the address of the next node in the list.** **1.6.2 Declaring a Singly Linked list**  In C language, a linked list can be implemented using structure and pointers. struct LinkedList { int data; struct LinkedList \*next; }; The above definition is used to create every node in the list. The **data** field stores the element and the **next** is a pointer to store the address of the next node. **Exercise 1: Create a linked List by inserting nodes at the Beginning** The following program uses two functions to **[insert new links (nodes) at the beginning of the list] *insertAtBegin* [and then print the list]** data using the function ***print list.*** **Read, understand and then write and execute the following code** 1. \#include \ 2. \#include \ 3. struct node { 4. int data; 5. struct node \*next; 6. }; 7. struct node \*head = NULL; 8. struct node \*current = NULL; 9. //The function display the list 10. void printList() 11. { 12. struct node \*ptr = head; 13. printf(\"\\n\[head\] =\>\"); 14. //start from the beginning 15. while(ptr != NULL) 16. { 17. printf(\" %d =\>\",ptr-\>data); 18. ptr = ptr-\>next; 19. } 20. printf(\" \[null\]\\n\"); 21. } 22. //The function insert link at the first location of 23. void insertAtBegin(int data) { 24. //create a link (or node) 25. struct node \*link = (struct node\*) malloc(sizeof(struct node)); 26. link-\>data = data; 27. //let the new node point to the first node pointed to by head 28. link-\>next = head; 29. //let the new node be the first node 30. head = link; 31. } 32. // The main 33. int main() 34. { 35. insertAtBegin(10); 36. insertAtBegin (20); 37. insertAtBegin (30); 38. insertAtBegin (1); 39. insertAtBegin (40); 40. insertAtBegin (56); 41. printList(); 42. return 0; 43. } **Output** Output of the program should be − \[head\] =\> 56 =\> 40 =\> 1 =\> 30 =\> 20 =\> 10 =\> \[null\] **Exercise 2: Create a linked List by Inserting Nodes at the End of the List** The following program uses two functions to **[insert new links (nodes) at the end of the list] *insertAtEnd* [and then count the size of the list]** data using the function ***SizeOfList.*** **Read, understand and then write and execute the following code** 1. \#include \ 2. \#include \ 3. struct node 4. { 5. int data; 6. struct node \*next; 7. }; 8. struct node \*head = NULL; 9. struct node \*current = NULL;// to be used to traverse the list 10. **//Create Linked List** 11. void insertAtEnd(int data) 12. { 13. **// Allocate memory for new node;** 14. struct node \*link = (struct node\*) malloc(sizeof(struct node)); 15. link-\>data = data; 16. link-\>next = NULL; 17. **// If head is empty, create new list** 18. if(head==NULL) { 19. head = link; 20. return; 21. } 22. current = head; 23. **// move to the end of the list** 24. while(current-\>next!=NULL) 25. current = current-\>next; 26. **// Insert link at the end of the list** 27. current-\>next = link; 28. } 29. void SizeOfList() 30. { 31. int size = 0; 32. if(head==NULL) 33. { 34. printf(\"List size : %d \", size); 35. return; 36. } 37. current = head; 38. size = 1; 39. while(current-\>next!=NULL) 40. { 41. current = current-\>next; 42. size++; 43. } 44. printf(\"List size : %d \", size); 45. } 46. int void main() 47. { 48. insertAtEnd(10); 49. insertAtEnd(20); 50. insertAtEnd(30); 51. insertAtEnd(1); 52. insertAtEnd(40); 53. insertAtEnd(56); 54. sizeOfList(); 55. return 0; 56. } **Output** Size is 6 **Exercise 3: Create a linked List by Inserting Nodes at the End of the List** The following program uses two functions to **[insert new links (nodes) at the end of the list] *insert* [ and then we search the list]** data using the function ***find\_data.*** **Read, understand and then write and execute the following code** 1. \#include \ 2. \#include \ 3. struct node 4. { 5. int data; 6. struct node \*next; 7. }; 8. struct node \*head = NULL; 9. struct node \*current = NULL; 10. //Create Linked List 11. void insert(int data) 12. { 13. // Allocate memory for new node; 14. struct node \*link = (struct node\*) malloc(sizeof(struct node)); 15. link-\>data = data; 16. link-\>next = NULL; 17. // If head is empty, create new list 18. if(head==NULL) 19. { 20. head = link; 21. return; 22. }//end if 23. current = head; 24. // move to the end of the list 25. while(current-\>next!=NULL) 26. current = current-\>next; 27. // Insert link at the end of the list 28. current-\>next = link; 29. }// end insert function 30. void find\_data(int item) 31. { 32. int pos = 0; 33. if(head==NULL) 34. { 35. printf(\"Linked List not initialized\"); 36. return; 37. } 38. current = head; 39. while(current-\>next!=NULL) 40. { 41. if(current-\>data == item) 42. { 43. printf(\"%d found at position %d\\n\", item, pos); 44. return; 45. }// end if 46. current = current-\>next; 47. pos++; 48. } //end while 49. printf(\"%d does not exist in the list\", item); 50. }// end find\_data function 51. int void main() 52. { 53. insert(10); 54. insert(20); 55. insert(30); 56. insert(1); 57. insert(40); 58. insert(56); 59. find\_data(40); 60. find\_data(44); 61. return 0; 62. }// end main **Output** 40 found at position 4 44 does not exist in the list **Lab Assessment (1)** **The following steps shows how an element with a given value can be deleted from the linked list**\> 1. Here, we already have a value that needs to be deleted from the list. The main thing is that we'll delete only the first occurrence. 2. Create a struct Node\* function *deleteByValue* which will return the pointer to the head. 3. Pass into this function the head node, the value which needs to be deleted. 4. Create a new struct Node\* pointer *p* pointing to the head. 5. Create another struct Node\* pointer q pointing to the next of head. 6. Run a while loop until the pointer q encounters the given value or the list finishes. 7. If it encounters the value, delete that node by making p point the next node, skipping the node q. And free q from memory. 8. And if the list just finishes, it means there was no such value in the list. Continue without doing anything. 9. Return head **// The function code for deleting the element with a given value from the linked list** 1. struct Node \* deleteByValue(struct Node \* head, int value) 2. { 3. struct Node \*p = head; 4. struct Node \*q = head-\>next; 5. while(q-\>data!=value && q-\>next!= NULL) 6. { 7. p = p-\>next; 8. q = q-\>next; 9. } 10. if(q-\>data == value){ 11. p-\>next = q-\>next; 12. free(q); 13. } 14. return head; 15. } **Assignment** Write a complete program that uses the above given program and test your program. **Lab Assessment (2)** Students has to write and execute the C code for the following exercise as an in-lab assessment. Instructor has to evaluate students work immediately. Write a program that uses two functions, the first function ***insert*** to insert new links (nodes) at the end of the list and the function ***remove\_data*** to remove a data item from the list. If the data item is not in the list an appropriate message has to be sent. The program allow the user to insert the data 10, 20, 30, 1, 40, 56, and ask the user to insert the number to be deleted. The **Output of the program should be as shown below if the user want to remove 30.** Before Removal : \[head\] =\> 10 =\> 20 =\> 30 =\> 1 =\> 40 =\> 56 =\> \[null\] After Removal : \[head\] =\> 10 =\> 20 =\> 1 =\> 40 =\> 56 =\> \[null\] **Lab (2): Linked Lists -- Circular Linked Lists** **Description** This lab is to demonstrate to students how to implement Circular linked lists. **Lab (2): Learning Outcomes** By the end of this lab the student must be able to: - Define what is a circular linked list? - Compare Circular linked lists to singly linked lists. - Write C codes that create and manipulate different types of linked lists. **Lab (2): What Instructor has to do** The instructor has to: - Follow the steps below to demonstrate to the students how to use C to implement circular linked lists - Explain to the students the stated circular lists concepts and definitions. - Supervise students while they write and run all C codes in this lab. **2.1 Circular Linked List** **A circular linked list is a linked list where the last element points to the first element (head) hence forming a circular chain**. There is no node pointing to the NULL, indicating the absence of any end node. In circular linked lists, we have a head pointer but no starting of this list. Refer to the illustration of a circular linked list below:  **2.2 Operations on a Circular Linked List** Operations on circular linked lists can be performed exactly like a singly linked list. It's just that we have to maintain an extra pointer to check if we have gone through the list once. **2.2.1 Traversal** - Traversal in a circular linked list can be achieved by creating a new struct Node\* pointer p, which starts from the head and goes through the list until it points again at the head. So, this is how we go through this circle only once, visiting each node. - And since traversal is achieved, all the other operations in a circular linked list become as easy as doing things in a linear linked list.  - One thing that may have sounded confusing to you is that there is a head but no starting of this circular linked list. Yes, that is the case; we have this head pointer just to start while operating on it. There is no first element here. **2.3 Creating the circular linked list:** 1. Creating a circular linked list is no different from creating a singly linked list. One thing we do differently is that instead of having the last element to point to NULL, we'll make it point to the head. 2. Refer to those previous tutorials while creating these nodes and connecting them. This is the third time we are doing it, and I believe you must have gained that confidence. **2.4 Traversing the Circular Linked List** 1. Create a void function *linkedListTraversal *and pass the head pointer of the linked list to the function. 2. In the function, create a pointer *ptr* pointing to the head. 3. Run a *do-while* loop until *ptr *reaches the last node, and ptr-\> next becomes head, i.e. ptr-\>next = head. And keep printing the data of each node. 4. So, this is how we traverse through a circular linked list. And *do-while* was the key to make it possible. **Traversing a Circular Linked List Code** void linkedListTraversal(struct Node \*head) { struct Node \*ptr = head; do { printf(\"Element is %d\\n\", ptr-\>data); ptr = ptr-\>next; } while(ptr!=head); } **Exercise 1: Search a Circular linked List for a given Item** The following program uses two functions to **[insert new links (nodes) at the end of the list] *insert* [an then search for a]** data item using the function ***find\_data.*** **Read, understand and then write and execute the following code** 1. \#include \ 2. \#include \ 3. struct node { 4. int data; 5. struct node \*next; 6. }; 7. struct node \*head = NULL; 8. struct node \*current = NULL; 9. //insert link at the first location function 10. void insert(int data) 11. { 12. // Allocate memory for new node; 13. struct node \*link = (struct node\*) malloc(sizeof(struct node)); 14. link-\>data = data; 15. link-\>next = NULL; 16. // If head is empty, create new list 17. if(head==NULL) 18. { 19. head = link; 20. head-\>next = link; 21. return; 22. } 23. current = head; 24. // move to the end of the list 25. while(current-\>next != head) 26. current = current-\>next; 27. // Insert link at the end of the list 28. current-\>next = link; 29. // Link the last node back to head 30. link-\>next = head; 31. } 32. //display the list 33. void find\_data(int item) 34. { 35. int pos = 0; 36. if(head == NULL) 37. { 38. printf(\"Linked List not initialized\"); 39. return; 40. } 41. current = head; 42. while(current-\>next != head) 43. { 44. if(current-\>data == item) { 45. printf(\"%d found at position %d\\n\", item, pos); 46. return; 47. } 48. current = current-\>next; 49. pos++; 50. } 51. if(current-\>data == item) { 52. printf(\"%d found at position %d\\n\", item, pos); 53. return; 54. } 55. printf(\"%d does not exist in the list\", item); 56. } 57. int main() 58. { 59. insert(10); 60. insert(20); 61. insert(30); 62. insert(1); 63. insert(40); 64. insert(56); 65. find\_data(56); 66. return 0; 67. } //end main **Output** Output of the program should be − 56 found at position 5 **2.5 Deletion in Circular Linked List in C** There is three ways to delete the node in circular linked list like doubly or singly linked list. - Deletion at beginning - Deletion at a given position - Deletion at end **2.5.1 Deletion at the beginning** The figure below shows the deletion at the beginning **Exercise 2: Deleting the first node of the linked list.** To delete the first node, the ***next*** pointer of the last node will point to the second node of the linked list.   Below is the implementation of the above operation: **Read, understand and then write and execute the following code** 1. // C program for the above operation 2. \#include \ 3. \#include \ 4. // Structure of a linked list node 5. struct node { 6. }; 7. // Pointer to last node in list 8. struct node\* last = NULL; 9. // Function to add a new node at the end of the list 10. void add-at-last(int data) 11. { // Initialize a new node struct node\* temp; 12. } //end of the function 13. // Function to delete the first element of the list 14. void delete-first() 15. { 16. } 17. // Function to print the list 18. void print-list() 19. { 20. } 21. // Driver Code 22. int main() 23. { 24. } **Output** Before deletion: Data = 10 Data = 20 Data = 30 After deletion: Data = 20 Data = 30 **Lab Assessment** Write a C program that deletes an element from a specified position (index) in the linked list. Use the functions defined in the above program. The output of your program should be as shown below: Enter data to be inserted: 10 Enter data to be inserted: 20 Enter data to be inserted: 30 Enter item index to be removed: 1 Data in the circular list after removal: 10 30 **Lab (3): Stacks** **Description** This lab is to demonstrate to students how to implement stacks. **Lab (3): Learning Outcomes** By the end of this lab the student must be able to: - Define what is a stack? - Compare stacks to linked lists. - Write C codes that create and manipulate stacks. **Lab (3): What Instructor has to do** The instructor has to: - Follow the steps below to demonstrate to the students how to use C to implement stacks. - Explain to the students the stated stacks concepts and definitions. - Supervise students while they write and run all C codes in this lab. **3.1 Introduction** A stack is a one of the most important and useful non-primitive linear data structure in computer science. Real-life examples of the stack are a stack of books, a stack of plates, a stack of cards, a stack of coins, etc. ***Definition:* A stack is a sequential collection of elements into which new elements are inserted and from which, elements are deleted only at one end.** As all the insertion and deletion in a stack is done from the top of the stack, the lastly added element will be first to be removed from the stack. **That is the reason why stack is also called Last-InFirst-Out (LIFO) data structure.** Note that the most frequently accessed element in the stack is the top most elemental, whereas the least accessible element is the bottom of the stack. **[In the stack, the top variable is used to point the top of the stack]**. The following tasks are performed by the top variable: To keep track, how many cells are used, Whether the stack is full or empty Insert new element in the stack Delete elements from the stack **3.2 Operations on Stack** The stack is an abstract data type since it is defined in terms of operations on it and its implementation is hidden. [Therefore, we can implement a stack using either array or linked list]. The stack includes a finite sequence of the same type of items with the different operations described in table 6.1.  **The insertion (or addition) operation is [referred as push], and the deletion (or remove) [operation as pop]**. A stack is said to be empty if the stack contains no elements. At this point, the top of the stack is present at the bottom of the stack. In addition, it is full when the stack becomes full, i.e., no other elements can be pushed onto the stack. At this point, the top pointer is at the highest location of the stack. https://cwh-full-next-space.fra1.digitaloceanspaces.com/videos/data-structures-and-algorithms-in-hindi-19/Image\_1.webp **3.3 Stack Representation with Array** The array can be used to **[implement a stack of fixed size]**, therefore only fixed a number of data items can be pushed and popped. The stack can be represented using the following structure: struct STACK { int a\[MAXSIZE\]; int top; }; **3.4 Stack Insertion: push()** The push() is an operation that inserts elements into the stack. The following is an algorithm that describes the push() operation in a simpler way. **Algorithm** 1\. Checks if the stack is full. 2\. If the stack is full, produces an error and exit. 3\. If the stack is not full, increments top to point next empty space. 4\. Adds data element to the stack location, where top is pointing. 5\. Returns success. **Exercise 1: Create a stack and push() elements into it** **Read, understand and then write and execute the following code** 1. \#include \ 2. int MAXSIZE = 8; 3. int stack\[8\]; 4. int top = -1; 5. /\* Check if the stack is full\*/ 6. int isfull() 7. { 8. if(top == MAXSIZE) 9. return 1; 10. else 11. return 0; 12. } 13. /\* Function to insert into the stack \*/ 14. int push(int data) 15. { 16. if(!isfull()) 17. { 18. top = top + 1; 19. stack\[top\] = data; 20. } else 21. { 22. printf(\"Could not insert data, Stack is full.\\n\"); 23. } 24. } 25. /\* Main function \*/ 26. int void main() 27. { 28. int i; 29. push(44); 30. push(10); 31. push(62); 32. push(123); 33. push(15); 34. printf(\"Stack Elements: \\n\"); 35. // print stack data 36. for(i = 0; i \< 8; i++) { 37. printf(\"%d \", stack\[i\]); 38. } 39. return 0; 40. } 41. **Output:** Stack Elements: 44 10 62 123 15 0 0 0 **3.5 Stack Deletion: pop()** The *pop()* is a data manipulation operation which removes elements from the stack. The following pseudo code describes the pop() operation in a simpler way. **Algorithm** 1\. Checks if the stack is empty. 2\. If the stack is empty, produces an error and exit. 3\. If the stack is not empty, accesses the data element at which top is pointing. 4\. Decreases the value of top by 1. 5\. Returns success. **Exercise 2: Create a stack and push() and pop() elements into and from it** **Read, understand and then write and execute the following code** 1. \#include \ 2. int MAXSIZE = 8; 3. int stack\[8\]; 4. int top = -1; 5. /\* Check if the stack is empty \*/ 6. int isempty() 7. { 8. if(top == -1) 9. return 1; 10. else 11. return 0; 12. } 13. /\* Check if the stack is full\*/ 14. int isfull() 15. { 16. if(top == MAXSIZE) 17. return 1; 18. else 19. return 0; 20. } 21. /\* Function to delete from the stack \*/ 22. int pop() 23. { 24. int data; 25. if(!isempty()) { 26. data = stack\[top\]; 27. top = top - 1; 28. return data; 29. } else { 30. printf(\"Could not retrieve data, Stack is empty.\\n\"); 31. } 32. } 33. /\* Function to insert into the stack \*/ 34. int push(int data) 35. { 36. if(!isfull()) { 37. top = top + 1; 38. stack\[top\] = data; 39. } else { 40. printf(\"Could not insert data, Stack is full.\\n\"); 41. } 42. } 43. /\* Main function \*/ 44. int void main() 45. { 46. int i; 47. push(44); 48. push(10); 49. push(62); 50. push(123); 51. push(15); 52. printf(\"Stack Elements: \\n\"); 53. // print stack data 54. for(i = 0; i \< 8; i++) { 55. printf(\"%d \", stack\[i\]); 56. } 57. /\*printf(\"Element at top of the stack: %d\\n\" ,peek());\*/ 58. printf(\"\\nElements popped: \\n\"); 59. // print stack data 60. while(!isempty()) { 61. int data = pop(); 62. printf(\"%d \",data); 63. } 64. return 0; } **Output** Stack Elements: 44 10 62 123 15 0 0 0 Elements popped: 15 123 62 10 44 **3.6 Retrieving topmost Element from Stack: peek()** The *peek()* is an operation retrieves the topmost element within the stack, without deleting it. This operation is used to check the status of the stack with the help of the top pointer. **Algorithm** 1\. START 2\. return the element at the top of the stack 3\. END **Exercise 3: C code to return the top of the stack** **Read, understand and then write and execute the following code** 1. \#include \ 2. int MAXSIZE = 8; 3. int stack\[8\]; 4. int top = -1; 5. /\* Check if the stack is full \*/ 6. int isfull() 7. { 8. if(top == MAXSIZE) 9. return 1; 10. else 11. return 0; 12. } 13. /\* Function to return the topmost element in the stack \*/ 14. int peek() 15. { 16. return stack\[top\]; 17. } 18. /\* Function to insert into the stack \*/ 19. int push(int data) 20. { 21. if(!isfull()) 22. { 23. top = top + 1; 24. stack\[top\] = data; 25. } else 26. { 27. printf(\"Could not insert data, Stack is full.\\n\"); 28. } 29. } 30. /\* Main function \*/ 31. int main() 32. { 33. int i; 34. push(44); 35. push(10); 36. push(62); 37. push(123); 38. push(15); 39. printf(\"Stack Elements: \\n\"); 40. // print stack data 41. for(i = 0; i \< 8; i++) { 42. printf(\"%d \", stack\[i\]); 43. } 44. printf(\"\\nElement at top of the stack: %d\\n\" ,peek()); 45. return 0; 46. } **Output** Stack Elements: 44 10 62 123 15 0 0 0 Element at top of the stack: 15 **3.7 Parenthesis Checking of Mathematical Expressions Using Stack** To check parentheses matching in a mathematical expressions such as (3 + 9 \*( A-X) ) we can follow this simple algorithm: 1. Read the expression from left to right We call this match of **parentheses unbalanced** when we encounter either of the two of these troubles: 1. There is no more opening bracket inside the stack to pop, and you read a closing bracket. 2. The stack size is not zero, or there are still more than zero opening brackets present in the stack after you read EOE (end-of-expression). **Exercise 4: C code for Parenthesis Checking** **Read, understand and then write and execute the following code** 1. / /C program  to check the balanced parenthesis.   2. \#include\   3. **int** main()   4. {   5.     **char** expression\[50\]; // declaration of char type array   6.     **int** x=0, i=0; // declaration of two integer type variables   7.     printf(\"\\nEnter an expression\");   8.     scanf(\"%s\", expression);   9. // Scanning the expression until we reach the end of the expression.      10.  **while**(expression\[i\]!= \'\\0\')   11.     {   12.     // Condition to check the symbol is \'(\'      13.      **if**(expression\[i\]==\'(\')   14.         {   15.             x++;    // incrementing \'x\' variable    16.         }   17.      // condition to check the symbol is \')\'      18.      **else** **if**(expression\[i\]==\')\')   19.         {   20.             x\--;   // decrementing \'x\' variable   21.             **if**(x\ rear) {   21.         printf(\"Queue is empty\");   22.         **return** -1;   23.     }   24.     **int** element = queue\[front\];   25.     front++;   26.     **return** element;   27. }   28.    29. **int** main() {   30.     enqueue(10);   31.     enqueue(20);   32.     enqueue(30);   33.     printf(\"%d \", dequeue());   34.     printf(\"%d \", dequeue());   35.     printf(\"%d \", dequeue());   36.     printf(\"%d \", dequeue());   37.     **return** 0;   38. }   **Output** 10 20 30 Queue is empty-1 **4.4 Circular Queue** A circular queue is similar to a linear queue as it is also based on the FIFO (First In First Out) principle except that the last position is connected to the first position in a circular queue that forms a circle. It is also known as a ***Ring Buffer***. **4.4.1 Operations on Circular Queue** The following are the operations that can be performed on a circular queue: - **Front:** It is used to get the front element from the Queue. - **Rear:** It is used to get the rear element from the Queue. - **enQueue(value):** This function is used to insert the new value in the Queue. The new element is always inserted from the rear end. - **deQueue():** This function deletes an element from the Queue. The deletion in a Queue always takes place from the front end. **4.4.2 Applications of Circular Queue** **The circular Queue can be used in the following scenarios:** - **Memory management:** The circular queue provides memory management. As we have already seen that in linear queue, the memory is not managed very efficiently. But in case of a circular queue, the memory is managed efficiently by placing the elements in a location which is unused. - **CPU Scheduling:** The operating system also uses the circular queue to insert the processes and then execute them. - **Traffic system:** In a computer-control traffic system, traffic light is one of the best examples of the circular queue. Each light of traffic light gets ON one by one after every jinterval of time. Like red light gets ON for one minute then yellow light for one minute and then green light. After green light, the red light gets ON. **4.4.3 Enqueue Operation** Enqueue Algorithm to insert an element in a circular queue Add an element to the rear of the circular queue. Steps: - Check if the queue is full. If (rear + 1) % size == front, the queue is full. - If the queue is not full, update the rear pointer to (rear + 1) % size. - Insert the new element at the rear position. - If the queue was initially empty (i.e., front was -1), set front to 0. **4.4.5 Dequeue Operation** Dequeue (Removing an element) Remove an element from the front of the circular queue. Steps: - Check if the queue is empty. If front == -1, the queue is empty. - If the queue is not empty, remove the element at the front position. - Update the front pointer to (front + 1) % size. - If the queue becomes empty after the dequeue operation (i.e., front equals rear), reset both front and rear to -1**.** **Exercise 1: Implementation of Circular Queue Using Array** **Read, understand and write and execute the following code.** 1. \#include \   2.    3. \# define max 6   4. **int** queue\[max\];  // array declaration   5. **int** front=-1;   6. **int** rear=-1;   7. // function to insert an element in a circular queue   8. **void** enqueue(**int** element)   9. {   10.     **if**(front==-1 && rear==-1)   // condition to check queue is empty   11.     {   12.         front=0;   13.         rear=0;   14.         queue\[rear\]=element;   15.     }   16.     **else** **if**((rear+1)%max==front)  // condition to check queue is full   17.     {   18.         printf(\"Queue is overflow..\");   19.     }   20.     **else**   21.     {   22.         rear=(rear+1)%max;       // rear is incremented   23.         queue\[rear\]=element;     // assigning a value to the queue at the rear position.   24.     }   25. }   26.    27. // function to delete the element from the queue   28. **int** dequeue()   29. {   30.     **if**((front==-1) && (rear==-1))  // condition to check queue is empty   31.     {   32.         printf(\"\\nQueue is underflow..\");   33.     }   34.  **else** **if**(front==rear)   35. {   36.    printf(\"\\nThe dequeued element is %d\", queue\[front\]);   37.    front=-1;   38.    rear=-1;   39. }    40. **else**   41. {   42.     printf(\"\\nThe dequeued element is %d\", queue\[front\]);   43.    front=(front+1)%max;   44. }   45. }   46. // function to display the elements of a queue   47. **void** display()   48. {   49.     **int** i=front;   50.     **if**(front==-1 && rear==-1)   51.     {   52.         printf(\"\\n Queue is empty..\");   53.     }   54.     **else**   55.     {   56.         printf(\"\\nElements in a Queue are :\");   57.         **while**(i\next=0;   17.     **if**(rear==-1)  // checking whether the Queue is empty or not.   18.     {   19.         front=rear=newnode;   20.         rear-\>next=front;   21.     }   22.     **else**   23.     {   24.         rear-\>next=newnode;   25.         rear=newnode;   26.         rear-\>next=front;   27.     }   28. }   29.    30. // function to delete the element from the queue   31. **void** dequeue()   32. {   33.     **struct** node \*temp;   // declaration of pointer of node type   34.     temp=front;   35.     **if**((front==1)&&(rear=1))  // checking whether the queue is empty or not   36.     {   37.         printf(\"\\nQueue is empty\");   38.     }   39.     **else** **if**(front==rear)  // checking whether the single element is left in the queue   40.     {   41.         front=rear=-1;   42.         free(temp);   43.     }   44.     **else**   45.     {   46.         front=front-\>next;   47.         rear-\>next=front;   48.         free(temp);   49.     }   50. }   51.    52. // function to get the front of the queue   53. **int** peek()   54. {   55.     **if**((front==-1) &&(rear==-1))   56.     {   57.         printf(\"\\nQueue is empty\");   58.     }   59.     **else**   60.     {   61.         printf(\"\\nThe front element is %d\", front-\>data);   62.     }   63. }   64.    65. // function to display all the elements of the queue   66. **void** display()   67. {   68.     **struct** node \*temp;   69.     temp=front;   70.     printf(\"\\n The elements in a Queue are : \");   71.     **if**((front==-1) && (rear==-1))   72.     {   73.         printf(\"Queue is empty\");   74.     }   75.    76.     **else**    77.     {   78.         **while**(temp-\>next!=front)   79.         {   80.             printf(\"%d,\", temp-\>data);   81.             temp=temp-\>next;   82.         }   83.         printf(\"%d\", temp-\>data);   84.     }   85. }   86.    87. **void** main()   88. {   89.     enqueue(34);    90.     enqueue(10);   91.     enqueue(23);   92.     display();    93.     dequeue();    94.     peek();   95. }   **Output:** The elements in a Queue are: 34,10,23 The front element is 10 **Lab (5): Priority Queues** **Description** This lab is to demonstrate to students how to implement priority queues in C Language. **Lab (5): Learning Outcomes** By the end of this lab the student must be able to: - Define what is a priority queue? - Compare priority queues to Linear and circular queues. - Write C codes that create and manipulate priority queues. **Lab (5): What Instructor has to do** The instructor has to: - Follow the steps below to demonstrate to the students how to use C to implement priority queues. - Explain to the students the stated priority queues concepts and definitions. - Supervise students while they write and run all C codes in this lab. **5.1 Priority Queues** A Priority Queue is a collection of elements such that each element has been assigned a priority and the elements are arranged on the basis of priority. The order in which elements are deleted and processed comes from the following rules: 1. The element having a higher priority is processed before any elements of lower priority. 2. The two elements that have the same priority are processed according to the order in which that are inserted into the priority queue. There are two types of priority queue: 1. **Ascending priority queue:** In this type of the priority queue, the elements can be inserted arbitrarily, but only the element with the smallest priority can be removed. 2. **Descending priority queue:** In this type of the priority queue, the elements can be inserted arbitrarily, but only the element with the highest priority can be removed. **5.2 Priority Queue Operations** A priority queue is an abstract concept**[. A priority queue can be implemented with an array, a linked list or a heap]**. Priority Queue supports the operations as follows:  **5.3 Implementation of Priority Queue as a Heap** Priority queue can be implemented using an array, a linked list, a heap data structure, or a binary search tree. Among these data structures, heap data structure provides an efficient implementation of priority queues. We will be using **the heap data structure to implement the priority queue in this** lab. **5.4 Heap Data Structure** Heap data structure **[is [a complete binary tree](https://www.programiz.com/dsa/complete-binary-tree) that]** satisfies the heap property, where any given node is - Always greater than its child node/s and the key of the root node is the largest among all other nodes. **[This property is also called max heap property.]** - Always smaller than the child node/s and the key of the root node is the smallest among all other nodes. **[This property is also called min heap property]**. This type of data structure is also called a **binary heap**. **5.5 Complete Binary Tree** **A complete binary tree is a binary tree in which all the levels are completely filled except possibly the lowest one, which is filled from the left.** 1. All the leaf elements must lean towards the left. 2. The last leaf element might not have a right sibling i.e. a complete binary tree doesn\'t have to be a full binary tree. 3. Complete Binary Tree Complete Binary Tree Where the following graph shows a full binary tree  **9.4.1.2 How a Complete Binary Tree is Created?** 1. Select the first element of the list to be the root node. (no. of elements on level-I: 1)Complete binary tree creation Select the first element as root 2. Put the second element as a left child of the root node and the third element as the right child. (no. of elements on level-II: 2) 12 as a left child and 9 as a right child 3. Put the next two elements as children of the left node of the second level. Again, put the next two elements as children of the right node of the second level (no. of elements on level-III: 4) elements). 4. Keep repeating until you reach the last element.Complete binary tree creation 5 as a left child and 6 as a right child **9.5 Heap Operations (Priority Queue Operations)** Some of the important operations performed on a heap are described below along with their algorithms. **9.5.1 Heapify** Heapify is the process of creating a heap data structure from a binary tree. It is used to create a Min-Heap or a Max-Heap. The steps are: **Algorithm** 1. Heapify(array, size, i) 2. set i as largest 3. leftChild = 2i + 1 4. rightChild = 2i + 2 5. if leftChild \> array\[largest\] 6. set leftChildIndex as largest 7. if rightChild \> array\[largest\] 8. set rightChildIndex as largest 9. swap array\[i\] and array\[largest\] To create a Max-Heap: 1. MaxHeap(array, size) 2. loop from the first index of non-leaf node down to zero 3. call heapify For Min-Heap, both leftChild and rightChild must be larger than the parent for all nodes. **Exercise 1: C Implementation of Heapify** 1. // Function to heapify the tree 2. void heapify(int array\[\], int size, int i) { 3. if (size == 1) { 4. printf(\"Single element in the heap\"); 5. } else { 6. // Find the largest among root, left child and right child 7. int largest = i; 8. int l = 2 \* i + 1; 9. int r = 2 \* i + 2; 10. if (l \< size && array\[l\] \> array\[largest\]) 11. largest = l; 12. if (r \< size && array\[r\] \> array\[largest\]) 13. largest = r; 14. // Swap and continue heapifying if root is not largest 15. if (largest != i) { 16. swap(&array\[i\], &array\[largest\]); 17. heapify(array, size, largest); 18. } 19. } 20. } **Insert Element into Heap** **[Algorithm for insertion in Max Heap]** If there is no node, create a newNode. else (a node is already present) insert the newNode at the end (last node from left to right.) heapify the array **Exercise 2: C Implementation of Insert()** **Read, understand the following code** 1. // Function to insert an element into the tree 2. void insert(int array\[\], int newNum) { 3. if (size == 0) { 4. array\[0\] = newNum; 5. size += 1; 6. } else { 7. array\[size\] = newNum; 8. size += 1; 9. for (int i = size / 2 - 1; i \>= 0; i\--) { 10. heapify(array, size, i); 11. } 12. } 13. } **Delete Element from Heap** **Algorithm for deletion in Max Heap** If nodeToBeDeleted is the leafNode remove the node Else swap nodeToBeDeleted with the lastLeafNode remove noteToBeDeleted heapify the array **Exercise 3: C Implementation of delete()** **Read, understand the following code** 1. // Function to delete an element from the tree 2. void deleteRoot(int array\[\], int num) { 3. int i; 4. for (i = 0; i \< size; i++) { 5. if (num == array\[i\]) 6. break; 7. } 8. swap(&array\[i\], &array\[size - 1\]); 9. size -= 1; 10. for (int i = size / 2 - 1; i \>= 0; i\--) { 11. heapify(array, size, i); 12. } 13. } **Exercise 4: C Implementation of a Priority Queue** **Read, understand and then write and execute the following code** 1. \#include \ 2. int size = 0; 3. void swap(int \*a, int \*b) { 4. int temp = \*b; 5. \*b = \*a; 6. \*a = temp; 7. } 8. // Function to heapify the tree 9. void heapify(int array\[\], int size, int i) { 10. if (size == 1) { 11. printf(\"Single element in the heap\"); 12. } else { 13. // Find the largest among root, left child and right child 14. int largest = i; 15. int l = 2 \* i + 1; 16. int r = 2 \* i + 2; 17. if (l \< size && array\[l\] \> array\[largest\]) 18. largest = l; 19. if (r \< size && array\[r\] \> array\[largest\]) 20. largest = r; 21. // Swap and continue heapifying if root is not largest 22. if (largest != i) { 23. swap(&array\[i\], &array\[largest\]); 24. heapify(array, size, largest); 25. } 26. } 27. } 28. // Function to insert an element into the tree 29. void insert(int array\[\], int newNum) { 30. if (size == 0) { 31. array\[0\] = newNum; 32. size += 1; 33. } else { 34. array\[size\] = newNum; 35. size += 1; 36. for (int i = size / 2 - 1; i \>= 0; i\--) { 37. heapify(array, size, i); 38. } 39. } 40. } 41. // Function to delete an element from the tree 42. void delete (int array\[\], int num) { 43. int i; 44. for (i = 0; i \< size; i++) { 45. if (num == array\[i\]) 46. break; 47. } 48. swap(&array\[i\], &array\[size - 1\]); 49. size -= 1; 50. for (int i = size / 2 - 1; i \>= 0; i\--) { 51. heapify(array, size, i); 52. } 53. } 54. // Print the array 55. void printArray(int array\[\], int size) { 56. for (int i = 0; i \< size; ++i) 57. printf(\"%d \", array\[i\]); 58. printf(\"\\n\"); 59. } 60. // Driver code 61. int main() { 62. int array\[10\]; 63. insert(array, 3); 64. insert(array, 4); 65. insert(array, 9); 66. insert(array, 5); 67. insert(array, 2); 68. printf(\"Max-Heap array: \"); 69. printArray(array, size); 70. delete (array, 4); 71. printf(\"After deleting an element: \"); 72. printArray(array, size); 73. } **Lab (6): Searching** **Description** This lab is to demonstrate to students how to implement search algorithms. **Lab (6): Learning Outcomes** By the end of this lab the student must be able to: - Define searching algorithms - Compare linear and binary search algorithms. - Write C codes that implements search algorithms. **Lab (6): What Instructor has to do** The instructor has to: - Follow the steps below to demonstrate to the students how to use C to implement search algorithms. - Explain to the students the stated search algorithms. - Supervise students while they write and run all C codes in this lab. **6.1 Introduction** Searching for items and sorting through items are tasks that we do every day. We search for all occurrences of a word in a file in order to replace it with another word. We sort the items on a list into alphabetical or numerical order. Searching and sorting are also most common operations in computer programs. **6.2 Searching** Searching refers to the operation of finding the location of the desired key element within some data structures. Data structures can include linked lists, arrays, search trees or hash tables. The search is successful if the item is found, and then returns its location; otherwise, the search is unsuccessful. The appropriate search algorithms often depends on the data structure being searched. There are many searching algorithms, the most common two are: Linear Search Binary Search **6.3 Linear Search** Linear search, or sequential search is a method for finding the position of a particular key value in a list, where the search starts from beginning of the list and checking every element, one at a time in sequence until the desired key is found or the end of the list is reached. **[Algorithm for Linear Search Algorithm:]** The algorithm for linear search can be broken down into the following steps: - **Start:** Begin at the first element of the collection of elements. - **Compare:** Compare the current element with the desired element. - **Found:** If the current element is equal to the desired element, return true or index to the current element. - **Move: **Otherwise, move to the next element in the collection. - **Repeat:** Repeat steps 2-4 until we have reached the end of collection. - **Not found:** If the end of the collection is reached without finding the desired element, return that the desired element is not in the array. **[Implementation of Linear Search Algorithm:]** In Linear Search, we iterate over all the elements of the array and check if it the current element is equal to the target element. If we find any element to be equal to the target element, then return the index of the current element. Otherwise, if no element is equal to the target element, then return -1 as the element is not found. Below is the implementation of the linear search algorithm: **Exercise 1: C implementation of Linear Search** 1. */\* C program to find the minimum element in an array using Linear Search \*\** 3. \*  \* C program accept an array of N elements and a key to search.* 4. \*  \* If the search is successful, it displays \"SUCCESSFUL SEARCH\".* 5. \*  \* Otherwise, a message \"UNSUCCESSFUL SEARCH\" is displayed.* 6. \*  \*\* search begins \*/* 28.   29. low = 0; 30. high = (size - 1); 31.   32. while (low \