Assignment No :01

1. Define data structure. List the various linear and non-linear data structures and explain
them in brief.

Data Structure is a specialized format used for organizing, managing, and storing data efficiently. It
allows for the efficient retrieval and modification of data and forms the foundation for designing
algorithms. Data structures help us optimize both time and space complexity for various operations
like searching, sorting, insertion, and deletion.

Linear Data Structures:

These are data structures in which elements are stored sequentially or linearly, meaning one element
is directly connected to the next. The elements can be accessed in a single pass, and there is a specific
order.

1. Array:

• An array is a collection of elements of the same data type, stored at contiguous

memory locations.

• Operations:

• Insertion (fixed size)

• Deletion (fixed size)

• Searching (via index)

• Example: int arr[5] = {1, 2, 3, 4, 5};

• Limitation: Fixed size, so you cannot change its size during runtime.

2. Linked List:

• A linked list is a linear collection of elements (nodes), where each node contains data
and a reference (link) to the next node.

• Types: Singly Linked List, Doubly Linked List, Circular Linked List.

• Advantage: Dynamic in size, elements can be added or removed without needing

contiguous memory.

• Example: head -> data -> next -> data -> next -> null.

3. Stack:

• A stack follows the Last-In-First-Out (LIFO) principle. Elements are added (pushed)
and removed (popped) from the top of the stack.

• Operations: Push, Pop, Peek, IsEmpty.

• Example: Stack of plates where the last plate added is the first to be removed.

• Use case: Function call stack, undo operations in editors.

4. Queue:
• A queue follows the First-In-First-Out (FIFO) principle. Elements are added
(enqueued) at the rear and removed (dequeued) from the front.

• Operations: Enqueue, Dequeue, Peek, IsEmpty.

• Example: Waiting lines (e.g., at a bank or ticket counter).

• Use case: Job scheduling, printer queue.

Non-linear Data Structures:

In non-linear data structures, the data is not arranged sequentially. The elements can have complex
relationships and are typically used for more complex problems.

1. Tree:

• A tree is a hierarchical structure consisting of nodes connected by edges. Each tree

has a root, and every other node has a parent node.

• Types: Binary Tree, Binary Search Tree, AVL Tree, N-ary Tree, etc.

• Operations: Traversal (Inorder, Preorder, Postorder), insertion, deletion, searching.

• Example: Organizational charts, file systems.

2. Graph:

• A graph consists of a set of vertices (nodes) connected by edges. The relationships

between nodes can be one-way (directed) or two-way (undirected).

• Types: Directed, Undirected, Weighted, Unweighted, Cyclic, Acyclic.

• Example: Social networks, city road maps, web pages and their hyperlinks.

• Operations: Depth First Search (DFS), Breadth First Search (BFS), shortest path
algorithms (Dijkstra, A*).

2. What does abstract data type mean? Briefly explain linear and non-linear data structures.

Abstract Data Type (ADT) is a high-level description of a data structure, defined by its behavior
from the user's point of view, without specifying the implementation details. An ADT provides a
logical description of the data and the operations that can be performed on it, but the internal
representation or storage is hidden.

• Example: A Queue can be defined as an ADT that supports enqueue (add an element) and
dequeue (remove an element) operations. The implementation can vary (e.g., using arrays
or linked lists), but the operations remain the same.

Linear Data Structures:

As mentioned previously, in linear data structures, elements are arranged in a sequential manner. The
most common examples are arrays, linked lists, stacks, and queues, which allow for efficient traversal,
insertion, and deletion, but all operations must respect the linear ordering of elements.

Non-Linear Data Structures:

Non-linear data structures have a more complex arrangement of elements. In these structures, the data
does not follow a strict sequence, allowing for more flexible relationships. Graphs and trees are
typical examples, where the elements may be connected in various ways, like parent-child
relationships in trees or inter-node relationships in graphs.

3. Discuss the basic operations performed with linear structures.

In linear data structures, the primary operations allow you to manage and manipulate the elements
in the structure effectively. Here are the most common operations:

1. Insertion:

• Adding a new element to the data structure.

• In an array: you can insert an element at any index if there is enough space.

• In a linked list: insert a new node after a specific node (at the beginning, middle, or
end).

2. Deletion:

• Removing an element from the data structure.

• In an array: you can remove an element and shift other elements if necessary.

• In a linked list: remove a node by adjusting the pointers (either the previous or next
pointer).

3. Traversal:

• Accessing each element in the structure one by one.

• In an array, you can access elements by their indices.

• In a linked list, you need to start from the head node and follow the links until you
reach the end.

4. Search:

• Finding an element in the data structure.

• In an array, you can use linear search or binary search (if the array is sorted).

• In a linked list, you traverse the list and compare each node’s data until you find the
desired element.

5. Update:

• Modifying an element in the structure.

• In an array, you can directly access and modify an element via its index.

• In a linked list, you must traverse the list to find the node and then update its data.
6. Peek/Top:

• In stack and queue operations, you can view the element at the top (stack) or front
(queue) without removing it.

7. Check Empty:

• In stack and queue, we need to check if the structure is empty.

• For example, checking if the top of a stack is NULL or if the front of the queue is
NULL.

4. Explain the dynamic memory allocation functions in C.

Dynamic memory allocation in C allows you to allocate memory at runtime using pointers. This is
especially useful when you don’t know the amount of memory needed beforehand. The following
functions are used for dynamic memory allocation:

1. malloc():

• Allocates a block of memory of the specified size.

• Returns a pointer to the beginning of the block. If memory allocation fails, it returns
NULL.

• Syntax: ptr = (type*) malloc(size_in_bytes); • Example: int *arr = (int*) malloc(5 *

sizeof(int));

2. calloc():

• Allocates memory for an array of elements and initializes them to zero.

• It takes two parameters: the number of elements and the size of each element.

• Syntax: ptr = (type*) calloc(num_elements, element_size);

• Example: int *arr = (int*) calloc(5, sizeof(int));

3. realloc():

• Resizes an already allocated block of memory.

• The new size is specified, and it returns a pointer to the resized memory block.

• Syntax: ptr = (type*) realloc(ptr, new_size);

• Example: arr = realloc(arr, 10 * sizeof(int));

4. free():

• Frees up the dynamically allocated memory and releases it back to the system.

• Syntax: free(ptr);

• Example: free(arr);
Using dynamic memory allocation helps in creating flexible programs that can adapt to different
memory requirements at runtime.

5. Differentiate the following terms:

(a) Linear and Non-Linear Data Structures

Linear Data Structure Non-Linear Data Structure

Elements are arranged in a sequence. Elements are arranged in a hierarchical or networked structure.

Each element has a predecessor and successor. There is no such direct relationship between elements.

Easy to implement and manage. More complex to implement and manage.

Memory is contiguous (arrays). Memory can be non-contiguous (graphs).

Operations like traversal and searching are simple. Traversal requires more complex algorithms (DFS, BFS).

Examples: Array, Linked List, Stack, Queue. Examples: Tree, Graph.

Best used for simpler problems where data can be Best suited for more complex problems where relationships
sequentially processed. between elements are important.

Stack Queue

Follows LIFO (Last-In, First-Out) order. Follows FIFO (First-In, First-Out) order.

Elements are added and removed from the same end, called Elements are added from the rear and removed from
the top. the front.

Operations: Push, Pop, Peek, IsEmpty. Operations: Enqueue, Dequeue, Peek, IsEmpty.

Example: Undo functionality in text editors. Example: Print job processing.

Uses: Function calls, expression evaluation. Uses: CPU scheduling, managing requests in queues.
(b) Primitive and Non-Primitive Data Structures
Primitive Data Structure Non-Primitive Data Structure

Directly provided by the language. Built using primitive data types.

Example: int, char, float, etc. Example: Arrays, Linked Lists, Trees, Graphs, etc.

Stores a single value. Can store multiple values or objects.

Not divided into smaller components. Divided into smaller subcomponents (nodes, edges).

Simple data types with direct memory allocation. Complex structures requiring additional handling.

Example: int a = 10; Example: int arr[5];

(c) Stack and Queue

(d) Static and Dynamic Data Structures

Static Data Structure Dynamic Data Structure

Size is fixed at compile-time. Size can change during runtime.

Memory is allocated at compile-time. Memory is allocated and freed at runtime.

