Part 3 add_node(&head, 30);
4(a) Here's an algorithm/program to create a single linked list and find out the add_node(&head, 40);
largest element in C programming language:
add_node(&head, 50);
#include <stdio.h>
// Find the largest element in the linked list
#include <stdlib.h>
int largest = find_largest_element(head);
// Define the structure for a node in the linked list
printf("The largest element in the linked list is %d\n", largest);
struct node {
return 0;
int data;
}
struct node *next;
4(b) Here's an algorithm/program to create a single linked list and search for an
}; element in C programming language:
// Function to create a new node and return a pointer to it #include <stdio.h>
struct node* create_node(int data) { #include <stdlib.h>
struct node *new_node = (struct node*) malloc(sizeof(struct node)); // Define the structure for a node in the linked list
new_node->data = data; struct node {
new_node->next = NULL; int data;
return new_node; struct node *next;
} };
// Function to add a new node to the end of the linked list // Function to create a new node and return a pointer to it
void add_node(struct node **head, int data) { struct node* create_node(int data) {
struct node *new_node = create_node(data); struct node *new_node = (struct node*) malloc(sizeof(struct node));
if (*head == NULL) { new_node->data = data;
*head = new_node; new_node->next = NULL;
return; return new_node;
} }
struct node *last_node = *head; // Function to add a new node to the end of the linked list
while (last_node->next != NULL) { void add_node(struct node **head, int data) {
last_node = last_node->next; struct node *new_node = create_node(data);
} if (*head == NULL) {
last_node->next = new_node; *head = new_node;
} return;
// Function to find the largest element in the linked list }
int find_largest_element(struct node *head) { struct node *last_node = *head;
int largest = head->data; while (last_node->next != NULL) {
while (head != NULL) { last_node = last_node->next;
if (head->data > largest) { }
largest = head->data; last_node->next = new_node;
} }
head = head->next; // Function to search for an element in the linked list
} int search_element(struct node *head, int element) {
return largest; while (head != NULL) {
} if (head->data == element) {
// Main function to test the linked list and find the largest element return 1; // element found
int main() { }
struct node *head = NULL; head = head->next;
// Add some elements to the linked list }
add_node(&head, 10); return 0; // element not found
add_node(&head, 20); }
// Main function to test the linked list and search for an element 22, 20, 15, 12, 10, 9, 8, 7, 4, 3
int main() {
Note that the Heap Sort technique is an in-place sorting algorithm and has a time complexity
struct node *head = NULL; of O(n log n).
// Add some elements to the linked list
Part 2
add_node(&head, 10);
2.(k)To perform a binary search for the element 10 in the given list, we need to follow these
steps:
add_node(&head, 20);
Sort the list in ascending order
add_node(&head, 30);
Set the lower bound (left) and upper bound (right) of the search range to the first and last
add_node(&head, 40);
indices of the list respectively
add_node(&head, 50);
Calculate the middle index (mid) of the search range as the average of the left and right
indices
// Search for an element in the linked list
Compare the middle element of the list to the target element (10)
int element = 30;
If the middle element is equal to the target element, return the index of the middle element
if (search_element(head, element)) {
If the middle element is greater than the target element, set the new upper bound (right) to
printf("The element %d is found in the linked list.\n", element);
the index before the middle index and repeat steps 3-5
} else {
If the middle element is less than the target element, set the new lower bound (left) to the
index after the middle index and repeat steps 3-5
printf("The element %d is not found in the linked list.\n", element);
If the target element is not found after the search range has been exhausted (left > right),
}
return -1
return 0;
Now, let's apply this algorithm to the given list:
}
Step 1: Sort the list
Q(5) To create a Maxheap from the given list, we follow the steps: 3 7 10 12 15 19 32 35 67
Step 2: Set the search range
We start by considering the second last level of the heap and apply Maxheapify on all nodes
at that level. left = 0
Next, we move up to the next level and apply Maxheapify on all nodes at that level. right = 8
Step 3: Calculate the middle index
We continue the above step till we reach the root node.
mid = (left + right) // 2 = 4
The Maxheap for the given list would look like: Step 4: Compare the middle element to the target element
list[mid] = 15 > 10
markdown
Step 7: Update the lower bound and repeat
22
left = mid + 1 = 5
/ \ right = 8
mid = (left + right) // 2 = 6
20 9
Step 4: Compare the middle element to the target element
/ \ /\
list[mid] = 32 > 10
15 10 7 4 Step 7: Update the lower bound and repeat
left = mid + 1 = 7
/ \
right = 8
3 12
mid = (left + right) // 2 = 7
To sort the given list using the Heap Sort technique, we follow the steps: list[mid] = 35 > 10
Step 7: Update the lower bound and repeat
We first create the Maxheap from the given list.
left = mid + 1 = 8
Next, we swap the root node with the last node in the heap. right = 8
Step 8: Exhausted search range, target element not found
We then remove the last node from the heap (as it is now sorted) and decrease the heap size
by 1.
return -1
We apply Maxheapify on the root node to maintain the Maxheap property. Therefore, the element 10 is not present in the given list.
2(j)A queue is a data structure that follows the First-In-First-Out (FIFO) principle, where the
We repeat the above steps till the heap size becomes 1. element that is added first is the one that gets removed first. In a linear queue, the elements
are stored in a contiguous block of memory, and there are two pointers, front and rear, that
The sorted list using the Heap Sort technique would be: keep track of the first and last elements in the queue, respectively. When an element is
added to the queue, it is inserted at the rear end, and when an element is removed from the
queue, it is removed from the front end.
In a circular queue, the elements are stored in a circular fashion instead of a linear fashion. C --- D
This means that the last element in the queue points back to the first element in the queue,
and the first element points to the last element. The front and rear pointers are still used to The adjacency list representation for this graph is as follows:
keep track of the first and last elements in the queue, but they wrap around the queue
when they reach the end. A: B, C
There are several advantages of using a circular queue over a linear queue: B: A, D
Efficient use of memory: In a circular queue, the elements are stored in a circular fashion, C: A, D
which means that the memory is utilized efficiently. If the rear pointer reaches the end of
the queue, it can wrap around to the beginning of the queue, which means that there is no D: B, C
need to move the elements in the queue to make space for new elements.
In the above representation, the vertex A has two adjacent vertices B and C, and so on.
Faster insertion and deletion: In a linear queue, if the rear pointer reaches the end of the
queue, it cannot add any more elements to the queue, even if there is space available at the Adjacency Matrix:In an adjacency matrix representation, the graph is represented by a 2D
beginning of the queue. This means that the linear queue can become full even if there is matrix of size VxV, where V is the number of vertices in the graph. The cell at row i and
still space available in the memory. In a circular queue, the rear pointer can wrap around to column j represents whether there is an edge from vertex i to vertex j or not. For an
the beginning of the queue, which means that new elements can be added to the queue unweighted graph, the cell contains either 0 or 1, where 0 represents no edge and 1
even if it is full. Similarly, in a linear queue, if the front pointer reaches the end of the queue, represents an edge. For a weighted graph, the cell contains the weight of the edge. For
it cannot remove any more elements from the queue, even if there are elements available at example, consider the same graph as above:
the beginning of the queue. In a circular queue, the front pointer can wrap around to the
beginning of the queue, which means that elements can be removed from the queue even if A --- B
it is full.
||
Implementation of circular buffer: Circular queues are used to implement circular buffers,
C --- D
which are used in embedded systems to store data in a circular fashion. A circular buffer is a
data structure that is used to store a fixed amount of data, and it is used in systems where
The adjacency matrix representation for this graph is as follows:
the memory is limited, such as in microcontrollers. A circular buffer is implemented using a
circular queue, and it allows the data to be stored and retrieved efficiently.
A B C D
In summary, circular queues have several advantages over linear queues, including efficient
A 0 1 1 0
use of memory, faster insertion and deletion, and their ability to be used to implement
circular buffers.
B 1 0 0 1
2(i)I think you might have meant "Insertion Sort" instead of "inplace Sorting". So, I'll provide
C 1 0 0 1
an explanation of both "Insertion Sort" and "Stable Sort" below.
D 0 1 1 0
Insertion Sort:Insertion Sort is a simple sorting algorithm that works by sorting an array one
element at a time. In each iteration, the algorithm takes an element from the unsorted part In the above representation, the cell at row A and column B contains 1, indicating that there
of the array and inserts it into the correct position in the sorted part of the array. The is an edge from vertex A to vertex B, and so on. If the graph were weighted, the cell would
insertion process is repeated until all the elements are sorted. contain the weight of the edge instead of 1 or 0.
Here's an example of how Insertion Sort works on an array of integers [7, 5, 2, 4, 3, 9]: 2(l)I assume you meant "construct an AVL tree" instead of "evl tree". Here are the steps to
construct an AVL tree by inserting the given values one by one:
In the first iteration, the first element 7 is already sorted, so we move on to the second
element 5. We compare 5 with 7 and swap them, so the array becomes [5, 7, 2, 4, 3, 9]. Insert 23 as the root of the tree.
In the second iteration, we consider the third element 2. We compare it with 7, then with 5, 23
and finally with 2. We swap 2 with 5 and then with 7, so the array becomes [2, 5, 7, 4, 3, 9].
Insert 24 to the right of 23.
In the third iteration, we consider the fourth element 4. We compare it with 7, then with 5,
and then with 2. Since 4 is greater than 2 and less than 5, we insert it between 2 and 5, so 23
the array becomes [2, 4, 5, 7, 3, 9].
\
In the fourth iteration, we consider the fifth element 3. We compare it with 7, then with 5,
then with 4, and finally with 2. We insert it between 2 and 4, so the array becomes [2, 3, 4, 24
5, 7, 9].
Insert 12 to the left of 23.
In the fifth iteration, we consider the last element 9. We compare it with 7 and insert it after
7, so the array becomes [2, 3, 4, 5, 7, 9]. 23
Stable Sort:A stable sort is a sorting algorithm that preserves the relative order of equal / \
elements in the sorted array. In other words, if there are two or more elements with the
same value in the original array, a stable sort will preserve their order in the sorted array. 12 24
Here's an example of how a stable sort works on an array of strings ["cat", "dog", "ant", Insert 11 to the left of 12. This causes an imbalance in the tree.
"bee", "cat", "fox"]:
23
We can use Insertion Sort as a stable sort in this case. In the first iteration, we sort the array
one element at a time. When we consider the second "cat" element, we compare it with the / \
first "cat" element and insert it after it, so the array becomes ["cat", "cat", "dog", "ant",
"bee", "fox"]. 12 24
In the second iteration, we consider the third element "dog". We insert it after "cat", so the /
array becomes ["cat", "cat", "dog", "ant", "bee", "fox"].
11
In the third iteration, we consider the fourth element "ant". We insert it before "bee", so the
array becomes ["cat", "cat", "dog", "ant", "bee", "fox"]. Since the balance factor of the node 23 is now -2 (i.e., the height of its left subtree is 2
greater than the height of its right subtree), we need to rebalance the tree.Perform a right
In the fourth iteration, we consider the fifth element "bee". We insert it after "ant", so the rotation at node 23.
array becomes ["cat", "cat", "dog", "ant", "bee", "fox"].
12
2(g)There are two commonly used methods to represent a graph: Adjacency List and
Adjacency Matrix. / \
Adjacency List:In an adjacency list representation, each vertex of the graph is represented by 11 23
a list of its adjacent vertices. For example, consider the following graph:
\
A --- B
24
||
Insert 6 to the left of 12. This causes an imbalance in the tree. 6 24
12 / \
/ \ 12 23
11 23 /\
/ 25 45
6 The resulting tree is the AVL tree with the given values.
Since the balance factor of the node 12 is now -2, we need to rebalance the tree.Perform a what are the different a symptoms relation used for algorithm analysis
right rotation at node 12.
The different asymptotic notations used for algorithm analysis are:
11
Big-O Notation: Big-O notation is used to represent the upper bound of an algorithm's time
/ \ complexity. It defines the worst-case scenario of an algorithm. For example, an algorithm
that has a time complexity of O(n) means that its worst-case running time grows at most
6 12 linearly with the size of the input.
\ Omega Notation: Omega notation is used to represent the lower bound of an algorithm's
time complexity. It defines the best-case scenario of an algorithm. For example, an algorithm
23 that has a time complexity of Ω(n) means that its best-case running time grows at least
linearly with the size of the input.
\
Theta Notation: Theta notation is used to represent the tight bound of an algorithm's time
24 complexity. It defines the average-case scenario of an algorithm. For example, an algorithm
that has a time complexity of Θ(n) means that its running time grows linearly with the size of
Insert 45 to the right of 24. This causes an imbalance in the tree. the input in the worst-case, best-case, and average-case scenarios.
11 Little-O Notation: Little-O notation is used to represent the upper bound of an algorithm's
time complexity, but it excludes the constant factors. It defines the growth rate of an
/ \ algorithm that is smaller than the upper bound. For example, an algorithm that has a time
complexity of o(n) means that its worst-case running time grows strictly less than linearly
6 12
with the size of the input.
\
Little-Omega Notation: Little-Omega notation is used to represent the lower bound of an
algorithm's time complexity, but it excludes the constant factors. It defines the growth rate
23
of an algorithm that is larger than the lower bound. For example, an algorithm that has a
time complexity of ω(n) means that its best-case running time grows strictly more than
\
linearly with the size of the input.
24
2(h)Sure, here's how the Quick Sort algorithm can be applied to sort the given
\ leaves (18,23,17,9,4,26,22,40):
1. Choose a pivot element from the array. Let's choose the first element as
45 the pivot.
2. Partition the array into two sub-arrays - one containing elements smaller
Since the balance factor of the node 12 is now 2, we need to rebalance the tree.Perform a
than the pivot, and the other containing elements greater than the
left rotation at node 12.
pivot. This can be done using two pointers, one starting from the
beginning of the array, and the other starting from the end. Move the
11
pointers towards each other until they meet or cross. Swap the elements
/ \ at the two pointer positions if they are in the wrong sub-array. Continue
doing this until the pointers meet or cross.
6 23
After the first partition, the array is partitioned as follows:[9, 4, 17, 18, 23, 26, 22, 40]
/\
12 24
3. Recursively apply steps 1 and 2 to the two sub-arrays created in the
previous step.
\
45
For the sub-array containing elements smaller than the pivot, we choose 9 as the
pivot and partition the array as follows:[4, 9, 17, 18, 23, 26, 22, 40] ↑ ↑ i j For the sub-
Insert 25 to the right of 23. This causes an imbalance in the tree.
array containing elements greater than the pivot, we choose 23 as the pivot [4, 9, 17,
11 18, 22, 26, 23, 40] ↑ ↑ i j
/ \
4. Repeat step 3 until the sub-arrays have only one element or are empty.
6 23 5. The sorted array is obtained by concatenating the sorted sub-arrays
from step 4.
/\
12 24 The sorted array using Quick Sort algorithm for the given leaves
(18,23,17,9,4,26,22,40) is: [4, 9, 17, 18, 22, 23, 26, 40].
\
45
25
Since the balance factor of the node 23 is now 2, we need to rebalance the tree.Perform a
left rotation at node 23.
11
/ \
