ASSIGNMENT-1

ANSWER 1:
A data structure is a specific way of organizing and storing data in a computer so it
can be accessed and modified efficiently. It provides a means to manage and process data, facilitating
operations like data retrieval, insertion, deletion, and manipulation.
Linear Data Structures: These store elements sequentially and are easy to traverse since elements are
arranged in a specific order. They are generally simple to implement but may have limitations in terms of
efficiency when scaling.

1. Array: A collection of elements, identified by index or key, stored sequentially in memory. All elements
are of the same data type. Arrays allow constant-time access to elements but have fixed size and may require
significant memory if large.
2. Linked List: A collection of nodes where each node contains a data part and a reference (or link) to the
next node in the sequence. Linked lists allow for efficient insertions and deletions but have a slower access
time than arrays due to the need to traverse nodes.
Singly Linked List: Each node points to the next node.
Doubly Linked List: Each node points to both the next and the previous node.
Circular Linked List: The last node points back to the first, forming a loop.
 Stack: A collection of elements that follows the Last In, First Out (LIFO) principle. Operations are
performed at one end, called the "top" of the stack. Common operations include push (insert) and pop
(remove). Stacks are used for functions like backtracking, reversing, and recursion management.
 Queue: A collection of elements that follows the First In, First Out (FIFO) principle. Elements are added at
the back (enqueue) and removed from the front (dequeue). Queues are used in scheduling processes and
managing tasks in order.
1. Simple Queue: Basic FIFO structure.
2. Circular Queue: The end of the queue wraps around to connect with the start, optimizing
space.
3. Priority Queue: Elements are dequeued based on priority rather than order of arrival.
4. Dequeue: A double-ended queue where insertions and deletions can be made from both ends.

A data structure is a specific way of organizing and storing data in a computer so it can be accessed and
modified efficiently. It provides a means to manage and process data, facilitating operations like data
retrieval, insertion, deletion, and manipulation.

Data structures can be broadly classified into two main categories:

1. Linear Data Structures: These store elements sequentially and are easy to traverse since elements are
arranged in a specific order. They are generally simple to implement but may have limitations in terms
of efficiency when scaling.
2. Non-Linear Data Structures: These store elements in a hierarchical or interconnected manner,
allowing for more complex relationships among data. Non-linear structures are efficient for certain
tasks, such as representing hierarchical data or graphs, but can be more complex to implement.
Linear Data Structures

1. Array: A collection of elements, identified by index or key, stored sequentially in memory. All
elements are of the same data type. Arrays allow constant-time access to elements but have fixed
size and may require significant memory if large.
2. Linked List: A collection of nodes where each node contains a data part and a reference (or link) to
the next node in the sequence. Linked lists allow for efficient insertions and deletions but have a
slower access time than arrays due to the need to traverse nodes.
o Singly Linked List: Each node points to the next node.
o Doubly Linked List: Each node points to both the next and the previous node.
o Circular Linked List: The last node points back to the first, forming a loop.
3. Stack: A collection of elements that follows the Last In, First Out (LIFO) principle. Operations are
performed at one end, called the "top" of the stack. Common operations include push (insert) and pop
(remove). Stacks are used for functions like backtracking, reversing, and recursion management.
4. Queue: A collection of elements that follows the First In, First Out (FIFO) principle. Elements are
added at the back (enqueue) and removed from the front (dequeue). Queues are used in scheduling
processes and managing tasks in order.
o Simple Queue: Basic FIFO structure.
o Circular Queue: The end of the queue wraps around to connect with the start, optimizing
space.
o Priority Queue: Elements are dequeued based on priority rather than order of arrival.
o Deque: A double-ended queue where insertions and deletions can be made from both ends.

Non-Linear Data Structures

1. Tree: A hierarchical structure consisting of nodes. Each node contains a data value and links to child
nodes. The topmost node is the "root," and nodes with no children are "leaves." Trees are efficient for
hierarchical data storage, such as file systems and databases.
o Binary Tree: Each node has at most two children (left and right).
o Binary Search Tree (BST): A binary tree with sorted nodes; left child values are smaller, and
right child values are larger.
o AVL Tree: A self-balancing binary search tree that maintains balance through rotations to
ensure efficient search and update operations.
o B-Tree: A balanced tree structure optimized for systems that read and write large blocks of
data.
2. Graph: A structure consisting of nodes (vertices) connected by edges. Graphs represent complex
relationships among data points and can be directed or undirected.
o Undirected Graph: Edges have no direction (mutual connection).
o Directed Graph (Digraph): Edges have direction (one-way connection).
o Weighted Graph: Edges have weights (values) representing cost, distance, or other
factors.
o Unweighted Graph: Edges have no weight.
3. Heap: A specialized tree-based structure that follows the heap property. It is commonly used to
implement priority queues.
o Max-Heap: The value of each parent node is greater than or equal to the values of its children.
 o Min-Heap: The value of each parent node is less than or equal to the values of its children.

ANSWER 2:

An Abstract Data Type (ADT) is a theoretical model for data structures that defines a set of data
and the operations that can be performed on it without specifying the actual implementation details. An ADT
focuses on what operations can be done (the interface) rather than how they are done (the implementation). This
abstraction allows programmers to use data structures in a more general way, focusing on functionality without
worrying about underlying complexities.

Data structures are typically categorized into two main types:

1. Linear Data Structures

In linear data structures, elements are arranged sequentially, one after the other. They have a single
level, making them simple to traverse and use.
o Examples:
 Array: Stores elements in contiguous memory locations and is accessed using
indexes.
 Linked List: Consists of nodes, each containing data and a reference to the next node.
 Stack: Follows the Last In, First Out (LIFO) principle where elements are added and
removed from the top.
 Queue: Follows the First In, First Out (FIFO) principle, with elements added at
the back and removed from the front.

  CHARACTERISTICS:
o Elements are arranged in a sequential order.
o Each element has a single predecessor and successor, except the first and last.

 Non-Linear Data Structures

In non-linear data structures, elements are not arranged in a sequence but rather in a hierarchical or
interconnected fashion, allowing for more complex relationships.
Examples:
1. Tree: A hierarchical structure with a root element and child nodes, used to represent hierarchical
relationships
2. Graph: Consists of vertices (nodes) and edges, which can be directed or undirected, representing
connections between entities.
 Characteristics:
1. Elements may have multiple relationships, connections, or hierarchies.
2. Efficient for representing complex relationships.
3. Can be more challenging to implement and traverse due to varied structures

ANSWER 3:
Linear data structures support a variety of basic operations that are essential for manipulating and managing data.
Here are the primary operations commonly performed with linear structures like arrays, linked lists, stacks, and
queues:

1. Traversal

 Traversal is the process of accessing each element in the linear structure sequentially.
 This operation is essential for displaying, processing, or analyzing each element.
 For example, in an array or linked list, traversal involves moving from the first to the last element to
process each item.

2. Insertion

 Insertion adds a new element at a specified position within the structure.

 The specifics of insertion vary depending on the structure:
o Array: Adding an element in an array requires shifting existing elements, making insertion at
the start or middle costly (O(n) time complexity).
o Linked List: Inserting at the beginning or end is efficient (O(1) for singly linked lists), as it
only requires updating pointers.
o Stack: Elements are pushed (inserted) only at the top of the stack.
o Queue: Elements are enqueued (inserted) at the back of the queue.

3. Deletion

 Deletion removes an element from a specific position in the structure.

 Similar to insertion, the specifics depend on the data structure:
o Array: Removing an element in an array may require shifting elements to maintain
order, which can be costly.
o Linked List: Deleting the first node or a specific node is straightforward by updating
pointers.
o Stack: Elements are popped (removed) only from the top.
o Queue: Elements are dequeued (removed) from the front.

4. Searching

 Searching involves finding the location of a particular element within the structure.
 Searching methods vary based on the data structure:
o Array and Linked List: A linear search (O(n)) is used to locate an element by checking
each item.
o Stack and Queue: Typically, only the element at the top (stack) or front (queue) is accessible,
so searching isn’t commonly used for these structures.

5. Updating

 Updating changes the value of an element at a specific position in the structure.

 This operation is straightforward if the element's position is known (O(1) for direct- access
structures like arrays).
 In a linked list, traversal may be necessary to reach the node before updating.
6. Accessing

 Accessing retrieves the value of an element at a particular index or position in the structure.
 Array: Direct access is possible with indexing (O(1) time complexity).
 Linked List: Accessing a specific node requires traversal from the start to the desired position,
making it an O(n) operation.

ANSWER 4:

In C, dynamic memory allocation allows for allocating and managing memory at

runtime, providing flexibility to create data structures that can grow or shrink as needed. The C standard library
provides four main functions for dynamic memory allocation, each defined in the <stdlib.h> header file:

1. MALLOC (Memory Allocation)

o Syntax: void* malloc(size_t size);
o Description: Allocates a specified number of bytes of memory and returns a pointer to the
first byte of the allocated memory. The memory is uninitialized, meaning it may contain
garbage values.
o Parameters: size specifies the number of bytes to allocate.
o Return Value: Returns a void* pointer to the allocated memory. If the allocation fails (e.g., due
to insufficient memory), NULL is returned.

EXAMPLE:

int* ptr = (int*)malloc(10 * sizeof(int)); // Allocates memory for an array of 10

integers.

2. CALLOC(Contiguous Allocation)

 Syntax: void* calloc(size_t num, size_t size);

 Description: Allocates memory for an array of num elements, each of a specified size, and initializes
all bytes to zero.
 Parameters: num is the number of elements, and size is the size in bytes of each element.
 Return Value: Returns a void* pointer to the allocated and zero-initialized memory. Returns NULL
if the allocation fails.

EXAMPLE :

int* ptr = (int*)calloc(10, sizeof(int)); // Allocates and initializes memory for an array of 10 integers to 0.
 3. REALLOC (Reallocation)

 Syntax: void* realloc(void* ptr, size_t new_size);

 Description: Resizes a previously allocated memory block to a new size. It can increase or decrease
the size of the memory block, copying the existing data to the new block. If ptr is NULL, realloc
behaves like malloc.
 Parameters:
o ptr is a pointer to the previously allocated memory block (using malloc, calloc, or
realloc).
o new_size specifies the new size for the memory block in bytes.
 Return Value: Returns a void* pointer to the reallocated memory. If reallocation fails, it returns
NULL, and the original memory block remains unchanged.

EXAMPLE:

int* ptr = (int*)malloc(10 * sizeof(int)); // Initial allocation

ptr = (int*)realloc(ptr, 20 * sizeof(int)); // Resize to hold 20 integers

4. FREE (Deallocation)

 Syntax: void free(void* ptr);

 Description: Frees the memory block previously allocated by malloc, calloc, or realloc. It releases
the memory back to the system, preventing memory leaks. After calling free, the pointer becomes
invalid and should not be used until reallocated.
 Parameters: ptr is the pointer to the memory block to free.

Example Usage of Dynamic Memory Allocation Function