Cannot grow or shrink in size after allocation. Can grow or shrink in size during program execution.

Example: Arrays. Example: Linked Lists, Stacks, Queues.

Static Data Structure Dynamic Data Structure

More efficient in terms of memory access speed. Provides flexibility in memory usage.

6. What is a stack? Explain its operations and applications.

A stack is a linear data structure that follows the Last-In-First-Out (LIFO) principle. The last
element added to the stack is the first one to be removed.

Operations:

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

2. Pop: Removes the top element of the stack.

3. Peek/Top: Returns the top element without removing it.

4. IsEmpty: Checks whether the stack is empty.

5. Size: Returns the number of elements in the stack.

Applications:

1. Function calls: The call stack in programming languages is used to manage function calls,
storing local variables and function return addresses.

2. Expression evaluation: Infix, prefix, and postfix expression evaluation use stacks to convert
between different notations.

3. Undo operations: Used in applications like text editors to allow users to undo their previous
actions.

4. Browser history: The stack helps maintain the history of visited pages.

5. Balanced Parentheses: A stack can be used to check whether an expression has balanced
parentheses.

7. What is a Queue? Explain its operations and applications.

A Queue is a linear data structure that follows the First-In-First-Out (FIFO) principle. The first
element added to the queue will be the first one to be removed. The queue is often likened to a
realworld queue, such as a line at a ticket counter or a queue in a printer's job processing system.

Operations:

1. Enqueue: Adds an element to the back (rear) of the queue.

2. Dequeue: Removes an element from the front of the queue.

3. Front: Returns the front element of the queue without removing it.

4. Rear: Returns the rear element of the queue without removing it.

5. IsEmpty: Checks if the queue is empty.

6. Size: Returns the number of elements in the queue.

Applications:

1. Job Scheduling: Operating systems use queues to schedule tasks and processes. The first task
to arrive is the first to be executed.

2. CPU Scheduling: A queue is used to manage processes in the operating system. The
processes are executed in the order they arrive.

3. Breadth-First Search (BFS): In graph traversal, a queue is used to explore nodes level by
level.

4. Printer Queue: When multiple documents are sent to a printer, they are processed in the
order they were added to the queue.

5. Call Center Systems: Incoming calls are placed in a queue, and operators serve them in the
order of arrival.

8. Explain the difference between linear and non-linear data structures.

Linear Data Structure Non-Linear Data Structure

Elements are arranged in a sequential manner. Elements are not arranged sequentially.

Each element has a direct predecessor and

successor. No direct relationship between elements.

Traversal is simpler, usually from start to end. Traversal is more complex (e.g., DFS, BFS).

Examples: Arrays, Linked Lists, Stacks, Queues. Examples: Trees, Graphs.

Memory is contiguous (in arrays). Memory is non-contiguous (in graphs, trees).

Used for problems with simpler relationships Used for problems where data relationships are hierarchical or
between data. interconnected.

9. What is a Tree? Explain its types and operations.

A Tree is a hierarchical, non-linear data structure made up of nodes connected by edges. It consists of
a root node, child nodes, and subtrees. Trees are widely used to represent hierarchical structures like
file systems and organizational charts.

Types of Trees:

1. Binary Tree: A tree where each node has at most two children, usually referred to as the left
and right child.

2. Binary Search Tree (BST): A binary tree where for each node, the left child contains values
less than the node, and the right child contains values greater than the node.

3. AVL Tree: A self-balancing binary search tree where the difference in height between the left
and right subtrees of any node is at most one.

4. Heap: A complete binary tree where each parent node is greater than (or less than) its
children, used for implementing priority queues.

5. N-ary Tree: A tree where each node can have at most 'N' children.

Operations:

1. Traversal:

• Inorder: Traverse the left subtree, visit the root, then the right subtree.

• Preorder: Visit the root, then the left and right subtrees.

• Postorder: Traverse the left and right subtrees, then visit the root.

• Level-order: Visit nodes level by level, often implemented using a queue.

2. Insertion: Insert a node into the tree based on its value (in BSTs, this is done to maintain the
binary search property).

3. Deletion: Remove a node from the tree. In the case of BSTs, it requires ensuring the
properties of the tree are preserved.

4. Searching: Find a node in the tree. In a BST, it can be done more efficiently by comparing
values at each node.

Applications:

1. Hierarchical Data Representation: Trees are used to represent hierarchical data like
organizational charts and folder structures in file systems.

2. Expression Parsing: In expressions like arithmetic expressions, trees (specifically expression

trees) are used to represent operators and operands.
3. Decision Making: Decision trees used in machine learning are a form of tree used for making
decisions based on conditions.

4. Database Indexing: B-trees and B+ trees are used in databases for indexing and searching.

10. What is a Graph? Explain its types and applications.

A Graph is a non-linear data structure made up of a set of vertices (nodes) and edges (connections
between the vertices). Graphs are useful for representing complex relationships, such as social
networks, transportation networks, or web page links.

Types of Graphs:

1. Undirected Graph: In this type of graph, the edges do not have a direction. If there is an
edge between two nodes, you can traverse in both directions.

2. Directed Graph (Digraph): In this type of graph, edges have a direction. If there is an edge
from node A to node B, you cannot traverse from B to A unless there is a reverse edge.

3. Weighted Graph: Each edge has a weight (a numerical value), which could represent the
distance, cost, or time to traverse the edge.

4. Unweighted Graph: The edges do not have any weight; they simply represent a connection
between vertices.

5. Cyclic Graph: A graph that contains at least one cycle (a path where the first and last vertex
are the same).

6. Acyclic Graph: A graph that does not contain any cycles.

Operations:

1. Traversal:

• Depth-First Search (DFS): Start at the root and explore as far as possible along each
branch before backtracking.

• Breadth-First Search (BFS): Start at the root and explore all neighbors at the present
depth level before moving on to nodes at the next depth level.

2. Search: Searching for a specific vertex or edge in the graph.

3. Shortest Path: Algorithms like Dijkstra's or Bellman-Ford are used to find the shortest path
between two vertices in weighted graphs.

4. Cycle Detection: Algorithms to detect cycles in a graph, which is important in various

algorithms like topological sorting.

Applications:

1. Social Networks: Graphs can represent social media networks, where users are vertices and
their relationships (like friends, followers) are edges.

2. Routing Algorithms: Graphs are used in network routing protocols and algorithms to find the
best path for data packets in the network.
3. Web Page Link Structure: Graphs represent the hyperlinks between web pages.

4. Recommendation Systems: Graphs help in representing user-item interactions, which are

then used for recommendation algorithms.

5. Computer Networks: Representing communication paths between computers or devices.

11. Explain the different types of sorting algorithms.

Sorting is the process of arranging data in a particular order (ascending or descending). Below are the
most common types of sorting algorithms:

1. Bubble Sort:

• Repeatedly steps through the list, compares adjacent items, and swaps them if they
are in the wrong order. This process repeats until the list is sorted.

• Time Complexity: O(n²)

• Simple but inefficient for large datasets.

2. Selection Sort:

• Divides the list into a sorted and unsorted part. The smallest (or largest) element from
the unsorted part is selected and swapped with the first unsorted element. This
process is repeated for the remaining unsorted elements.

• Time Complexity: O(n²)

3. Insertion Sort:

• Builds the sorted list one item at a time by taking elements from the unsorted part and
inserting them into the correct position in the sorted part.

• Time Complexity: O(n²), but efficient for small datasets or nearly sorted lists.

4. Merge Sort:

• A divide-and-conquer algorithm. It divides the list into two halves, recursively sorts
them, and then merges them back together.

• Time Complexity: O(n log n) • Stable and efficient for large datasets.

5. Quick Sort:

• A divide-and-conquer algorithm. It selects a 'pivot' element and partitions the array

into two parts: one with elements less than the pivot, and one with elements greater.
These parts are recursively sorted.

• Time Complexity: O(n log n) (on average), but can degrade to O(n²) in the worst
case.

• Very fast in practice and commonly used for large datasets.

6. Heap Sort:
• Converts the list into a heap (a binary tree with a specific property), and then sorts it
by repeatedly extracting the maximum (or minimum) element from the heap and
rebuilding the heap. • Time Complexity: O(n log n)

• Efficient but not stable.

7. Radix Sort:

• Sorts numbers by processing individual digits. It processes digits starting from the
least significant to the most significant (or vice versa).

• Time Complexity: O(nk), where 'k' is the number of digits in the largest number.

• Efficient for large datasets with a small range of values.

8. Counting Sort:

• Works by counting the number of occurrences of each element and then calculates the
position of each element in the sorted output.

• Time Complexity: O(n+k), where 'k' is the range of input.

• Efficient for small ranges of integers.

Assignment No:02

1. Define Sparse Matrix. Briefly explain representation of sparse matrix with the help of link list
and array.
Sparse Matrix: A sparse matrix is a matrix in which the majority of its elements are zero. In contrast, a
dense matrix has very few zero elements. Sparse matrices are commonly encountered in real-world
problems, such as in graph theory, where most of the elements (edges) are not present. Storing all the
elements of a sparse matrix in a conventional 2D array would be inefficient as it would require
excessive space for zero elements.

Representation: To represent sparse matrices efficiently, we use techniques that store only the nonzero
elements. Two common ways of representing sparse matrices are using arrays and linked lists.

Array Representation:
Triple Array Representation: A sparse matrix can be represented by three arrays: one for row indices,
one for column indices, and one for the values of the non-zero elements.
Format: Each non-zero element is stored as a triplet (row index, column index, value), and these
triplets are stored in an array.

Example: Consider the following matrix:

0030

0000

5000

0000

It can be represented as:

Row indices: [0, 2]

Column indices: [2, 0]

Values: [3, 5]

Linked List Representation:

A more space-efficient way to represent a sparse matrix is by using a singly linked list where each
node stores a non-zero element and its row and column indices.

Each node contains: row

(row index), col (column

index), value (non-zero

element).

A linked list of linked lists can be used for storing each row as a separate linked list. This allows
efficient storage and access to non-zero elements.

Example: For the same matrix above, the linked list representation would look something like this:

Row 0: (0, 2, 3)

Row 2: (2, 0, 5)

2. Given a two-dimensional array A1(1:8, 7:14) stored in row-major order with base address 100
and size of each element is 4 bytes, find the address of the element A1(4, 12).
In row-major order, the elements are stored row by row. The formula for the address of an element
A[i][j]A[i][j] in a row-major ordered matrix is:

Address=Base Address+((i−1)×number of columns+(j−7))×size of elementAddress=Base Address+((i

−1)×number of columns+(j−7))×size of element Given:

• Base address = 100

• Size of each element = 4 bytes

• i=4i=4, j=12j=12

• The number of rows = 8, the number of columns = 8 (since columns are from 7 to 14)

Now, applying the formula:

Address=100+((4−1)×8+(12−7))×4

Address=100+((4−1)×8+(12−7))×4

Address=100+(3×8+5)×4

Address=100+(3×8+5)×4 Address=100+(24+5)×4

Address=100+(24+5)×4

Address=100+29×4

Address=100+29×4

Address=100+116=216

Address=100+116=216

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

3. Given a two-dimensional array Z1(2:9, 9:18) stored in column-major order with base address
100 and size of each element is 4 bytes, find the address of the element Z1(4, 12).

In column-major order, the elements are stored column by column. The formula for the address of
an element Z[i][j]Z[i][j] in a column-major ordered matrix is:

Address=Base Address+((j−9)×number of rows+(i−2))×size of element

Address=Base Address+((j−9)×number of rows+(i−2))×size of element Given:

• Base address = 100

• Size of each element = 4 bytes

• i=4i=4, j=12j=12

• The number of rows = 8, the number of columns = 10 (since rows are from 2 to 9 and
columns are from 9 to 18) Now, applying the formula:

Address=100+((12−9)×8+(4−2))×4

Address=100+((12−9)×8+(4−2))×4

Address=100+(3×8+2)×4

Address=100+(3×8+2)×4

Address=100+(24+2)×4

Address=100+(24+2)×4

Address=100+26×4

Address=100+26×4

Address=100+104=204

Address=100+104=204

So, the address of element Z1(4, 12) is 204.

Stack Questions:

1. What is a stack? Explain basic primitive operation of stack with example.

A stack is a linear data structure that follows the Last In, First Out (LIFO) principle. This means the
last element inserted into the stack will be the first one to be removed. Stacks are used in a variety of
applications such as function calls, expression evaluation, and backtracking algorithms.

Basic Operations:

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

• Example: Push 5 onto the stack → Stack: [5]

2. Pop: Removes the top element from the stack.

• Example: Pop from the stack → Stack: []

3. Peek (or Top): Returns the top element without removing it.

• Example: Peek at the stack → Top element: 5

4. IsEmpty: Checks if the stack is empty.

• Example: Is the stack empty? → No (if there are elements) 5. Size: Returns

the number of elements in the stack.

2. Differentiate peep() and pop() functions.

peep() pop()

The peep() function returns the top element of the stack The pop() function removes and returns the top element of the
without removing it. stack.

It allows you to view the top element. It modifies the stack by reducing its size.

Example: If the stack is [5, 10, 15], peep() will return Example: If the stack is [5, 10, 15], pop() will return 15 and the
15. stack will become [5, 10].

peep() does not change the state of the stack. pop() changes the stack by removing the top element.

Used when you only need to check the top element. Used when you need to remove the top element.

peep() pop()

Example usage: Checking if the top element is the

desired value.
Example usage: Removing an element after processing it.
Returns the value of the top element. Returns the value of the top element and removes it.

peep() does not raise an underflow error. pop() may raise an underflow error if the stack is empty.

3. Write a C program to implement a stack with all necessary overflow and underflow checks
using array.

#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 onto 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: %d\n",