#include <stdio.h>
#include <stdlib.h> int
main() {
// Allocate memory for an array of 5 integers using malloc int* arr
= (int*)malloc(5 * sizeof(int));
for(int i = 0; i < 5; i++) {
arr[i] = i + 1; printf("%d ",
arr[i]);
}
 // Resize the array to hold 10 integers using realloc arr =
(int*)realloc(arr, 10 * sizeof(int));

// Initialize and print new elements

for(int i = 5; i < 10; i++) {
arr[i] = i + 1; printf("%d ",
arr[i]);
}

// Free the allocated memory

free(arr);
return 0;

ANSWER 5:

Linear Data Structures organize data in a sequential, ordered manner, where elements are arranged one after
another. This sequential setup means each element typically has a unique predecessor and successor, except for
the first and last elements in the structure. Common examples of linear data structures include arrays, linked lists,
stacks, and queues.

These structures are generally straightforward to implement and use, making them suitable for simpler tasks
like managing lists of items or processing tasks in a sequence. For instance, stacks and queues manage data in
an orderly way, following Last In, First Out (LIFO) and First In, First Out (FIFO) principles, respectively.
Linear data structures often allow direct access to elements, such as accessing elements by index in arrays.
However, they may require shifting elements for insertions and deletions, which can impact performance,
especially for large datasets.

In Non-Linear Data Structures, data is organized in a hierarchical or interconnected manner, allowing

elements to have multiple relationships. Unlike linear structures, they don’t follow a strict sequence but are
instead organized in ways that reflect more complex associations between elements. Trees and graphs are
classic examples of non-linear structures. In a tree, for example, each node can have multiple child nodes,
forming a parent-child hierarchy. Graphs allow for even more intricate relationships, with nodes (vertices)
connected by edges that can represent various kinds of connections.

Non-linear structures are ideal for modeling complex data like hierarchical relationships (such as file
directories) or interconnected data (like social networks). They tend to be more complex to implement due to
the varied relationships among elements, and traversal methods can be intricate, requiring specific techniques
(e.g., preorder, inorder, and postorder for trees).
ANSWER 6:

The time complexity and space complexity of an algorithm are metrics used to evaluate its efficiency and
resource usage. They help in understanding the algorithm's performance, especially as the input size
grows.

Time Complexity

 Definition: Time complexity is a measure of the amount of time an algorithm takes to run as a
function of the input size, typically denoted as nnn.
 Purpose: It gives an idea of how the execution time increases with the input size, helping to
predict the algorithm’s behavior on large datasets.
 Notations: Big O notation (e.g., O(n)O(n)O(n), O(n2)O(n^2)O(n2), O(log⁡n)O(\log n)O(logn)) is
used to express the upper bounds of time complexity, representing the worst-case scenario of time
growth.
 Example: A linear search algorithm has a time complexity of O(n)O(n)O(n) because it may need to
check each element in a list of nnn elements in the worst case.

Space Complexity

 Definition: Space complexity is a measure of the amount of memory an algorithm requires to

run, also as a function of the input size.
 Purpose: It helps determine the algorithm’s memory consumption, which is crucial in environments
with limited memory resources.
 Components: Space complexity includes both auxiliary space (extra space needed by the
algorithm) and input space (space taken by input data).
 Notations: Space complexity is also expressed in Big O notation, indicating the maximum
memory usage growth as the input size increases.
 Example: A recursive algorithm that needs to store intermediate results or stack frames may have a
space complexity of O(n)O(n)O(n) if it needs memory proportional to the depth of the recursion.

ANSWER 7:

Best case, average case, and worst case time analyses are used to describe an algorithm's performance
under different conditions of input data. Each provides insights into how efficiently an algorithm will run
depending on the scenario. Let’s go through each case with examples:

1. Best Case

 Definition: The best case time complexity of an algorithm is the minimum time it takes to complete,
given the most favorable input.
  Purpose: This scenario is typically used to understand the fastest performance that an algorithm can
achieve.
 Example: Consider linear search in an unsorted array.
o Best Case: The element to be found is the very first element in the array.
o Time Complexity: O(1)O(1)O(1), as the algorithm only needs one comparison to find the
target element.

2. Average Case

 Definition: The average case time complexity represents the expected time it takes for an algorithm to
complete, assuming random input distribution.
 Purpose: This case gives a realistic measure of performance across a range of inputs, assuming no
particular bias.
 Example: Again, consider linear search in an unsorted array.
o Average Case: The element is expected to be somewhere in the middle of the array on
average.
o Time Complexity: O(n/2)O(n/2)O(n/2), which simplifies to O(n)O(n)O(n), as it might
take approximately half of the array's length to find the element.

3. Worst Case

 Definition: The worst case time complexity is the maximum time an algorithm takes to complete,
given the most challenging input.
 Purpose: This case helps to identify performance limits and ensure the algorithm won’t exceed certain
time constraints, even in the most difficult scenarios.
 Example: Consider linear search again.
o Worst Case: The element is located at the last position or is not in the array at all.
o Time Complexity: O(n)O(n)O(n), as the algorithm must examine each element in the array to
confirm the element's absence or to find it at the end.

Case Analysis in Sorting Algorithm Example (Bubble Sort)

 Best Case: If the array is already sorted, Bubble Sort will only make one pass without needing to
swap elements.
o Time Complexity: O(n)O(n)O(n).
 Average Case: When the elements are in random order, Bubble Sort has to go through multiple
passes and perform several swaps.
o Time Complexity: O(n2)O(n^2)O(n2).
 Worst Case: If the array is in reverse order, Bubble Sort must swap every pair on each pass, making
it go through the maximum number of comparisons and swaps.
o Time Complexity: O(n2)O(n^2)O(n2).
ANSWER 8:

Performance Analysis of an Algorithm

Performance analysis is the process of evaluating an algorithm to determine its efficiency and effectiveness in
solving a specific problem. This analysis involves studying various factors such as time complexity, space
complexity, and resource utilization under different conditions of input data. The goal is to understand how
well the algorithm performs, especially as the size of the input data grows.

Key Aspects of Performance Analysis:

1. Time Complexity: This measures the amount of time an algorithm takes to complete as a function of
the input size. Different cases (best, average, worst) are often analyzed to provide a comprehensive view
of expected performance.
2. Space Complexity: This assesses the amount of memory space required by the algorithm in relation to
the input size. Like time complexity, it can also be evaluated under different conditions.
3. Scalability: Analyzing how the algorithm's performance changes with increasing input sizes is
crucial for determining its applicability in real-world scenarios.
4. Resource Usage: Besides time and space, performance analysis can include evaluating the
algorithm's use of other resources, such as CPU cycles and network bandwidth, depending on the
context.

Performance Measurement of an Algorithm

Performance measurement involves quantifying the performance characteristics of an algorithm through

empirical means, typically by implementing the algorithm and running it on sample inputs. This provides
practical insights into how the algorithm behaves in real-world scenarios.

Key Aspects of Performance Measurement:

1. Benchmarking: Implementing the algorithm and comparing its performance against established
benchmarks or other algorithms to assess its relative efficiency.
2. Execution Time: Measuring the actual time taken by the algorithm to complete tasks, often using
built-in timing functions or profiling tools.
3. Memory Usage: Monitoring how much memory the algorithm consumes during execution,
which can be measured through profiling tools or manual tracking.
4. Test Cases: Running the algorithm with various input sizes and types to gather data on its
performance across different scenarios. This helps in identifying edge cases and understanding
average behavior.
5. Statistical Analysis: Collecting data from multiple runs to perform statistical analysis, which helps
to account for variations in performance due to external factors like hardware differences and system
load.
ANSWER 9:

#include <iostream>
#include <vector>
#include <chrono> using
namespace std;
using namespace std::chrono;

double sumVector(const vector<double>& V) {

double sum = 0.0;
for (size_t i = 0; i < V.size(); ++i) {
sum += V[i];
}

return sum;

int main() {

// Example vector

vector<double> V = {1.0, 2.5, 3.5, 4.0, 5.0, 6.5};

// Start measuring time

auto start = high_resolution_clock::now();

// Calculate the sum

double result = sumVector(V);

// Stop measuring time

auto stop = high_resolution_clock::now();

// Calculate the duration

auto duration = duration_cast<microseconds>(stop - start);

 // Output the result and execution time

cout << "Sum of vector values: " << result << endl;

cout << "Execution time: " << duration.count() << " microseconds" << endl;
return 0;
}

Assignment 2: Linear Data Structure

Ques 1: Define Sparse Matrix and Explain Representation Using Linked List and Array

Answer:

Sparse Matrix:

A sparse matrix is a matrix in which most of the elements are zero (or a predefined "empty" value). This is
in contrast to a dense matrix, where most of the elements are non-zero. Sparse matrices arise frequently in
scientific computing, image processing, and other areas where the data is large but sparse.

Representation of Sparse Matrix:

Using Array:

In an array-based representation of a sparse matrix, only the non-zero elements are stored along with their
row and column indices. This reduces memory usage significantly. There are a few common ways to store
sparse matrices:

 Triplet Format (COO - Coordinate List): The sparse matrix is stored as a list of non-zero values,
along with their row and column indices.

For example, consider the following matrix:

A = [0, 0, 0, 0]
[5, 0, 0, 0]
[0, 8, 0, 0]
[0, 0, 0, 4]

This can be represented in triplet form as:

Row Column Value

----------------------
2 1 5
3 2 8
4 4 4

In this format, the matrix is represented as an array of tuples or a 3-column array (row, column, value).

 Compressed Sparse Row (CSR) and Compressed Sparse Column (CSC) are other formats that
store row/column indices separately, further reducing memory.

Using Linked List:

In the linked list representation of a sparse matrix, each non-zero element is stored in a node that contains:
  The row index.
 The column index.
 The value of the non-zero element.
 A pointer to the next element in the list.

A linked list can be implemented in a row-wise or column-wise manner. It helps in saving memory,
especially when the number of non-zero elements is significantly less than the total number of elements.

Ques 2: Find the Address of Element A1(4, 12) in a Two-Dimensional Array Stored in Row-Major
Order

Answer:

Given:

 Array A1(1:8,7:14)A1(1:8, 7:14)A1(1:8,7:14) stored in row-major order.

 Base address = 100
 Size of each element = 4 bytes

We need to find the address of element A1(4,12)A1(4, 12)A1(4,12).

Formula for Address Calculation in Row-Major Order:

For a two-dimensional array A[i][j]A[i][j]A[i][j] with base address BBB, the address of element A[i,j]A[i,
j]A[i,j] is given by:

Address(i,j)=B+Size of element×((i−1)×number of columns+(j−1))

Here:

 Number of rows = 8 - 1 + 1 = 8
 Number of columns = 14 - 7 + 1 = 8

Now, for element A1(4,12)A1(4, 12)A1(4,12):

 i=4,j=12i = 4, j = 12i=4,j=12

Address(4,12)=100+4×((4−1)×8+(12−7))=100+4×(24+5)=100+4×29=100+116=216

Thus, the address of element A1(4,12)A1(4, 12)A1(4,12) is 216.

Ques 3: Find the Address of Element Z1(4, 12) in a Two-Dimensional Array Stored in Column-Major
Order

Answer:

Given:

 Array Z1(2:9,9:18)Z1(2:9, 9:18)Z1(2:9,9:18) stored in column-major order.

 Base address = 100
 Size of each element = 4 bytes
We need to find the address of element Z1(4,12)Z1(4, 12)Z1(4,12).

Formula for Address Calculation in Column-Major Order:

For a two-dimensional array Z[i][j]Z[i][j]Z[i][j] with base address BBB, the address of element Z[i,j]Z[i,
j]Z[i,j] is given by:

Address(i,j)=B+Size of element×((j−1)×number of rows+(i−1))

Here:

 Number of rows = 9 - 2 + 1 = 8
 Number of columns = 18 - 9 + 1 = 10

Now, for element Z1(4,12)Z1(4, 12)Z1(4,12):

 i=4,j=12i = 4, j = 12i=4,j=12

Address(4,12)=100+4×((12−1)×8+(4−1))=100+4×(11×8+3)=100+4×(88+3)=100+4×91=100+364=464

Thus, the address of element Z1(4,12)Z1(4, 12)Z1(4,12) is 464.

Stack
Ques 1: What is a Stack? Explain Basic Primitive Operations of Stack with Examples

Answer:

A stack is a linear data structure that follows the Last In, First Out (LIFO) principle. This means that the
last element inserted into the stack is the first to be removed.

Basic Operations of Stack:

 Push: Adds an element to the top of the stack.

 Pop: Removes the element from the top of the stack.
 Peek or Top: Returns the element at the top of the stack without removing it.
 isEmpty: Checks whether the stack is empty.
 isFull: Checks whether the stack is full (applicable in array-based stack).

Example:

 Push(10) → Stack: [10]

 Push(20) → Stack: [10, 20]
 Pop() → Removes 20 → Stack: [10]
 Peek() → Returns 10 (top element)
 isEmpty() → Returns false (stack is not empty)

Ques 2: Write a C Program to Implement a Stack with Overflow and Underflow Checks Using Array

Answer:
#include <stdio.h>
#define MAX 5

int stack[MAX];
int top = -1;

int isFull() {
return top == MAX - 1;
}

int isEmpty() {
return top == -1;
}

void push(int value) {

if (isFull()) {
printf("Stack Overflow\n");
} else {
stack[++top] = value;
printf("%d pushed to stack\n", value);
}
}

int pop() {
if (isEmpty()) {
printf("Stack Underflow\n");
return -1;
} else {
return stack[top--];
}
}

int peek() {
if (isEmpty()) {
printf("Stack is empty\n");
return -1;
} else {
return stack[top];
}
}

int main() {
push(10);
push(20);
push(30);
printf("Top element is %d\n", peek());
printf("%d popped from stack\n", pop());
printf("Top element is %d\n", peek());
return 0;
}

Ques 3: Write an Algorithm to Reverse a String Using Stack

Answer:
Algorithm:

1. Initialize an empty stack.

2. Push each character of the string onto the stack.
3. Pop characters from the stack and append them to the result string.
4. The result string will be the reverse of the original string.

Algorithm Steps:

1. Initialize an empty stack.

2. For each character in the string, push it onto the stack.
3. Pop all characters from the stack and append to the result string.
4. The resulting string is the reverse of the original.

Ques 4: What is the Advantage of Polish Expression Over Infix Notation? Write an Algorithm to
Convert Infix to Reverse Polish Notation (Postfix)

Answer:

Advantage of Polish Notation:

 No Parentheses Needed: Polish notation (both prefix and postfix) eliminates the need for
parentheses to enforce operator precedence.
 Faster Evaluation: It allows for faster computation because the order of operations is explicitly
defined.

Algorithm to Convert Infix to Postfix:

1. Initialize an empty stack for operators and an empty list for the result.
2. For each character in the infix expression:
o If it's an operand, add it to the result list.
o If it's an operator, pop operators from the stack to the result list until the operator at the top of
the stack has lower precedence, then push the current operator onto the stack.
o If it's a parenthesis, handle it by pushing it onto the stack or popping operators until a left
parenthesis is encountered.
3. Pop any remaining operators from the stack to the result list.

Ques 5: Convert the Given Infix Expression to Postfix Expression

Answer:

To convert an infix expression to postfix, we use a stack-based algorithm that respects operator precedence
and parentheses.

Operator Precedence:

 Highest precedence: ^ (exponentiation)

 Next precedence: *, / (multiplication and division)
 Lowest precedence: +, - (addition and subtraction)
 Associativity:
o +, -, *, / are left-associative.
o ^ is right-associative.
Postfix Conversion Algorithm:

1. Initialize an empty stack for operators and an empty list for the result.
2. For each token (operand or operator) in the infix expression:
o If the token is an operand (variable or number), append it to the result list.
o If the token is an operator, pop operators from the stack to the result list while they have
greater or equal precedence than the current operator. Then, push the current operator onto
the stack.
o If the token is a left parenthesis (, push it onto the stack.
o If the token is a right parenthesis ), pop operators from the stack to the result list until a left
parenthesis ( is encountered.
3. After reading the entire expression, pop any remaining operators from the stack to the result list.

1. Infix Expression: A + ( (B – C) * (D – E) + F) / G ) $ (H – J)

Postfix Expression: A B C – D E – * F + G / H J – $ +

Steps:

1. Encounter A → Append to result: A

2. Encounter + → Push + to stack
3. Encounter ( → Push to stack
4. Encounter B → Append to result: A B
5. Encounter – → Push – to stack
6. Encounter C → Append to result: A B C
7. Pop – from stack → Append to result: A B C –
8. Encounter * → Push * to stack
9. Encounter ( → Push to stack
10. Encounter D → Append to result: A B C – D
11. Encounter – → Push – to stack
12. Encounter E → Append to result: A B C – D E
13. Pop – from stack → Append to result: A B C – D E –
14. Pop * from stack → Append to result: A B C – D E – *
15. Encounter + → Push + to stack
16. Encounter F → Append to result: A B C – D E – * F
17. Pop + from stack → Append to result: A B C – D E – * F +
18. Encounter / → Push / to stack
19. Encounter G → Append to result: A B C – D E – * F + G
20. Pop / from stack → Append to result: A B C – D E – * F + G /
21. Encounter $ → Push $ to stack
22. Encounter ( → Push to stack
23. Encounter H → Append to result: A B C – D E – * F + G / H
24. Encounter – → Push – to stack
25. Encounter J → Append to result: A B C – D E – * F + G / H J
26. Pop – from stack → Append to result: A B C – D E – * F + G / H J –
27. Pop ( from stack → Discard
28. Pop $ from stack → Append to result: A B C – D E – * F + G / H J – $

2. Infix Expression: (A + B) * (C – D) $ E * F

Postfix Expression: A B + C D – * E F * $

Steps:
 1. Encounter ( → Push to stack
2. Encounter A → Append to result: A
3. Encounter + → Push + to stack
4. Encounter B → Append to result: A B
5. Pop + from stack → Append to result: A B +
6. Pop ( from stack → Discard
7. Encounter * → Push * to stack
8. Encounter ( → Push to stack
9. Encounter C → Append to result: A B + C
10. Encounter – → Push – to stack
11. Encounter D → Append to result: A B + C D
12. Pop – from stack → Append to result: A B + C D –
13. Pop * from stack → Append to result: A B + C D – *
14. Encounter $ → Push $ to stack
15. Encounter E → Append to result: A B + C D – * E
16. Encounter * → Push * to stack
17. Encounter F → Append to result: A B + C D – * E F
18. Pop * from stack → Append to result: A B + C D – * E F *
19. Pop $ from stack → Append to result: A B + C D – * E F * $

3. Infix Expression: (A + B) * (C ^ (D – E) + F) – G

Postfix Expression: A B + C D E – ^ F + * G –

Steps:

1. Encounter ( → Push to stack

2. Encounter A → Append to result: A
3. Encounter + → Push + to stack
4. Encounter B → Append to result: A B
5. Pop + from stack → Append to result: A B +
6. Pop ( from stack → Discard
7. Encounter * → Push * to stack
8. Encounter ( → Push to stack
9. Encounter C → Append to result: A B + C
10. Encounter ^ → Push ^ to stack
11. Encounter ( → Push to stack
12. Encounter D → Append to result: A B + C D
13. Encounter – → Push – to stack
14. Encounter E → Append to result: A B + C D E
15. Pop – from stack → Append to result: A B + C D E –
16. Pop ^ from stack → Append to result: A B + C D E – ^
17. Encounter + → Push + to stack
18. Encounter F → Append to result: A B + C D E – ^ F
19. Pop + from stack → Append to result: A B + C D E – ^ F +
20. Pop * from stack → Append to result: A B + C D E – ^ F + *
21. Encounter – → Push – to stack
22. Encounter G → Append to result: A B + C D E – ^ F + * G
23. Pop – from stack → Append to result: A B + C D E – ^ F + * G –

4. Infix Expression: A + B * C
Postfix Expression: A B C * +

Steps:

1. Encounter A → Append to result: A

2. Encounter + → Push + to stack
3. Encounter B → Append to result: A B
4. Encounter * → Push * to stack (higher precedence than +)
5. Encounter C → Append to result: A B C
6. Pop * from stack → Append to result: A B C *
7. Pop + from stack → Append to result: A B C * +

5. Infix Expression: A + B * C ^ D – E

Postfix Expression: A B C D ^ * + E –

Steps:

1. Encounter A → Append to result: A

2. Encounter + → Push + to stack
3. Encounter B → Append to result: A B
4. Encounter * → Push * to stack
5. Encounter C → Append to result: A B C
6. Encounter ^ → Push ^ to stack
7. Encounter D → Append to result: A B C D
8. Pop ^ from stack → Append to result: A B C D ^
9. Pop * from stack → Append to result: A B C D ^ *
10. Encounter – → Push – to stack
11. Encounter E → Append to result: A B C D ^ * E
12. Pop – from stack → Append to result: A B C D ^ * E –
13. Pop + from stack → Append to result: A B C D ^ * E – +

6. Infix Expression: A + [(B + C) + (D + E) * F] / G

Postfix Expression: A B C + + D E F * + G / +

Steps:

1. Encounter A → Append to result: A

2. Encounter + → Push + to stack
3. Encounter [ → Push [ to stack
4. Encounter ( → Push ( to stack
5. Encounter B → Append to result: A B
6. Encounter + → Push + to stack
7. Encounter C → Append to result: A B C
8. Pop + from stack → Append to result: A B C +
9. Pop ( from stack → Discard
10. Encounter + → Push + to stack
11. Encounter ( → Push ( to stack
12. Encounter D → Append to result: A B C + D
13. Encounter + → Push + to stack
14. Encounter E → Append to result: A B C + D E
15. Pop + from stack → Append to result: A B C + D E +
 16. Encounter * → Push * to stack
17. Encounter F → Append to result: A B C + D E + F
18. Pop * from stack → Append to result: A B C + D E + F *
19. Pop + from stack → Append to result: A B C + D E + F * +
20. Pop [ from stack → Discard
21. Encounter / → Push / to stack
22. Encounter G → Append to result: A B C + D E + F * + G
23. Pop / from stack → Append to result: A B C + D E + F * + G /
24. Pop + from stack → Append to result: A B C + D E + F * + G / +

7. Infix Expression: (A + B) * C / D + E ^ F / G

Postfix Expression: A B + C * D / E F ^ G / +

Steps:

1. Encounter ( → Push ( to stack

2. Encounter A → Append to result: A
3. Encounter + → Push + to stack
4. Encounter B → Append to result: A B
5. Pop + from stack → Append to result: A B +
6. Pop ( from stack → Discard
7. Encounter * → Push * to stack
8. Encounter C → Append to result: A B + C
9. Pop * from stack → Append to result: A B + C *
10. Encounter / → Push / to stack
11. Encounter D → Append to result: A B + C * D
12. Pop / from stack → Append to result: A B + C * D /
13. Encounter + → Push + to stack
14. Encounter E → Append to result: A B + C * D / E
15. Encounter ^ → Push ^ to stack
16. Encounter F → Append to result: A B + C * D / E F
17. Pop ^ from stack → Append to result: A B + C * D / E F ^
18. Encounter / → Push / to stack
19. Encounter G → Append to result: A B + C * D / E F ^ G
20. Pop / from stack → Append to result: A B + C * D / E F ^ G /
21. Pop + from stack → Append to result: A B + C * D / E F ^ G / +

8. Infix Expression: (A + B) * C / D

Postfix Expression: A B + C * D /

Steps:

1. Encounter ( → Push ( to stack

2. Encounter A → Append to result: A
3. Encounter + → Push + to stack
4. Encounter B → Append to result: A B
5. Pop + from stack → Append to result: A B +
6. Pop ( from stack → Discard
7. Encounter * → Push * to stack
 8. Encounter C → Append to result: A B + C
9. Pop * from stack → Append to result: A B + C *
10. Encounter / → Push / to stack
11. Encounter D → Append to result: A B + C * D
12. Pop / from stack → Append to result: A B + C * D /

9. Infix Expression: ((A + B – C / D) / E)

Postfix Expression: A B + C D / – E /

Steps:

1. Encounter ( → Push ( to stack

2. Encounter ( → Push ( to stack
3. Encounter A → Append to result: A
4. Encounter + → Push + to stack
5. Encounter B → Append to result: A B
6. Pop + from stack → Append to result: A B +
7. Encounter – → Push – to stack
8. Encounter C → Append to result: A B + C
9. Encounter / → Push / to stack
10. Encounter D → Append to result: A B + C D
11. Pop / from stack → Append to result: A B + C D /
12. Pop – from stack → Append to result: A B + C D / –
13. Pop ( from stack → Discard
14. Encounter / → Push / to stack
15. Encounter E → Append to result: A B + C D / – E
16. Pop / from stack → Append to result: A B + C D / – E /

10. Infix Expression: A / (B – C / D ^ E) + F

Postfix Expression: A B C D E ^ / – / F +

Steps:

1. Encounter A → Append to result: A

2. Encounter / → Push / to stack
3. Encounter ( → Push ( to stack
4. Encounter B → Append to result: A B
5. Encounter – → Push – to stack
6. Encounter C → Append to result: A B C
7. Encounter / → Push / to stack
8. Encounter D → Append to result: A B C D
9. Encounter ^ → Push ^ to stack
10. Encounter E → Append to result: A B C D E
11. Pop ^ from stack → Append to result: A B C D E ^
12. Pop / from stack → Append to result: A B C D E ^ /
13. Pop – from stack → Append to result: A B C D E ^ / –
14. Pop ( from stack → Discard
15. Pop / from stack → Append to result: A B C D E ^ / – /
16. Encounter + → Push + to stack
 17. Encounter F → Append to result: A B C D E ^ / – / F
18. Pop + from stack → Append to result: A B C D E ^ / – / F +

11. Infix Expression: A – B / (C * D ^ E)

Postfix Expression: A B C D E ^ * / –

Steps:

1. Encounter A → Append to result: A

2. Encounter – → Push – to stack
3. Encounter B → Append to result: A B
4. Encounter / → Push / to stack
5. Encounter ( → Push ( to stack
6. Encounter C → Append to result: A B C
7. Encounter * → Push * to stack
8. Encounter D → Append to result: A B C D
9. Encounter ^ → Push ^ to stack
10. Encounter E → Append to result: A B C D E
11. Pop ^ from stack → Append to result: A B C D E ^
12. Pop * from stack → Append to result: A B C D E ^ *
13. Pop / from stack → Append to result: A B C D E ^ * /
14. Pop – from stack → Append to result: A B C D E ^ * / –

Let's evaluate the two postfix expressions, step by step, assuming that:

 A=1
 B=2
 C=3

1. Postfix Expression: A B + C – B A + C - +

 Push A (1): [1]

 Push B (2): [1, 2]
 Encounter +: Pop 1 and 2 → 1 + 2 = 3; Stack: [3]
 Push C (3): [3, 3]
 Encounter –: Pop 3 and 3 → 3 - 3 = 0; Stack: [0]
 Push B (2): [0, 2]
 Push A (1): [0, 2, 1]
 Encounter +: Pop 1 and 2 → 1 + 2 = 3; Stack: [0, 3]
 Push C (3): [0, 3, 3]
 Encounter –: Pop 3 and 3 → 3 - 3 = 0; Stack: [0, 0]
 Encounter +: Pop 0 and 0 → 0 + 0 = 0; Stack: [0]

Final Result: 0

2. Postfix Expression: A B C + * C B A - + *
  Push A (1): [1]
 Push B (2): [1, 2]
 Push C (3): [1, 2, 3]
 Encounter +: Pop 3 and 2 → 2 + 3 = 5; Stack: [1, 5]
 Encounter *: Pop 5 and 1 → 1 * 5 = 5; Stack: [5]
 Push C (3): [5, 3]
 Push B (2): [5, 3, 2]
 Push A (1): [5, 3, 2, 1]
 Encounter –: Pop 1 and 2 → 2 - 1 = 1; Stack: [5, 3, 1]
 Encounter +: Pop 1 and 3 → 3 + 1 = 4; Stack: [5, 4]
 Encounter *: Pop 4 and 5 → 5 * 4 = 20; Stack: [20]

Final Result: 20

Summary:

1. A B + C – B A + C - + evaluates to 0.
2. A B C + * C B A - + * evaluates to 20.

Assignment 3: Sorting and Searching Algorithms

Sorting
Ques 1: Name two divide and conquer algorithms for sorting.

Answer:

 Merge Sort: A sorting algorithm that divides the data into two halves, recursively sorts each half,
and then merges the sorted halves back together.
 Quick Sort: A sorting algorithm that selects a pivot element, partitions the data around the pivot, and
recursively sorts the subarrays.

Ques 2: Apply Quick Sort Algorithm to Sort the Following Data

Answer:

Data to Sort: 42, 29, 74, 11, 65, 58

Steps of Quick Sort:

1. Choose Pivot: Choose a pivot element from the array. For simplicity, let's choose the last element as
the pivot.
o Initial Array: [42, 29, 74, 11, 65, 58]
o Pivot: 58
2. Partitioning: Rearrange the elements such that elements smaller than the pivot go to the left, and
elements greater than the pivot go to the right. After partitioning:
o [42, 29, 11, 58, 65, 74]
3. Recursively Apply Quick Sort on the subarrays to the left and right of the pivot:
o Left Subarray: [42, 29, 11]
 Pivot: 11

After partitioning: [11, 29, 42]

o Right Subarray: [65, 74]
 Pivot: 74
 After partitioning: [65, 74]
4. Final Sorted Array: [11, 29, 42, 58, 65, 74]

Ques 3: Write a C Program for Insertion Sort and Discuss Its Efficiency

Answer:

C Code for Insertion Sort:

#include <stdio.h>

void insertionSort(int arr[], int n) {

int key, j;
for (int i = 1; i < n; i++) {
key = arr[i];
j = i - 1;

// Move elements of arr[0..i-1], that are greater than key, to one position ahead
while (j >= 0 && arr[j] > key) {
arr[j + 1] = arr[j];
j = j - 1;
}
arr[j + 1] = key;
}
}

void printArray(int arr[], int size) {

for (int i = 0; i < size; i++) {
printf("%d ", arr[i]);
}
printf("\n");
}

int main() {
int arr[] = {42, 29, 74, 11, 65, 58};
int n = sizeof(arr) / sizeof(arr[0]);

printf("Original Array: ");

printArray(arr, n);

insertionSort(arr, n);

printf("Sorted Array: ");

printArray(arr, n);

return 0;
}

Efficiency of Insertion Sort:

 Best Case: O(n)O(n)O(n) when the array is already sorted.

 Worst Case: O(n2)O(n^2)O(n2) when the array is sorted in reverse order.
  Space Complexity: O(1)O(1)O(1), as it sorts the array in-place.

Ques 4: Write an Algorithm/C Function to Implement Selection Sort

Answer:

Algorithm for Selection Sort:

1. Loop through the entire array.

2. Find the minimum element in the unsorted portion of the array.
3. Swap it with the first element of the unsorted portion.
4. Repeat this process for each element until the array is sorted.

C Code for Selection Sort:

#include <stdio.h>

void selectionSort(int arr[], int n) {

int minIdx, temp;
for (int i = 0; i < n-1; i++) {
minIdx = i;
for (int j = i+1; j < n; j++) {
if (arr[j] < arr[minIdx]) {
minIdx = j;
}
}
temp = arr[i];
arr[i] = arr[minIdx];
arr[minIdx] = temp;
}
}

void printArray(int arr[], int size) {

for (int i = 0; i < size; i++) {
printf("%d ", arr[i]);
}
printf("\n");
}

int main() {
int arr[] = {42, 29, 74, 11, 65, 58};
int n = sizeof(arr) / sizeof(arr[0]);

printf("Original Array: ");

printArray(arr, n);

selectionSort(arr, n);

printf("Sorted Array: ");

printArray(arr, n);

return 0;
}

Ques 5: Write an Algorithm/C Function to Implement Bubble Sort

Answer:
Algorithm for Bubble Sort:

1. Loop through the array.

2. Compare adjacent elements, and swap them if they are in the wrong order.
3. Repeat this process until the array is sorted.

C Code for Bubble Sort:

#include <stdio.h>

void bubbleSort(int arr[], int n) {

int temp;
for (int i = 0; i < n-1; i++) {
for (int j = 0; j < n-i-1; j++) {
if (arr[j] > arr[j+1]) {
temp = arr[j];
arr[j] = arr[j+1];
arr[j+1] = temp;
}
}
}
}

void printArray(int arr[], int size) {

for (int i = 0; i < size; i++) {
printf("%d ", arr[i]);
}
printf("\n");
}

int main() {
int arr[] = {42, 29, 74, 11, 65, 58};
int n = sizeof(arr) / sizeof(arr[0]);

printf("Original Array: ");

printArray(arr, n);

bubbleSort(arr, n);

printf("Sorted Array: ");

printArray(arr, n);

return 0;
}

Ques 6: Write an Algorithm/C Function to Implement Quick Sort

Answer

Algorithm for Quick Sort:

1. Choose a pivot element.

2. Partition the array into two subarrays: one with elements less than the pivot and one with elements
greater than the pivot.
3. Recursively sort the two subarrays.

C Code for Quick Sort:

#include <stdio.h>

void swap(int* a, int* b) {

int temp = *a;
*a = *b;
*b = temp;
}

int partition(int arr[], int low, int high) {

int pivot = arr[high];
int i = (low - 1);
for (int j = low; j < high; j++) {
if (arr[j] < pivot) {
i++;
swap(&arr[i], &arr[j]);
}
}
swap(&arr[i + 1], &arr[high]);
return (i + 1);
}

void quickSort(int arr[], int low, int high) {

if (low < high) {
int pi = partition(arr, low, high);
quickSort(arr, low, pi - 1);
quickSort(arr, pi + 1, high);
}
}

void printArray(int arr[], int size) {

for (int i = 0; i < size; i++) {
printf("%d ", arr[i]);
}
printf("\n");
}

int main() {
int arr[] = {42, 29, 74, 11, 65, 58};
int n = sizeof(arr) / sizeof(arr[0]);

printf("Original Array: ");

printArray(arr, n);

quickSort(arr, 0, n-1);

printf("Sorted Array: ");

printArray(arr, n);

return 0;
}

Ques 7: Write an Algorithm/C Function to Implement Merge Sort

Answer:

Algorithm for Merge Sort:

 1. Divide the array into two halves.
2. Recursively sort each half.
3. Merge the sorted halves into one sorted array.

C Code for Merge Sort:

#include <stdio.h>

void merge(int arr[], int left, int mid, int right) {

int n1 = mid - left + 1;
int n2 = right - mid;

int leftArr[n1], rightArr[n2];

for (int i = 0; i < n1; i++)

leftArr[i] = arr[left + i];
for (int j = 0; j < n2; j++)
rightArr[j] = arr[mid + 1 + j];

int i = 0, j = 0, k = left;
while (i < n1 && j < n2) {
if (leftArr[i] <= rightArr[j]) {
arr[k] = leftArr[i];
i++;
} else {
arr[k] = rightArr[j];
j++;
}
k++;
}

while (i < n1) {

arr[k] = leftArr[i];
i++;
k++;
}

while (j < n2) {

arr[k] = rightArr[j];
j++;
k++;
}
}

void mergeSort(int arr[], int left, int right) {

if (left < right) {
int mid = left + (right - left) / 2;

mergeSort(arr, left, mid);

mergeSort(arr, mid + 1, right);

merge(arr, left, mid, right);

}
}

void printArray(int arr[], int size) {

 for (int i = 0; i < size; i++) {
printf("%d ", arr[i]);
}
printf("\n");
}

int main() {
int arr[] = {42, 29, 74, 11, 65, 58};
int n = sizeof(arr) / sizeof(arr[0]);

printf("Original Array: ");

printArray(arr, n);

mergeSort(arr, 0, n-1);

printf("Sorted Array: ");

printArray(arr, n);

return 0;
}

Ques 8: Using Quick Sort, Give Tracing for the Following Set of Numbers
Answer:

Set of Numbers: 42, 11, 23, 58, 65, 72, 36, 99

Tracing Steps:

1. First Pass:
Pivot: 99, Partitioning: [42, 11, 23, 58, 65, 72, 36, 99]
2. Second Pass (Left subarray, Pivot = 72):
Partitioning: [42, 11, 23, 58, 65, 36, 72, 99]
3. Third Pass (Left subarray, Pivot = 36):
Partitioning: [11, 23, 36, 58, 65, 42]
4. Continue recursively to partition and sort.

The final sorted array: [11, 23, 36, 42, 58, 65, 72, 99]

Searching
Ques 1: Precondition and Algorithm of Binary Search Method
Answer:

Precondition:

 The array must be sorted.

Algorithm for Binary Search:

1. Initialize two variables, low and high, to the start and end indices of the array.
2. While low <= high:
o Calculate mid = (low + high) / 2.
o If the element at mid is equal to the target, return mid.
o If the element at mid is less than the target, set low = mid + 1.
 o If the element at mid is greater than the target, set high = mid - 1.
3. If the target is not found, return -1.

ASSIGNMENT-4: Linked List

Singly Linked List
Ques 1: Differentiate between arrays and linked lists.

Answer:

Feature Arrays Linked Lists

Memory Allocation Contiguous memory block Dynamic, scattered in memory
Fixed size (defined at compile-
Size Dynamic size (can grow or shrink)
time)
Accessing Elements Fast access (random access) Sequential access (no direct access)
Efficient (easy insertion/deletion at both
Insertion/Deletion Costly (shifting elements)
ends)
Efficient, only allocates memory when
Memory Usage Wastes memory due to fixed size
needed
Data Structure Type Static Data Structure Dynamic Data Structure
Access Time Complexity O(1) (constant time) O(n) (linear time)
Implementation
Simple to implement Requires pointers and complex logic
Complexity

Ques 2: Write an algorithm to implement ascending priority queue using a singly linked list.

Answer:

An ascending priority queue means elements are inserted in such a way that the list is always ordered from
lowest to highest priority (or value).

Algorithm for insert() and remove() functions:

insert():

1. Create a new node with the given data.

2. If the list is empty, set the new node as the head.
3. Otherwise, traverse the list and find the correct position for the new node such that the list remains
sorted (ascending order).
4. Insert the node at the correct position.
5. Update the pointers to maintain the order.

remove():

1. If the list is empty, return an error.

2. Remove the node with the highest priority (in this case, the first node in the list).
3. Update the head pointer to the next node.
4. Free the memory of the removed node.
struct Node {
int data;
struct Node *next;
};

void insert(struct Node **head, int data) {

struct Node *newNode = (struct Node*) malloc(sizeof(struct Node));
newNode->data = data;
newNode->next = NULL;

if (*head == NULL || (*head)->data >= data) {

newNode->next = *head;
*head = newNode;
return;
}

struct Node *current = *head;

while (current->next != NULL && current->next->data < data) {
current = current->next;
}

newNode->next = current->next;
current->next = newNode;
}

int remove(struct Node **head) {

if (*head == NULL) {
return -1; // Queue is empty
}
struct Node *temp = *head;
int data = temp->data;
*head = temp->next;
free(temp);
return data;
}

Ques 3: Write an algorithm to reverse a given singly linked list.

Answer:

Algorithm for reversing a singly linked list:

1. Initialize three pointers: prev = NULL, current = head, next = NULL.

2. Traverse the list, and for each node:
o Save the next node: next = current->next
o Reverse the link: current->next = prev
o Move the prev and current pointers one step forward.
3. After the loop, set head = prev to complete the reversal.

void reverse(struct Node **head) {

struct Node *prev = NULL, *current = *head, *next = NULL;

while (current != NULL) {

next = current->next; // Save the next node
 current->next = prev; // Reverse the link
prev = current; // Move prev to current
current = next; // Move to the next node
}

*head = prev; // Update the head pointer

}

Ques 4: Write a program to insert and delete an element after a given node in a singly linked list.

Answer:

Insert After a Node:

1. Find the node after which the new node will be inserted.
2. Create a new node with the given data.
3. Adjust the pointers to insert the new node after the given node.

Delete After a Node:

1. Find the node after which the node will be deleted.

2. Adjust the pointers to bypass the node to be deleted.

void insertAfter(struct Node *prevNode, int data) {

if (prevNode == NULL) {
return; // Error: previous node cannot be NULL
}

struct Node *newNode = (struct Node*) malloc(sizeof(struct Node));

newNode->data = data;
newNode->next = prevNode->next;
prevNode->next = newNode;
}

void deleteAfter(struct Node *prevNode) {

if (prevNode == NULL || prevNode->next == NULL) {
return; // Error: next node is NULL
}

struct Node *temp = prevNode->next;

prevNode->next = temp->next;
free(temp);
}

Doubly Linked List

Ques 1: Write a C/C++ program to add two polynomials represented using doubly linked list.

Answer:

To represent a polynomial, each node in the doubly linked list will store the coefficient and the exponent of
a term.

Steps:
  Create nodes for each term in the polynomial.
 Add polynomials by comparing the exponents and adding the coefficients of terms with the same
exponent.

struct PolyNode {
int coef;
int exp;
struct PolyNode *next;
struct PolyNode *prev;
};

struct PolyNode* addPoly(struct PolyNode *poly1, struct PolyNode *poly2) {

struct PolyNode *result = NULL, *temp, *tail = NULL;

while (poly1 != NULL && poly2 != NULL) {

temp = (struct PolyNode*) malloc(sizeof(struct PolyNode));

if (poly1->exp > poly2->exp) {

temp->coef = poly1->coef;
temp->exp = poly1->exp;
poly1 = poly1->next;
} else if (poly1->exp < poly2->exp) {
temp->coef = poly2->coef;
temp->exp = poly2->exp;
poly2 = poly2->next;
} else {
temp->coef = poly1->coef + poly2->coef;
temp->exp = poly1->exp;
poly1 = poly1->next;
poly2 = poly2->next;
}

temp->next = NULL;
temp->prev = tail;
if (tail != NULL) tail->next = temp;
tail = temp;

if (result == NULL) result = temp;

}

return result;
}

Ques 2: Write a program to concatenate two doubly linked lists.

Answer:

To concatenate two doubly linked lists:

 Traverse the first list to its last node.

 Set the last node's next pointer to point to the first node of the second list.
 Update the second list's prev pointer to the last node of the first list.

void concatenate(struct PolyNode **list1, struct PolyNode *list2) {

if (*list1 == NULL) {
 *list1 = list2;
return;
}

struct PolyNode *temp = *list1;

while (temp->next != NULL) {
temp = temp->next;
}

temp->next = list2;
if (list2 != NULL) list2->prev = temp;
}

Ques 3: Explain the advantages of doubly linked list over singly linked list.

Answer:

Advantages:

1. Bidirectional Traversal: Doubly linked lists can be traversed in both forward and backward
directions, unlike singly linked lists, which can only be traversed in one direction.
2. Efficient Deletion: Insertion and deletion at both ends are more efficient. In a singly linked list,
deleting a node requires knowledge of the previous node, while in a doubly linked list, the previous
pointer is already available.
3. More Flexible: Doubly linked lists allow more complex operations such as reversing a list or
inserting/deleting nodes at any position with fewer pointer manipulations.

Ques 4: Write function delete(p, &x) which deletes the node pointed by p in a doubly linked list.

Answer:

void delete(struct PolyNode *p, int *x) {

if (p == NULL) {
return; // Node to delete is NULL
}

if (p->prev != NULL) {
p->prev->next = p->next;
}
if (p->next != NULL) {
p->next->prev = p->prev;
}

*x = p->coef; // Store the coefficient of the deleted node

free(p);
}

Circular Linked List

Ques 1: State the advantages of circular and doubly linked lists over singly linked lists.

Answer:

Circular Linked Lists:

 Efficient Traversal: Can be traversed in a circular manner, allowing easy access to the first node
from the last node without needing a special reference.
 Simplified Operations: Insertion and deletion at both ends become more straightforward as the list
is circular and does not require special handling for the first and last elements.

Doubly Linked Lists:

 Bidirectional Traversal: Can traverse in both directions, unlike singly linked lists.
 Efficient Deletion: Insertion and deletion operations are more efficient as there is direct access to the
previous node.

Ques 2: Write an algorithm to perform operations on Circular Singly Linked List using a header
node:

Answer:

Add node at the end:

1. Traverse to the last node (where the next pointer points to the header).
2. Insert the new node after the last node and make it point to the header node.

Add node at the beginning:

1. Create a new node and make it point to the node that the header node points to.
2. Update the header node to point to the new node.

void addNodeAtEnd(struct Node *header, int data) {

struct Node *newNode = (struct Node*) malloc(sizeof(struct Node));
newNode->data = data;
struct Node *temp = header;

while (temp->next != header) {

temp = temp->next;
}

newNode->next = header;
temp->next = newNode;
}

void addNodeAtBeginning(struct Node *header, int data) {

struct Node *newNode = (struct Node*) malloc(sizeof(struct Node));
newNode->data = data;

newNode->next = header->next;
header->next = newNode;
}