peek()); printf("%d popped from stack\

n", pop()); return 0;

4. Write an algorithm to reverse a string of characters using stack.

1. Algorithm:

1. Create a stack to store characters.

2. Push all characters of the string onto the stack.

3. Pop the characters from the stack and store them in the original string.
#include <stdio.h>

#include <string.h>

#define MAX 100

char stack[MAX];

int top = -1;

void push(char c) { stack[+

+top] = c;

char pop() { if (top !

= -1) { return

stack[top--];

return -1; }

void reverseString(char str[]) {

int len = strlen(str); for (int i

= 0; i < len; i++)

{ push(str[i]); } for

(int i = 0; i < len; i++)

{ str[i] = pop();

int main() { char str[] = "Hello";

reverseString(str); printf("Reversed

string: %s\n", str); return 0; }

5. Write an algorithm to check if an expression has balanced parentheses using stack.

1. Algorithm:

1. Create an empty stack.

2. Traverse the expression.

3. For every opening parenthesis, push it onto the stack.

4. For every closing parenthesis, check if the stack is empty; if it is not, pop the stack.

5. After processing all characters, check if the stack is empty.

--→ #include <stdio.h>

#include <string.h>

#define MAX 100

char stack[MAX];

int top = -1;

void push(char c) { stack[+

+top] = c;

char pop() { if (top !

= -1) { return

stack[top--];
}

return -1;

int isBalanced(char expr[]) { for

(int i = 0; i < strlen(expr); i++)

{ if (expr[i] == '(')

{ push(expr[i]);

} else if (expr[i] == ')') {

if (top == -1) { return

0; // Unbalanced

pop();

return top == -1; // Balanced if stack is empty

int main() { char expr[] =

"(a+b)*(c+d)"; if

(isBalanced(expr))

{ printf("Balanced\n");

} else

{ printf("Unbalanced\n");

return 0;

6. What is recursion? Write a C program for GCD using recursion.

Recursion is a technique in programming where a function calls itself in order to solve a problem. It
breaks down a problem into smaller sub-problems that are easier to solve. Each recursive call should
eventually reach a base case, which stops the recursion.

C Program for GCD (Greatest Common Divisor) using Recursion:

The GCD of two numbers can be calculated using Euclid's algorithm:

• GCD(a, b) = GCD(b, a % b)

• The base case is when b becomes 0, then GCD(a, 0) = a.

#include <stdio.h>

// Function to calculate GCD using recursion

int gcd(int a, int b) { if (b == 0)

return a; else

return gcd(b, a % b);

int main() {

int a, b; printf("Enter two

numbers: "); scanf("%d %d",

&a, &b);

printf("GCD of %d and %d is: %d\n", a, b, gcd(a, b));

return 0;

7. Write a recursive algorithm to find factorial.

The factorial of a non-negative integer n, denoted as n!, is the product of all positive integers less
than or equal to n. The recursive formula is:

• factorial(n) = n * factorial(n-1) for n > 0

• factorial(0) = 1 (base case)

Recursive algorithm to find factorial:

#include <stdio.h>

// Recursive function to calculate factorial

int factorial(int n) { if (n == 0)

return 1; else return n * factorial(n

- 1);

int main() {

int n;

printf("Enter a number: ");

scanf("%d", &n);

printf("Factorial of %d is: %d\n", n, factorial(n));

return 0;

8. Enlist difference between recursive and iterative algorithms. Write any one recursive function
showing the stack contents while function call and return.

Difference Between Recursive and Iterative Algorithms:

Criteria Recursive Algorithm Iterative Algorithm

A function calls itself to solve the The problem is solved using loops (for,
Definition problem. while).

Uses function call stack, leading to Uses a fixed amount of memory, mainly
Memory Usage high memory usage. for variables.

May be more efficient for certain

Can be more elegant and easier to problems in terms of memory and
Complexity understand for certain problems. speed.

Requires a base case to terminate the Does not require a base case but
Base Case recursion. requires proper loop conditions.
Can have higher overhead due to
Performance multiple function calls. Generally more efficient as it uses loops.

Ease of Easier to implement for problems Easier to implement for simple

Implementation like tree traversal, factorial, etc. problems, like summing an array.

Fibonacci series, Factorial, Tower of Sum of numbers, Sorting (like Bubble

Examples Hanoi, Tree Traversal. Sort).

Recursive Function Showing Stack Contents:

Let's consider the recursive function for factorial, and we'll print the stack contents at each call:

#include <stdio.h>

int factorial(int n) {

printf("Calling factorial(%d)\n", n); if (n == 0)

{ printf("Base case reached: factorial(0) = 1\n"); return 1;

} else { int result = n * factorial(n - 1); printf("Returning

from factorial(%d), result = %d\n", n, result); return result;

int main() { int n = 5; printf("Factorial of %d

is: %d\n", n, factorial(n)); return 0;

Stack contents for factorial(5):

• Calling factorial(5) → Stack: [factorial(5)]

• Calling factorial(4) → Stack: [factorial(5), factorial(4)]

• Calling factorial(3) → Stack: [factorial(5), factorial(4), factorial(3)]

• Calling factorial(2) → Stack: [factorial(5), factorial(4), factorial(3), factorial(2)]

• Calling factorial(1) → Stack: [factorial(5), factorial(4), factorial(3), factorial(2), factorial(1)]

• Base case factorial(0) reached → Stack: [factorial(5), factorial(4), factorial(3), factorial(2),

factorial(1), factorial(0)]
• Returning from factorial(1) → Stack: [factorial(5), factorial(4), factorial(3), factorial(2)]

• Returning from factorial(2) → Stack: [factorial(5), factorial(4), factorial(3)]

• Returning from factorial(3) → Stack: [factorial(5), factorial(4)]

• Returning from factorial(4) → Stack: [factorial(5)]

• Returning from factorial(5) → Stack: []

9. Write a C user-defined function for Tower of Hanoi for N disks and three towers. Write stack
representation for N=4.

Tower of Hanoi Problem: The goal is to move N disks from the source tower to the destination tower
using an auxiliary tower, following these rules:

1. Only one disk can be moved at a time.

2. A disk can only be placed on an empty tower or a tower with a larger disk on top.

Recursive Algorithm for Tower of Hanoi:

• Move N-1 disks from source to auxiliary tower.

• Move the Nth disk from source to destination tower.

• Move the N-1 disks from auxiliary tower to destination tower.

#include <stdio.h>

void towerOfHanoi(int n, char source, char destination, char auxiliary) {

if (n == 1) { printf("Move disk 1 from %c to %c\n", source,

destination);

return;

towerOfHanoi(n - 1, source, auxiliary, destination);

printf("Move disk %d from %c to %c\n", n, source, destination);

towerOfHanoi(n - 1, auxiliary, destination, source);

int main() { int n = 4;

towerOfHanoi(n, 'A', 'C', 'B');

return 0;

}
Stack Representation for N = 4: Each recursive call represents a function call to move a disk. For N
= 4, the sequence of function calls would look like this:

• Move 3 disks from A to B (recursive call)

• Move 2 disks from A to C (recursive call)

• Move 1 disk from A to B (recursive call)

• Base case: Move disk 1 from A to B

• Move disk 2 from A to C

• Move 1 disk from B to C (recursive call)

• Base case: Move disk 1 from B to C

• Move disk 3 from A to B

• Move 2 disks from C to B (recursive call)

• Move 1 disk from C to A (recursive call)

• Base case: Move disk 1 from C to A

• Move disk 2 from C to B

• Move 1 disk from A to B (recursive call)

• Base case: Move disk 1 from A to B

• Move disk 4 from A to C

• Move 3 disks from B to C (recursive call)

10. Explain Difference Between FIFO and LIFO.

Criteria FIFO (First In, First Out) LIFO (Last In, First Out)

FIFO is a queue system where the first LIFO is a stack system where the last
Definition element added is the first to be removed. element added is the first to be removed.

Data Structure
Type Queue Stack

Order of First element in is processed first (like a Last element in is processed first (like a
Operations queue at a ticket counter). stack of plates).

Example Queue (e.g., printer queue) Stack (e.g., stack of plates or books)
Data Removal Removed in the order they were added. Removed in reverse order of addition.

Used in scheduling, buffers, and handling Used for function calls, undo operations,
Usage requests. and depth-first search.

12. What is the advantage of Polish expression over infix notation? Write an algorithm to
convert an infix expression into reverse Polish expression.

Advantages of Polish Expression (Prefix and Postfix) over Infix Notation:

1. No need for parentheses: In Polish (Prefix) and Reverse Polish (Postfix) notations,
parentheses are not needed to dictate the order of operations. The operator precedence is
inherent in the expression's structure.

2. Easier for computers to evaluate: Reverse Polish notation (RPN) is easy for computers to
evaluate because it removes the need for parsing operator precedence or handling parentheses
during evaluation.

3. Faster computation: Polish and Reverse Polish expressions reduce the computational
overhead by eliminating the need to perform operator precedence and parenthesis evaluation.

Algorithm to Convert Infix to Reverse Polish Expression:

We can use Shunting Yard algorithm (created by Edsger Dijkstra) to convert an infix expression to a
postfix (Reverse Polish) expression.

1. Create an empty stack for operators and an empty list for the output.

2. Read the input from left to right.

3. For each token (operand, operator, or parenthesis):

• If the token is an operand, add it directly to the output.

• If the token is an operator:

• While the stack is not empty and the top of the stack has the same or higher
precedence, pop the stack to the output.

• Push the current operator onto the stack.

• If the token is a left parenthesis, push it onto the stack.

• If the token is a right parenthesis, pop operators from the stack to the output until a
left parenthesis is encountered.

4. After reading the input, pop all operators from the stack to the output.

#include <stdio.h>

#include <ctype.h>

#include <string.h>
#define MAX 100

int precedence(char c) { if (c

== '^') return 3; if (c == '*' ||

c == '/') return 2; if (c == '+' ||

c == '-') return 1; return 0;

void infixToPostfix(char* infix, char* postfix) {

char stack[MAX];

int top = -1, k = 0;

for (int i = 0; infix[i] != '\0'; i++) {

char c = infix[i];

if (isalnum(c)) { postfix[k++] = c; // If the character is an

operand, add it to output

} else if (c == '(') { stack[+

+top] = c; // Push '(' to the stack

} else if (c == ')') { while (top >= 0 &&

stack[top] != '(') { postfix[k++] = stack[top--]; //

Pop until '(' is found

top--; // Pop '('

else {

while (top >= 0 && precedence(stack[top]) >= precedence(c))

{ postfix[k++] = stack[top--]; // Pop operators with higher or equal

precedence
}

stack[++top] = c; // Push the current operator to the stack

// Pop all remaining operators from the stack

while (top >= 0) { postfix[k++] =

stack[top--];

postfix[k] = '\0'; // Null-terminate the postfix expression

int main() { char infix[MAX],

postfix[MAX]; printf("Enter an

infix expression: "); scanf("%s",

infix);

infixToPostfix(infix, postfix);

printf("Postfix Expression: %s\n", postfix);

return 0;

13. Convert the given infix expression to postfix and prefix expression.

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

• Postfix: A B C - D E - * F + G / + H J - $

• Prefix: $ + + A * - B C - D E F / G - H J

2) (A + B) * (C – D) $ E * F

• Postfix: A B + C D - * E F * $
• Prefix: $ * + A B - C D * E F

3) (A + B) * (C ^ (D – E) + F) – G

• Postfix: A B + C D E - ^ F + * G -

• Prefix: - * + A B + ^ C - D E F G

4) A + B * C

• Postfix: A B C * +

• Prefix: + A * B C

5) A + B * C ^ D – E

• Postfix: A B C D ^ * + E -

• Prefix: - + A * B ^ C D E

6) A + [(B + C) + (D + E) * F] / G

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

• Prefix: + A / + + B C * F + D E G

7) (A + B) * C / D + E ^ F / G

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

• Prefix: + / * + A B C D ^ E F / G

8) (A + B) * C / D

• Postfix: A B + C * D /

• Prefix: / * + A B C D

9) ((A + B – C / D) / E)

• Postfix: A B + C D / - E /

• Prefix: / - + A B / C D E

10) A / (B – C / D ^ E) + F
• Postfix: A B C D E ^ / - / F +

• Prefix: + / A - B / C ^ D E F

11) A – B / (C * D ^ E)

• Postfix: A B C D E ^ * / -

• Prefix: - A / B * C ^ D E

2. Evaluate the following expressions.

1) 5 + 4 * 2

First,perform the multiplication

(4 * 2): 42=8 Now,

perform the addition

(5+8):

5+8=13

Answer: 13

2) 4 + 2 * 5 ^ 2 + 9 / 3 – 1 * 8

Start by handling the exponentiation (5 ^ 2): 5^2=25

Next, perform the multiplication and division (from left to right):

First, 2 * 25: 2 25=50

Then, 9 / 3: 9/3=3

Then, 1 * 8: 1 8 = 8

Now, substitute the results and perform the remaining addition and

subtraction: 4+50+3−8

First, 4 + 50 = 54
Then, 54 + 3 = 57 Finally,

57 - 8 = 49

Answer: 49

3) 40 25 + 20 5 * 3 + *

40 25 +: Add 40 + 25: 40 + 25 =65

Now, the expression becomes: 65 20 5 * 3 + *

20 5=100

Now, the expression becomes: 65 100 3 + *

100+3=103

Now, the expression becomes: 65 103 *

65 103=6695

4) 9 + 5 * 7 – 6 ^ 2 + 9 / 3

Start by handling the exponentiation (6 ^ 2):

6^2=36

Next, perform the multiplication and division (from left to right):

First, 5 * 7: 5 7=355 * 7 = 355 7=35

Then, 9 / 3: 9/3=39 / 3 = 39/3=3

Now, substitute the results and perform the remaining addition and subtraction:

9+35−3

First, 9 + 35 = 44 Then,

44 - 36 = 8

Finally, 8 + 3 = 11

Answer: 11

5) 8 * 2 -1 + 7 * 5

First, perform the multiplication:

8 * 2: 8 2=16

7 * 5: 7 5=35
Now, substitute the results and perform the remaining addition and

subtraction:

16−1+35

First, 16 - 1 = 15

Then, 15 + 35 = 50

Answer: 50

6. Evaluate the following Postfix expression assume A=1, B=2, C=3

1) A B + C – B A + C - +

2) A B C + * C B A - + *

1. A B + C – B A + C - +

Substitute ( A = 1 ), ( B = 2 ), and ( C = 3 ):

(12+3-21+3-+)

( 1 + 2 = 3 ) → `3 3 - 2 1 + 3 - +`

( 3 - 3 = 0 ) → `0 2 1 + 3 - +`

( 2 + 1 = 3 ) → `0 3 3 - +`

( 3 - 3 = 0 ) → `0 0 +`

(0+0=0)

Final Result: 0

2.A B C + * C B A - +

Substitute ( A = 1 ), ( B = 2 ), and ( C = 3 ):

(123+*321-+*)

(2+3=5)→15*321-+

( 1 * 5 = 5) → `5 3 2 1 - +

(2-1=1)→531+
(3+1=4)→54*

( 5 * 4 = 20 )

Final Result: 20
Name :Vishal Rajesh Bhutekar

Roll No :BT24S05F002

Assignment No: 3 - Linked List

Question 1: Differentiate between Arrays and Linked Lists

1. Structure:

• Array : Arrays are collections of elements stored in contiguous memory locations,

meaning each element is positioned next to the previous one. This structure allows for
quick access to any element using its index, providing an O(1) time complexity for
accessing an element.
• Linked List : Linked Lists are collections of nodes where each node contains data and a
pointer to the next node in the sequence. In a singly linked list, each node only points to
the next node, creating a chain of nodes. This structure makes linked lists dynamic and
more flexible than arrays but requires sequential access, which is slower than array
indexing.

2. Memory Allocation:

• Array : Arrays have a fixed size that must be defined at the time of their creation, and
memory is allocated in contiguous blocks. This can be a disadvantage if the size of the
array needs to change, as resizing is often costly in terms of time and memory.
• Linked List : Linked Lists use dynamic memory allocation. Each node is allocated
separately, and nodes are linked together using pointers. This means the list can grow or
shrink easily by adding or removing nodes without a need to reallocate a contiguous
memory block.

3. Flexibility and Resizing:

• Array : Fixed in size; if you need more space, a new array must be created with
additional space, and the existing elements must be copied over. This can be inefficient in
cases of frequent resizing.
• Linked List : Supports dynamic resizing, allowing easy addition and removal of nodes
without worrying about a fixed size. Thus, linked lists are useful when the number of
elements is unknown at the outset or may vary significantly.

4. Insertion and Deletion:

• Array : Insertion and deletion are costly operations (O(n) in the worst case)
because all elements following the inserted/deleted element must be shifted to
maintain contiguous memory.
• Linked List : Inserting and deleting nodes in a linked list, especially at the
beginning or middle, is more efficient, as only the pointers need to be updated.
However, accessing a specific element by position requires traversing from the head,
which is O(n).

5. Example Use Cases:

• Array : Suitable for applications where fast element access is essential, and the size of the
collection is known in advance (e.g., look-up tables, databases).
• LinkedList : Used in scenarios requiring frequent insertions and deletions (e.g.,
implementation of stacks, queues, and real-time applications).

•.

Question 2: Write an Algorithm to Implement Ascending Priority Queue

Using Singly Linked List
An ascending priority queue is a data structure where elements are ordered based on priority,
with the lowest priority (smallest value) at the front. In this example, we will use a singly linked
list to implement this priority queue.

Algorithm:

1. Insertion ( insert() ) : o Step 1: Create a new node with the

given priority and data.
o Step 2: If the list is empty or if the priority of the new node is less than the head
node, set the new node as the head.
o Step 3: Otherwise, traverse the list to find the correct position based on priority
order. Insert the new node at the appropriate position to maintain ascending order. o
Complexity: O(n) due to the traversal to find the insertion point.
2. Removal ( remove() ) :
o Step 1: Check if the list is empty. If it is, output an error message. o Step 2:
Remove the head node, as it contains the element with the lowest priority. o Step
3: Update the head pointer to the next node.
o Complexity: O(1) as it only removes the head.

Code Example in C :

c
Copy code
#include <stdio.h>
#include
<stdlib.h> struct
Node { int data;
int priority;
struct Node* next;
};

// Insert node in ascending order of priority void

insert(struct Node** head, int data, int priority) {
struct Node* newNode = (struct Node*)malloc(sizeof(struct
Node)); newNode->data = data; newNode->priority = priority;
newNode->next = NULL;

if (*head == NULL || (*head)->priority > priority)

{ newNode->next = *head;
*head = newNode;
} else {
struct Node* current = *head; while (current->next != NULL &&
current->next->priority <= priority) { current = current->next;
}
newNode->next = current->next; current-
>next = newNode;
}
}

// Remove node with the highest priority (smallest value)

void remove(struct Node** head) {
if (*head == NULL)
{ printf("Queue is empty\n");
return;
}
struct Node* temp = *head;
*head = (*head)->next;
free(temp);
}

Question 3: Write an Algorithm to Reverse a Given Singly Linked List

Reversing a singly linked list involves changing the direction of the next pointers, such that the
last node becomes the head and the head node becomes the last node.

Algorithm:

1. Initialize three pointers: prev (initially NULL), current (points to the head), and next (will
be used to store the next node).
2. Traverse the list. For each node: o Save the next node. o Change the next pointer of
the current node to prev .
o Move prev and current one step forward.
3. Once current becomes NULL (end of the list), prev will be the new head of the reversed
list.

Code Example in C :

void reverse(struct Node** head) {

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

while (current != NULL)

{ next = current->next;
current->next = prev;
prev = current; current =
next;
}
*head = prev;
}

Question 4: Write a Program to Insert and Delete an Element After a Given

Node in a Singly Linked List
This question requires two functions: one for inserting a node after a specified node and another
for deleting the node after a specified node.

Insertion :

1. Find the specified node after which the new node needs to be inserted. 2.
Create a new node, set its next pointer to the next pointer of the specified node. 3.
Update the next pointer of the specified node to point to the new node.

Deletion :

1. Find the specified node.

2. Check if the specified node has a next node; if not, there's nothing to delete.
3. Save the node to be deleted in a temporary pointer.
4. Update the next pointer of the specified node to skip the node to be deleted.
5. Free the memory of the deleted node.
Code Example in C :
void insertAfter(struct Node* prevNode, int data)
{
if (prevNode == NULL) { printf("Previous
node cannot be NULL\n"); return;
}
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)
{ printf("No node to delete\n"); return;
}
struct Node* temp = prevNode->next;
prevNode->next = temp->next;
free(temp);
}

Each function here provides the essential operations for manipulating linked lists,
essential in various applications such as implementing queues, dynamic memory
structures, and real-time systems where fast insertion and deletion are critical.

Doubly Linked List

1. C/C++ Program to Add Two Polynomials Represented Using Doubly Linked

Lists

Brief Explanation:

A polynomial can be represented using a doubly linked list where each node contains the
coefficient and exponent of a term. To add two polynomials, we traverse both lists
simultaneously, comparing the exponents:

• If the exponents match, add the coefficients.

• If one exponent is greater, move the pointer of the smaller exponent forward. •
Insert the sum result into a new list to represent the result polynomial.
Detailed Explanation:

1. Representation of a Polynomial:
o Each node in the doubly linked list contains the coefficient and exponent of a
polynomial term.
o For example, 3x2+4x+53x^2 + 4x + 53x2+4x+5 would be represented as three
nodes: (3,2),(4,1),(5,0)(3, 2), (4, 1), (5, 0)(3,2),(4,1),(5,0).
o Using a doubly linked list allows us to traverse the list in both forward and
reverse directions, making it versatile.
2. Adding Two Polynomials:
o Initialization: Start with two pointers, each at the head of one of the polynomial
lists. o Comparison: Compare the exponents of the nodes at both pointers.
▪ If exponents are the same, add the coefficients and create a new node with
the sum.
If exponents differ, add the node with the smaller exponent directly to the
▪
result list.
o Traversal: Move the pointer for the processed term to the next node.
o Edge Cases: If one polynomial has more terms than the other, append the
remaining terms to the result.
3. Necessary Functions:
o Insert Node: To add terms to the result list in the correct order. o Display
Polynomial: To print the resulting polynomial in readable form.

C++ Code Example:

#include <iostream>
using namespace std;

struct Node {
int coeff;
int exp;
Node* next;
Node* prev;
};

Node* addTerm(Node* head, int coeff, int exp)

{ Node* newNode = new Node(); newNode-
>coeff = coeff; newNode->exp = exp;
newNode->next = NULL; newNode->prev =
NULL; if (!head) return newNode;

Node* temp = head; while (temp-

>next) temp = temp->next; temp-
>next = newNode; newNode->prev =
temp; return head;
}
Node* addPolynomials(Node* poly1, Node* poly2) { Node*
result = NULL; while (poly1 && poly2) { if (poly1->exp ==
poly2->exp) { result = addTerm(result, poly1->coeff + poly2-
>coeff, poly1->exp); poly1 = poly1->next; poly2 = poly2->next;
} else if (poly1->exp > poly2->exp) { result =
addTerm(result, poly1->coeff, poly1->exp); poly1
= poly1->next;
} else {
result = addTerm(result, poly2->coeff, poly2-
>exp); poly2 = poly2->next;
}
}
while (poly1) { result = addTerm(result, poly1-
>coeff, poly1->exp); poly1 = poly1->next;
}
while (poly2) { result = addTerm(result, poly2-
>coeff, poly2->exp); poly2 = poly2->next;
}
return result;
}

2. Program to Concatenate Two Doubly Linked Lists

Brief Explanation:

Concatenating two doubly linked lists involves linking the last node of the first list to the first
node of the second list. This can be done in constant time if we maintain pointers to the last
node in each list.

Detailed Explanation:

1. Steps for Concatenation:

Check List Head Nodes: If either of the lists is empty, return the other list as the
o
concatenated result. o Traverse to the End of the First List: Start from the
head of the first list and move to its last node.
o Link Last and First Nodes: Set the next pointer of the last node in the first list
to point to the head of the second list. Update the prev pointer of the head of the
second list to point back to the last node of the first list.
2. Edge Cases:
o Empty Lists: If one list is empty, return the other list directly.
o Single-Node Lists: If both lists contain only one node, link them normally as
described.
Code Example:

void concatenate(Node*& head1, Node*& head2)

{ if (!head1) { head1 = head2; return;
}
if (!head2) return;

Node* temp = head1; while (temp-

>next) temp = temp->next;

temp->next = head2; head2-

>prev = temp;
}

3. Advantages of Doubly Linked Lists over Singly Linked

Lists Brief Explanation:

A doubly linked list allows traversal in both directions, providing more flexibility compared to
a singly linked list. Additionally, it allows easy deletion of nodes from both ends, improving the
efficiency of certain operations like reversing and deletion.

Detailed Explanation:

1. Bidirectional Traversal:
o In a doubly linked list, each node contains a pointer to both its next and previous
nodes, allowing traversal in both directions.
o This is particularly useful in applications where both forward and backward
traversal are needed (e.g., in browser history, where users may go backward and
forward).
2. Efficient Node Deletion:
o With a pointer to the previous node, deleting a node is faster and doesn’t require
traversing from the head.
oFor example, if we want to delete the last node, we can reach it directly from the
previous node, while in a singly linked list, we would need to traverse from the
beginning.
3. Improved Insertion and Deletion at Both Ends:
o A doubly linked list allows direct insertion and deletion at both the beginning and
end without needing to traverse the list.
o
For instance, inserting at the end in a singly linked list requires traversal unless a
tail pointer is maintained. In doubly linked lists, insertion and deletion from the
end are O(1) operations.
4. Complexity Comparison:
o Doubly linked lists are slightly more complex to implement due to the extra
pointer but provide flexibility in navigation and operations.
Example Code for Deleting a Node in Doubly Linked List: The function delete(p, &x) deletes
the node pointed by p and updates x with the deleted data.

void deleteNode(Node*& head, Node* p, int& x)

{ if (!p) return;

x = p->data;
if (p->prev) p->prev->next = p-
>next; else head = p->next; if (p-
>next) p->next->prev = p->prev;

delete p;
}

• Parameters:
o p : Node to be deleted. o head : Reference to the head node for
updating if the head node is deleted. o x : Variable to store the data of the
deleted node for further use if required.

Circular Linked List:

1. Advantages of Circular and Doubly Linked Lists over Singly Linked

Lists Circular Linked List Advantages:

1. Continuous Traversal:
o In a circular linked list, the last node points back to the first node. This creates a
loop, allowing continuous traversal of the list.
o
oThis property is particularly useful in applications that require circular or
repetitive access, such as round-robin scheduling in operating systems.
2. Efficient Navigation:
A circular linked list allows for a more efficient setup for applications that cycle
through data continuously. For example, in multiplayer gaming where players
take turns in a loop, a circular list lets us return to the start without additional
checks.
3. No NULL Pointers for End Node:
o Since the last node in a circular linked list points back to the head node instead
of NULL, it avoids issues with null pointers when implementing circular
behavior, reducing the need for extra conditions or checks.
Doubly Linked List Advantages:

1. Bidirectional Traversal:
o In a doubly linked list, each node has both a next and prev pointer, enabling
traversal in both forward and backward directions. o This feature is useful in
applications like browser history navigation, where users may want to go backward
and forward easily.
2. Efficient Deletion of Nodes:
o In a doubly linked list, any node can be deleted without traversing from the head.
Once a node is located, it can be removed directly since it has a prev pointer. o For
instance, deleting the last node in a singly linked list requires traversal from the head,
while in a doubly linked list, it can be done in constant time if we keep a pointer to
the tail node.
3. More Flexible Operations:
o A doubly linked list simplifies certain operations that are challenging in singly
linked lists, like adding or removing elements from both ends. This makes it useful
in data structures that require double-ended functionality, such as deques (double-
ended queues).

2. Algorithms for Operations on Circular Singly Linked List Using Header Node
A circular singly linked list with a header node means the list starts with a dummy or header
node. The header node doesn’t store data but acts as a placeholder, pointing to the start of the
actual data nodes.

Algorithm to Add a Node at the End

1. Initialize New Node: o Create a new node, newNode , with the desired data and set its
next pointer to NULL .
o
2. Check if List is Empty:
o If the header node's next pointer is NULL (indicating an empty list), point the
header’s next to the newNode .
o Also, set newNode->next to the header node, completing the circular link.
3. Traverse to the Last Node:
If the list is not empty, start from the header node and traverse to the last node
(where current->next points back to the header).
4. Insert New Node:
o Set the last node’s next pointer to newNode .
o Set newNode->next to the header node, maintaining the circular structure.
5. End of Algorithm.

Algorithm in Pseudocode:

Function addNodeAtEnd(header, data):

newNode = Create a new Node
newNode.data = data
newNode.next = NULL

If header.next is NULL:
// List is empty
header.next = newNode
newNode.next = header // Link back to header
Else:
current = header.next While
current.next != header:
current = current.next
End While
current.next =
newNode
newNode.next = header // Maintain circular link
End If
End Function

Algorithm to Add a Node at the Beginning

1. Initialize New Node: o Create a new node, newNode , with the desired data.
2. Check if List is Empty:
o If the list is empty (header’s next pointer is NULL), point header->next to newNode
and newNode->next to the header, creating a self-loop.
3. Set New Node’s next :
o If the list is not empty, set newNode->next to point to the node currently following
the header ( header->next ).
o
4. Update Header Node’s Next Pointer: o Point header->next to the newNode , making it
the first node in the list.
5. Traverse to Last Node:
o If the list was not empty, traverse to the last node (where current->next points to the
header).
6. Maintain Circular Link: o Set the last node’s next pointer to newNode to maintain the
circular structure.
7. End of Algorithm.
Algorithm in Pseudocode:

Function addNodeAtBeginning(header, data):

newNode = Create a new Node
newNode.data = data

If header.next is NULL:
// List is empty
header.next = newNode
newNode.next = header // Link back to header
Else:
newNode.next = header.next // Point new node to first node
header.next = newNode // Set header's next to new node
// Traverse to last node
current = newNode.next
While current.next != header:
current = current.next
End While
current.next = newNode // Maintain circular link
End If
End Function

Summary of Both Algorithms:

These algorithms are designed to handle circular singly linked lists using a header node,
making insertions flexible and efficient. The header node enables consistent management of
the list's start and helps avoid special cases when the list is empty or only has one node.
Name :Vishal Rajesh Bhutekar
Roll no :BT24S05F002

ASSIGNEMENT- 4

Tree Datastructure:
1. Discuss following with reference to trees. Tree Ans.
A tree is a hierarchical data structure consisting of nodes connected by
edges. It is acyclic (no cycles) and connected, with a single root node from
which all other nodes descend. Key terms in tree structures include:
• Root: The topmost node.
• Node: An individual element in the tree, which holds data and may have
child nodes.
• Child: A node directly connected to another node (its parent).
• Leaf: A node with no children.
• Parent: A node that has one or more child nodes.
• Subtree: A tree formed by any node and all its descendants.
• Depth: The number of edges from the root to a node.
• Height: The number of edges from a node to its farthest leaf. Types of
Trees:
1. Binary Tree: Each node has at most two children.

2. Binary Search Tree (BST): A binary tree where left child < node < right
child.
3. AVL Tree: A self-balancing binary search tree.

4. Red-Black Tree: A balanced binary search tree with extra properties to

maintain balance.
5. Heap: A binary tree that satisfies the heap property.
6. B-Tree: A balanced tree used in databases for efficient searching.

7. Trie: A tree used for efficient string searching. Tree Traversals:

• Pre-order: Root → Left → Right
• In-order: Left → Root → Right
• Post-order: Left → Right → Root
• Level-order: Level by level (breadth-first).
Common Operations:
• Insertion, Deletion, Search, and Traversal are basic operations on trees.
Applications:
• File systems, expression trees, decision trees, search trees, and
databases.
Example:
A binary tree where each node has at most two children, often used in
searching and sorting algorithms.

2. What are the applications of trees?

Trees are widely used in computer science and various applications due to
their hierarchical structure and efficient performance in organizing and
searching data. Some key applications of trees include:
1. Binary Search Trees (BST): Used for fast searching, insertion, and
deletion in sorted data. Common in dictionaries, autocomplete, and
database indexing.
2. Expression Trees: Represent mathematical expressions in compilers and
calculators, where internal nodes are operators and leaves are operands.
3. File Systems: Organize directories and files hierarchically in systems like
Unix, Linux, and Windows.
4. Database Indexing (B-trees): Enhance search efficiency in databases for
quick retrieval and storage.
5. Decision Trees: Used in machine learning for classification and
decisionmaking tasks.
6. Huffman Coding Trees: Applied in data compression algorithms like ZIP
and JPEG.
7. Routing Tables: Used in network protocols for efficient IP address lookup
and routing in networks.
8. Hierarchical Data Representation: Model structures like organizational
charts, family trees, and category hierarchies.
9. Priority Queues (Heap Trees): Implement priority queues for scheduling
tasks, such as in job scheduling and Dijkstra's algorithm.
10.Parsing Trees: Used in compilers to represent the syntactic structure of
source code.
11.Game Trees: Model possible moves in strategy games, supporting AI
decision-making (e.g., in chess).
12.Social Networks: Represent relationships and connections in social media
platforms.
Trees are fundamental for tasks requiring hierarchical relationships and
efficient data retrieval or management

3. Construct a tree for the given inorder and postorder traversals Inorder
DGBAHEICF Postorder GDBHIEFCA
Ans. To construct a tree from inorder and postorder traversals, follow these
steps:
1. Identify the root: The last element of the postorder sequence is always the
root. For this problem, the root is A (last in postorder).
2. Split inorder sequence: Use the root to divide the inorder sequence into the
left and right subtrees: o Left subtree (elements before the root in inorder):
DGBo
Right subtree (elements after the root in inorder): H E I C F
3. Split postorder sequence: Exclude the root, and the remaining postorder
sequence will be divided between the left and right subtrees: o Left subtree
(postorder for left subtree): G D B o Right subtree
(postorder for right subtree): H I E F C 4. Recursively
construct subtrees:
For the left subtree, the root is B (from postorder), with left
o

child G and right

child D.
For the right subtree, the root is C (from postorder), with left
o

child E (which has children H and I) and right child F. Final Tree:
A
/ \
B C
/\ /\
G D E F
/\
H I
This is the tree constructed from the given inorder and postorder traversals.
4. Give the preorder and Inorder traversal of the tree given in below fig.

Ans.
To find the preorder and inorder traversal of this binary tree, let's analyze the
structure based on the image. Tree Structure
The tree appears as follows:
F
/ \
B G
/\ \
A D I
/\ /
C E H
Traversal Definitions
• Preorder Traversal (Root, Left, Right): Visit the root node first, then
recursively visit the left subtree, followed by the right subtree.
• Inorder Traversal (Left, Root, Right): Recursively visit the left subtree
first, then visit the root node, followed by the right subtree. Preorder
Traversal
1. Start at F
2. Move to B
3. Move to A
4. Move to D
5. Move to C
6. Move to E
7. Move to G
8. Move to I
9. Move to H
Preorder Traversal: F, B, A, D, C, E, G, I, H
Inorder Traversal
1. Start at the leftmost node A
2. Move up to B
3. Move to C
4. Move up to D
5. Move to E
6. Move up to F
7. Move to G
8. Move to H
9. Move up to I
Inorder Traversal: A, B, C, D, E, F, G, H, I
Final Answer
• Preorder Traversal: F, B, A, D, C, E, G, I, H
• Inorder Traversal: A, B, C, D, E, F, G, H, I

5. Construct binary search tree for the following data Find its
inorder, preorder and postorder traversal
1. 10,3,15,22,6,45,65,23,78,34,5.
➔ 10
/\
3 15
\ \
6 22
/ \
5 45
/\
23 65
\ \
34 78

2.50, 60, 25, 40, 30, 70, 35, 10, 55, 65, 5

➔ 50
/\
25 60
/\ /\
10 40 55 70
/ / /
5 30 65
\
35

3. 40, 65,25, 55, 10,70,30,50,15,80,75

➔ 40
/ \
25 65
/ \ / \
10 30 55 70
\ / \
15 50 80
/
75
5. 45,56,39,12,34,78,54,67,10,32,89,81

➔ 45
/ \
39 56
/ / \
12 54 78
/ \ / \
10 34 67 89
5. 60, 15, 4, 30, 70, 65, 10, 95, 25, 34 Find its inorder, preorder and
postorder traversal
➔ Inorder Traversal : 4, 10, 15, 25, 30, 34, 60, 65, 70, 95
Preorder Traversal : 60, 15, 4, 10, 30, 25, 34, 70, 65, 95 Postorder
Traversal: 10, 4, 25, 34, 30, 15, 65, 95, 70, 60

6. Write an algorithm to perform traversal of Binary search tree

Ans.
Here's an algorithm to perform the three primary types of traversals for a
Binary Search Tree (BST): Preorder, Inorder, and Postorder. These are
DepthFirst Search (DFS) traversal methods.
Algorithm for Traversal of a Binary Search Tree Assume each
node has three components:
• node.value: the value of the node
• node.left: pointer to the left child
• node.right: pointer to the right child
Let’s define recursive algorithms for each traversal type.
1. Preorder Traversal (Root, Left, Right)
In Preorder traversal, we visit the root node first, then recursively traverse the
left subtree, and finally the right subtree. Steps:
1. Visit the root node.
2. Recursively perform Preorder traversal on the left subtree.
3. Recursively perform Preorder traversal on the right subtree.

2. Inorder Traversal (Left, Root, Right)

In Inorder traversal, we recursively traverse the left subtree, visit the root node,
and then recursively traverse the right subtree
Here's an algorithm to perform the three primary types of traversals for a
Binary Search Tree (BST): Preorder, Inorder, and Postorder. These are
DepthFirst Search (DFS) traversal methods. Steps:
1. Recursively perform Inorder traversal on the left subtree.
2. Visit the root node.
3. Recursively perform Inorder traversal on the right subtree.
Note: Inorder traversal of a BST gives nodes in ascending order.

3. Postorder Traversal (Left, Right, Root)

In Postorder traversal, we recursively traverse the left subtree, then the right
subtree, and finally visit the root node.
Here's an algorithm to perform the three primary types of traversals for a
Binary Search Tree (BST): Preorder, Inorder, and Postorder. These are
DepthFirst Search (DFS) traversal methods. Steps:
1. Recursively perform Postorder traversal on the left subtree.
2. Recursively perform Postorder traversal on the right subtree.
3. Visit the root node.

7. First insert 10 and then insert 24. After these insertions, delete 37 and then
delete 22 from the following binary search tree. Draw the tree after each
operation.

Step 1: Insert 10
• Inserted 10 as the right child of 9. Tree
after Inserting 10

14
/ \
9 26
/\ /
7 10 22 37
\ \
17 40
\
20

Step 2: Insert 24 •
Inserted 24 as the right child of 22.

14
/ \
9 26
/\ / \
7 10 22 37
\ \
17 40
\
20
\
24

Step 3: Delete 37
• Replaced 37 with its only child, 40.
14
/ \
9 26
/\ / \
7 10 22 40
\
17
\
20
\
24

Step 4: Delete 22 • Replaced 22 with its in-order successor, 24, and removed
the original 24.

14
/ \
9 26
/\ / \
7 10 24 40
\
17
\
20

8. Answer the following

1.The height of a binary tree is the maximum number of edges in any
root to leaf path. Define the maximum number of nodes in a binary tree
of height h.
2.Consider a B-tree in which the maximum number of keys in a node is
What is the minimum number of keys in any non-root node?

1. Maximum Number of Nodes in a Binary Tree of Height h

In a binary tree of height h, where height is defined as the maximum number
of edges in any root-to-leaf path:
• The maximum number of nodes in a binary tree of height h is given by the
formula: 2(h+1)−1 Explanation:
• At height 0, there is 1 node (the root).
• At height 1, there can be up to 2 nodes in the second level, totaling
2^2−1=3 nodes.
• At height h, the maximum number of nodes is the sum of all nodes from the
root to the h-th level, which leads to the formula 2(h+1)−1.
2. Minimum Number of Keys in Any Non-Root Node of a B-Tree In a B-
tree, the minimum number of keys in any non-root node is determined by the
order of the tree, usually denoted as t (the minimum degree of the Btree).
• For a B-tree of minimum degree t:
o Each non-root node must have at least t−1keys.
o The maximum number of keys a node can have is 2t−1. o This

ensures that each node is at least half-full.

So, the minimum number of keys in any non-root node

Graph:

1.Consider the graph shown in below figure. Find depth-first and breadth
first traversals of this graph starting at A

Ans. To find the depth-first and breadth-first traversals of the graph starting at
node A, let's examine the graph structure in the image:
The graph structure based on the image seems to be:
• A is connected to B, C, and D.
• C is connected to E and F.
Given this structure, we can determine the traversals as follows:
Depth-First Traversal (DFS) Starting from A
In DFS, we explore as far as possible along each branch before backtracking.
1. Start at A.
2. Move to B.
3. Backtrack to A and move to C.
4. From C, move to E.
5. Backtrack to C and move to F.
6. Backtrack to C, then back to A, and finally move to D.
DFS Traversal: A→B→C→E→F→D
Breadth-First Traversal (BFS) Starting from A
In BFS, we explore all neighbors at the present depth before moving on to nodes
at the next depth level.
1. Start at A.
2. Visit A's neighbors: B, C, and D.
3. Move to C's neighbors (since B and D have no other connections): E and F.
BFS Traversal: A→B→C→D→E→F
These are the DFS and BFS traversals starting from node A.

2. Define spanning tree and minimum spanning tree. Find the minimum
spanning tree of the graph shown in figure.

Ans. Spanning Tree: A spanning tree of a graph is a subgraph that includes all
the vertices of the original graph and is a tree (i.e., it has no cycles). It connects
all the vertices with the minimum number of edges needed to keep the graph
connected.8+5`
Minimum Spanning Tree (MST): A minimum spanning tree is a spanning tree
with the smallest possible total edge weight. It is a subgraph that connects all
vertices in the graph with the minimum sum of edge weights, ensuring no cycles.
MST of the Graph
Using Kruskal’s Algorithm:
• Edges in MST: C−D (1), B−C (2), A−B (4), A−E (5)
• Total Weight: 1+2+4+5=12
MST Weight: 12

3. Explain the breadth first search and depth first search tree traversal on the
following graph.

c
Ans. BFS Traversal: A → B → C → D → E → F → G DFS
Traversal: A → B → D → E → C → F → G

4..Answer the following for the below given Graph.

1. What is the outdegree of node B.

➔2
2. Write down a path from node D to node A.

➔ D→E→A
3. Is the above graph a multigraph? Give a reason for your answer.

➔yes
4. What is the total degree of node A.
➔3

6.Obtain the adjacency matrix A for the following graph. Find A2. Find
outdegree of E and D nodes.

Ans. A B C D E
A 0 1 1 1 0
B 1 0 0 1 1
C 1 0 0 1 0
D 1 1 1 0 1
E 0 1 0 1 0
Outdegree of E node :- 2
Outdegree of D node :- 2