DATA STRUCTURES

PART I

ANSWER ANY 10 QUESTION

1. Define Data structure.
A data structure is a way of organizing and storing data in a computer so that it can be
accessed and used efficiently. Data structures are used in almost every program or software
system. They are used to store and organize data in a way that makes it easy to access and
manipulate. Some common examples of data structures include arrays, linked lists, stacks,
queues, trees, graphs, and hash tables

2. List the operations performed in the Linear Data Structure.

The various operations performed on linear data structures are:
 Traversal: The process of accessing each data item exactly once to perform some
operation.
 Insertion: The process of adding a new data item into the given collection of data
neats.
 Deletion: The process of removing existing data item from the given collection of
data neats.
 Searching: The process of finding the location of a given data item in the given
collection of data neats.
 Sorting: The process of arranging the data items in some order.

3. Whatis abstract data type?

An abstract data type (ADT) is a high-level description of a set of values and the operations
that can be performed on those values. It is defined as a mathematical model of the data
objects that make up a data type as well as the functions that operate on these objects. The
definition of ADT only mentions what operations are to be performed but not how these
operations will be implemented

4. Define Array.
An array is a data structure consisting of a collection of elements (values or variables), each
identified by at least one array index or key. An array is stored such that the position of each
element can be computed from its index tuple by a mathematical formula. An array is a linear
data structure that stores elements of the same data type together in contiguous memory
locations.

5. Write the limitations of Array.

Arrays have a fixed size that is determined at the time of creation 1. This means that if the size
of the array is not known beforehand, it may not be possible to use an array.
Allocating a large array can be problematic, particularly in systems with limited memory. If
an array is too large, it may not be possible to allocate enough memory for it. Insertion and
deletion of elements in an array can be difficult and time-consuming

6. What are the ways to represent the two dimensional Array in memory.
There are two ways to represent a two-dimensional array in memory: row-major and column-
major. A 2D array has a type such as int[][] or String[][], with two pairs of square
brackets. The elements of a 2D array are arranged in rows and columns, and the new operator
for 2D arrays specifies both the number of rows and the number of columns1.
In row-major order, the elements of each row are stored together in memory. In other words,
all the elements of the first row are stored first, followed by all the elements of the second
row, and so on. This is the default way that Java stores 2D arrays1.
In column-major order, the elements of each column are stored together in memory. In other
words, all the elements of the first column are stored first, followed by all the elements of the
second column, and so on

7. Calculate the address of the element a[2][4] of an array a[3][5] in row major order.
To calculate the address of the element a[2][4] of an array a[3][5] in row major order, we can
use the following formula:
Address of A [i] [j] = B + W * ((i * N) + j)
Where, B is the base address of the array. W is the size of each element in bytes. N is the
number of columns in the array.
In this case, we have: B = address of a[0][0] W = size of each element in bytes N = 5
So, to find the address of a[2][4], we have: Address of A 2 [4] = B + W * ((2 * 5) + 4) = B +
W * (14)

8. What are structures in c?

In C programming, a struct (or structure) is a collection of variables (can be of different
types) under a single name. You can define a struct using the struct keyword. The syntax for
defining a struct is as follows:

struct structureName
{
dataType member1;
dataType member2;
...
};

Here, structureName is the name of the structure and member1, member2, etc. are the

members of the structure. You can access these members using the dot operator (.).
Structures are used to represent a record. For example, you can use a structure to represent an
employee record that contains information such as name, age, salary, etc. You can then create
variables of this structure type to store information about different employees

9. Define Stack.
A stack is a linear data structure in which the insertion of a new element and removal of an
existing element takes place at the same end represented as the top of the stack. A stack has
only one end, whereas a queue has two ends (front and rear). It contains only one pointer top
pointer pointing to the topmost element of the stack.

10. What are the operations allowed in stack?

The following are some common operations implemented on the stack:
 push (): When we insert an element in a stack then the operation is known as a push.
If the stack is full then the operation is said to be an overflow condition.
 pop (): When we delete an element from the stack, the operation is known as a pop. If
the stack is empty means that there are no elements to delete, then it is said to be an
underflow condition.
11. List the notations used to represent the arithmetic expression?
Arithmetic expressions can be written in 3 different notations - infix, prefix, and postfix 1.
Infix notation is the most common notation used to represent arithmetic expressions. In this
notation, each operator is written between two operands (i.e., A + B)

12. Write the rules for converting an Infix notation to Postfix form.
To convert infix notation to postfix notation, we use the stack data structure. Here are the
rules for conversion123:
1. Start scanning from left to right.
2. If there is an operand, store it into the output string.
3. If there is an operator, push it onto the stack.
4. If there is a left parenthesis, push it onto the stack.
5. If there is a right parenthesis, pop operators from the stack and add them to the output
string until you reach the left parenthesis.
6. If there is an operator with higher precedence than the top of the stack, push it onto
the stack.
7. If there is an operator with lower or equal precedence than the top of the stack, pop
operators from the stack and add them to the output string until you reach an operator
with lower precedence or a left parenthesis.
8. Repeat steps 2-7 until you have scanned all characters in the infix expression.
9. Pop any remaining operators from the stack and add them to the output string.

13. Write any four applications of stack.

Stacks are used in many applications such as expression evaluation, backtracking, recursion
and the implementation of other data structures such as queues 1. Here are some of the most
common uses of a stack234:
 To reverse a word - Put all the letters in a stack and pop them out. Because of the
LIFO order of stack, you will get the letters in reverse order.
 Function calls and recursion - When a function is called, the current state of the
program is pushed onto the stack. When the function returns, the state is popped off
the stack and execution continues from where it left off.
 Undo/Redo operations - The undo-redo feature in various applications uses stacks to
keep track of the previous actions.
 Expression evaluation - A stack is a very effective data structure for evaluating
arithmetic expressions in programming languages.

14. Define queue.

A queue is a linear data structure that follows the First In First Out (FIFO) principle. It has
two main operations: enqueue (insertion) and dequeue (deletion). The enqueue operation adds
an element to the rear of the queue while the dequeue operation removes an element from the
front of the queue.

15. Mention some applications of queue.

Queues are used in many applications such as simulations, operating systems, and computer
networks. Here are some of the most common uses of a queue:
 Printers - When multiple print jobs are sent to a printer, they are stored in a queue and
printed in the order they were received.
 Operating systems - In an operating system, processes are stored in a queue and
executed in the order they were received.
  Computer networks - In computer networks, packets are stored in a queue and
transmitted in the order they were received.

16. Whatis priority queue?

A priority queue is a type of queue that arranges elements based on their priority values.
Elements with higher priority values are typically retrieved before elements with lower
priority values. In a priority queue, each element has a priority value associated with it

17. Define circular queue.

A circular queue is an extended version of a normal queue where the last element of the
queue is connected to the first element of the queue forming a circle. The operations are
performed based on FIFO (First In First Out) principle. It is also called ‘Ring Buffer’

PART IA

UNIVERSITY EXAM QUESTION PATTERN– 6 MARK (EACH QUESTIONCARRIES 6

MARKS)
ANSWER ALLQUESTION
1. Explain in detail about Arrays?
n array is a data structure that stores a collection of elements of the same type. It is stored in
contiguous memory locations. Each element in an array is identified by an index or a
key. The index starts from 0 and goes up to n-1 where n is the number of elements in the
array.
int arr[5] = {1, 2, 3, 4, 5};
This creates an array called arr with 5 elements. The first element is 1, the second element
is 2, and so on. You can access each element of the array using its index. For example, to
access the first element of the array, you would use arr[0].
Arrays are used in many applications in computer programming. Here are some examples:
 Arrays can be used to implement stack and queue data structures1.
 Arrays are good to implement Vectors and Lists1.
 CPU scheduling algorithm can be implemented using an array1.
 Arrays play an important role in the implementation of other data structures like
linked lists2.
 Database records are usually implemented as arrays2.
 Trees also use array implementation whenever possible as arrays are easy to handle
compared to pointers

2. Discuss in detail about structures in c.

In C programming, a structure is a user-defined data type that can be used to group items of
possibly different types into a single type. The struct keyword is used to define the structure
in the C programming language. The items in the structure are called its member and they can
be of any valid data type1.
Structures are used for the following:
 The structure can be used to define the custom data types that can be used to create
some complex data types such as… It can also be used in data organization where a
large amount of data can be stored in different fields.
 Structures are used to create data types that can be used to store a collection of related
data.
  Structures are used to create records which are used to store information about
something in particular

3. What is a Stack? Explain its operations with example.

In C programming, a stack is a linear data structure that follows the LIFO (Last In First Out)
approach to perform a series of basic operations like push, pop, peek, and traverse. A Stack
can be implemented using an Array or Linked List1.
Here is an example of how a stack works:
 Push: Adds an item in the stack. If the stack is full, then it is said to be an Overflow
condition.
 Pop: Removes an item from the stack. The items are popped in the reversed order in
which they are pushed. If the stack is empty, then it is said to be an Underflow
condition.
 Peek or Top: Returns the top element of the stack.
 isEmpty: Returns true if the stack is empty, else false.
 isFull: Returns true if the stack is full, else false

4. Write the algorithm for converting infix expression to postfix expression.

Here is an algorithm to convert infix expression to postfix expression:
1. Scan the infix expression from left to right.
2. If the scanned character is an operand, output it.
3. Else,
4. If the precedence of the scanned operator is greater than the precedence of the
operator in the stack (or the stack is empty or the stack contains a left parenthesis on
top), push it.
5. Else, Pop all the operators from the stack which are greater than or equal to in
precedence than that of the scanned operator. After doing that Push the scanned
operator to the stack. (If you encounter parenthesis while popping then stop there and
push the scanned operator in the stack.)
6. If the scanned character is an ‘(’, push it to the stack.
7. If the scanned character is an ‘)’, pop and output from the stack until an ‘(’ is
encountered.
8. Repeat steps 2-6 until infix expression is scanned.
9. Pop and output from the stack until it is not empty

5. What is a Queue? Explain its operations with example.

A queue is a linear data structure that follows the First In First Out (FIFO) rule - the item that
goes in first is the item that comes out first. It is similar to the ticket queue outside a cinema
hall, where the first person entering the queue is the first person who gets the ticket1.
A queue has two main operations:
 Enqueue: Adds an item to the queue. Addition of an item to the queue is always done
at the rear of the queue.
 Dequeue: Removes an item from the queue. An item is removed or de-queued always
from the front of the queue2.
For example, consider a line of people waiting for their turn at a ticket counter. The person
who comes first will get their ticket first and leave first. Similarly, in programming, when we
use a queue data structure, we can add elements to it and remove them in a FIFO manner
6. Explain any two applications of stack.
Stacks are used in many applications such as expression evaluation, backtracking, recursion
and the implementation of other data structures such as queues 1. Here are two examples of
how stacks are used:
 Function calls and recursion: When a function is called, the current state of the
program is pushed onto the stack. When the function returns, the state is popped off
the stack and execution resumes from where it left off2.
 Undo/Redo operations: The undo-redo feature in various applications uses stacks to
keep track of the previous actions. Expression evaluation is also done using stacks

7. Explain the Linear linked Implementation of Stack and Queue.

A linear linked implementation of a stack or queue is a way to implement these data
structures using a linked list. In this implementation, we use a singly linked list where each
node contains two fields: data and next. The data field stores the value of the element and
the next field stores the address of the next node in the list.
In a stack, we add elements to the top of the stack and remove elements from the top of the
stack. In a linear linked implementation of a stack, we add elements to the head of the linked
list and remove elements from the head of the linked list.
In a queue, we add elements to the rear of the queue and remove elements from the front of
the queue. In a linear linked implementation of a queue, we add elements to the rear of the
linked list and remove elements from the head of the linked list.

8. Explain the Insertion and Deletion algorithm for Circular linked List.
In a circular linked list, the last node of the list points to the first node of the list instead of
pointing to null. This makes it easier to traverse the list in a circular manner.
The insertion and deletion algorithms for a circular linked list are similar to those for a singly
linked list. Here are the algorithms for insertion and deletion in a circular linked list:
 Insertion: To insert an element into a circular linked list, we first create a new node
with the given data. If the list is empty, we set the new node as the head of the list and
point its next field to itself. If the list is not empty, we traverse the list until we reach
the last node. We then set the next field of the last node to point to the new node and
set the next field of the new node to point to the head of the list.
 Deletion: To delete an element from a circular linked list, we first find the node that
contains the element. We then set the next field of the previous node to point to the
next node of the current node. If we are deleting the head of the list, we set the head
of the list to point to its next field.

9. Explain the operations of Priority Queue.

A priority queue is a data structure that stores elements with priorities. The priority of an
element determines the order in which it will be processed. The element with the highest
priority is processed first.
A priority queue must at least support the following operations1:
 is_empty: check whether the queue has no elements.
 insert_with_priority with an associated priority.
 pull_highest_priority_element: remove the element from the queue that has the
highest priority, and return it.
In addition to these basic operations, some priority queues may support other operations such
as changing the priority of an element or deleting an element from the queue
10. Write the algorithm to merge any two Linked list.
Here is an algorithm to merge two linked lists:
1. Create a new linked list that will contain the merged elements.
2. Traverse both linked lists simultaneously.
3. Compare the values of the current nodes of both linked lists.
4. If the value of the current node in the first linked list is less than or equal to the value
of the current node in the second linked list, add the current node from the first linked
list to the new linked list and move to the next node in the first linked list.
5. If the value of the current node in the second linked list is less than the value of the
current node in the first linked list, add the current node from the second linked list to
the new linked list and move to the next node in the second linked list.
6. If one of the linked lists becomes empty, add all remaining nodes from the other
linked list to the new linked list.
7. Return the head of the new merged linked list.

PART II

UNIVERSITY EXAM QUESTION PATTERN– 6 MARK (EACH QUESTIONCARRIES 2

MARKS)

ANSWER ANY 10QUESTION

1. What is the purpose of nonlinear data structures?
Non-linear data structures are used to represent data that contains a hierarchical relationship
among its elements1. Unlike linear data structures, non-linear data structures do not store data
elements sequentially or linearly. Instead, data elements are arranged in random order without
forming a linear structure2. Examples of non-linear data structures include trees and
graphs3. Non-linear data structures are used to optimize memory usage

2. What is binary tree?

A binary tree is a tree data structure in which each node has at most two children 1. Each node
of a binary tree consists of three items: data item, address of left child and address of right
child2. A binary tree is represented by a pointer to the topmost node (commonly known as the
“root”) of the tree

3. What is mean by siblings?

Nodes that have the same parent node are called siblings 1. In a binary tree, each node has at
most two children. If a node has two children, then the children are referred to as left child
and right child2. If a node has only one child, then the child is either left or right

4. What are ancestors and descendants?

In a binary tree, an ancestor of a node is any node that is on the path from the root node to
that node. A descendant of a node is any node that is on the path from that node to a leaf
node.

5. What is strictly binary tree (or) full binary tree?

A strictly binary tree (or) full binary tree is a binary tree in which each node has either zero or
two children. In other words, a binary tree is called a full binary tree if every node has 0 or 2
children.
6. What do you mean by complete binary tree?
A complete binary tree is a binary tree in which all levels except possibly the last are
completely filled, and all nodes are as far left as possible. In other words, a complete binary
tree is a binary tree in which every level, except possibly the last, is completely filled, and all
nodes in the last level are as far left as possible.

7. Define almost complete binary tree?

An almost complete binary tree is a binary tree in which all levels except possibly the last are
completely filled, and all nodes are as far left as possible. In other words, an almost complete
binary tree is a binary tree in which every level, except possibly the last, is completely filled,
and all nodes in the last level are as far left as possible.

8. What are the different representations of nodes in a tree?

There are different ways to represent nodes in a tree. Some of the common representations
are:
 Parent pointer representation
 Left-child right-sibling representation
 Array representation
 Linked list representation

9. Give various implementations of binary tree?

There are different ways to implement a binary tree. Some of the common implementations
are:
 Array implementation
 Linked list implementation
 Dynamic memory allocation

10. What are the advantages of binary tree linked representation over array representation?
The linked list representation of binary trees has several advantages over the array
representation:
1. Dynamic size: Linked lists can grow or shrink dynamically as needed, whereas arrays
have a fixed size.
2. Ease of insertion/deletion: Inserting or deleting a node in a linked list is easier than in
an array because it does not require shifting elements.
3. Ease in randomly accessing a node: In a linked list, accessing an element at a random
position requires traversing the list from the beginning, whereas in an array it can be
done in constant time.
4. Both dynamic size and ease in insertion/deletion.

11. What do you mean by External nodes and internal nodes?

In a binary tree, an internal node is a node that has at least one child node. In contrast, an
external node (also called a leaf node) is a node that has no children

12. What is an expression tree?

An expression tree is a binary tree in which each internal node corresponds to an operator and
each leaf node corresponds to an operand. The tree is used to represent expressions in a way
that can be easily evaluated. The inorder traversal of the expression tree produces the infix
version of the given postfix expression (and the postorder traversal gives the postfix
expression)
13. What is a almost complete binary tree?
An almost complete binary tree is a binary tree in which all levels except possibly the last are
completely filled and all nodes are as far left as possible.

14. How almost complete binary tree nodes can be numbered?

In an almost complete binary tree, the nodes can be numbered starting from the root node as
follows:
1. The root node is assigned the number 1.
2. The left child of a node with number i is assigned the number 2i.
3. The right child of a node with number i is assigned the number 2i + 1.

PART IIA

UNIVERSITY EXAM QUESTION PATTERN– 6 MARK (EACH QUESTIONCARRIES 6

MARKS)

ANSWER ALLQUESTION
1. Explain various tree traversal algorithms with implementation.
There are two types of tree traversal algorithms: Depth-First Search (DFS) and Breadth-First
Search (BFS). DFS is further classified into three categories: Preorder Traversal, Inorder
Traversal, and Postorder Traversal1.
Here’s an implementation of the Preorder Traversal algorithm in Python:

class Node:
def __init__(self, value):
self.left = None
self.right = None
self.value = value

def preorder(node):
if node is not None:
print(node.value)
preorder(node.left)
preorder(node.right)

root = Node(1)
root.left = Node(2)
root.right = Node(3)
root.left.left = Node(4)
root.left.right = Node(5)

preorder(root)

Here’s an implementation of the Inorder Traversal algorithm in Python:

class Node:
def __init__(self, value):
self.left = None
 self.right = None
self.value = value

def inorder(node):
if node is not None:
inorder(node.left)
print(node.value)
inorder(node.right)

root = Node(1)
root.left = Node(2)
root.right = Node(3)
root.left.left = Node(4)
root.left.right = Node(5)

inorder(root)

Here’s an implementation of the Postorder Traversal algorithm in Python:

class Node:
def __init__(self, value):
self.left = None
self.right = None
self.value = value

def postorder(node):
if node is not None:
postorder(node.left)
postorder(node.right)
print(node.value)

root = Node(1)
root.left = Node(2)
root.right = Node(3)
root.left.left = Node(4)
root.left.right = Node(5)

postorder(root)

2. Explain binary search tree ADT in detail.

A Binary Search Tree (BST) is a binary tree with an ordering property of its elements, such
that the data in any internal node is greater than the data in any node in its left subtree and
less than the data in any node in its right subtree1.
The following are the basic operations that can be performed on a BST:
 Insertion: To insert a new element into the tree.
 Deletion: To delete an element from the tree.
 Traversal: To visit all nodes of the tree in a particular order.
 Search: To search for an element in the tree.
class Node:
def __init__(self, value):
self.left = None
self.right = None
self.value = value

class BinarySearchTree:
def __init__(self):
self.root = None

def insert(self, value):

if self.root is None:
self.root = Node(value)
else:
self._insert(value, self.root)
def _insert(self, value, current_node):
if value < current_node.value:
if current_node.left is None:
current_node.left = Node(value)
else:
self._insert(value, current_node.left)
elif value > current_node.value:
if current_node.right is None:
current_node.right = Node(value)
else:
self._insert(value, current_node.right)
else:
print("Value already exists in tree.")

def search(self, value):

if self.root is None:
return False
else:
return self._search(value, self.root)

def _search(self, value, current_node):

if value == current_node.value:
return True
elif value < current_node.value and current_node.left is not None:
return self._search(value, current_node.left)
elif value > current_node.value and current_node.right is not None:
return self._search(value, current_node.right)
return False

def inorder_traversal(self):
if self.root is not None:
self._inorder_traversal(self.root)

def _inorder_traversal(self, current_node):

if current_node is not None:
 self._inorder_traversal(current_node.left)
print(current_node.value)
self._inorder_traversal(current_node.right)

bst = BinarySearchTree()
bst.insert(5)
bst.insert(3)
bst.insert(7)
bst.insert(1)
bst.insert(9)

print(bst.search(3))
print(bst.search(10))

bst.inorder_traversal()

3. Write down an algorithm to find the max and smallest element in a tree structure.
To find the smallest element in a binary tree, we can traverse the left subtree of the root node
until we reach a leaf node. The value of that leaf node will be the smallest element in the
tree. Similarly, to find the largest element, we can traverse the right subtree of the root node
until we reach a leaf node. The value of that leaf node will be the largest element in the tree1.

Here is an algorithm in C programming to find the minimum and maximum element in a

binary search tree. The algorithm uses recursive functions to traverse the tree and find the
minimum and maximum elements.

struct node *Min (struct node *ptr)

{
if (ptr==NULL) return NULL;
else if (ptr->lchild==NULL) return ptr;
else return Min (ptr->lchild);
}

struct node *Max (struct node *ptr)

{
if (ptr==NULL) return NULL;
else if (ptr->rchild==NULL) return ptr;
else return Max (ptr->rchild);
}

This algorithm is used to find the minimum and maximum elements in a binary search tree.
The function Min finds the minimum element by recursively traversing the left subtree of the
root node until it reaches the leftmost leaf node. Similarly, the function Max finds the
maximum element by recursively traversing the right subtree of the root node until it reaches
the rightmost leaf node.

4. Write a non-recursive and recursive algorithm for in order tree traversal

Here are two algorithms for in-order tree traversal:

1. Non-recursive algorithm using a stack:

void inorderTraversal(struct node *root)

{
struct node *stack[100];
int top = -1;
struct node *current = root;
while (current != NULL || top != -1)
{
while (current != NULL)
{
stack[++top] = current;
current = current->left;
}
current = stack[top--];
printf("%d ", current->data);
current = current->right;
}
}

2. Recursive algorithm:

void inorderTraversal(struct node *root)

{
if (root != NULL)
{
inorderTraversal(root->left);
printf("%d ", root->data);
inorderTraversal(root->right);
}
}

The non-recursive algorithm uses a stack to traverse the tree. It starts with the root node and
traverses the left subtree until it reaches the leftmost leaf node. It then pops the nodes from
the stack and prints their values. Finally, it traverses the right subtree.
The recursive algorithm is simpler and more intuitive. It traverses the left subtree recursively,
then prints the value of the root node, and finally traverses the right subtree recursively.

5. Explain how arithmetic expressions are manipulated using binary trees. Illustrate with
example.
Arithmetic expressions can be represented using binary trees called expression trees. In an
expression tree, each leaf node represents an operand (such as a number or variable), and
each internal node represents an operator (such as addition or multiplication). The root of the
tree represents the entire expression. Here’s an example of how to create an expression tree
for the arithmetic expression “2 * (3 + 4)”
*
/\
2 +
/\
3 4
To evaluate this expression, we traverse the tree in post-order (left subtree, right subtree,
root) and perform the corresponding operation at each internal node. In this case, we would
first evaluate the left subtree (3 + 4), then multiply the result by 2.

6. What are the applications of tree? Explain with example.

Trees have many applications in computer science. Here are some examples:
 File systems: The file system of a computer is often represented as a tree. Each folder
or directory is a node in the tree, and each file is a leaf node.
 XML parsing: Trees are used to parse and process XML documents. An XML
document can be thought of as a tree, with the root element at the top and child
elements branching off from it.
 Database indexing: Many databases use tree data structures for indexing. This allows
for fast searching and sorting of data.
 Decision-based algorithms in machine learning: Decision trees are used in machine
learning to model decisions and their possible consequences.
 Game development: Trees are used in several games like moves in chess.

7. Discuss how the code could be inserted in a binary tree.

To insert a node into a binary tree, you first need to find the appropriate location for the new
node. You can do this by traversing the tree using either depth-first search (DFS) or breadth-
first search (BFS). Once you find the appropriate location, you can insert the new node as a
child of the parent node.

Here is an example of how to insert a node into a binary tree using Python:

class Node:
def __init__(self, val):
self.left = None
self.right = None
self.val = val

def insert(root, val):

if root is None:
return Node(val)
else:
if root.val < val:
root.right = insert(root.right, val)
else:
root.left = insert(root.left, val)
return root

This code defines a Node class with left, right, and val attributes. The insert function takes

a root node and a value to insert. If the root is None, it creates a new node with the given
value. Otherwise, it compares the value to the root value and inserts it as either the left or
right child of the root.

8. Write a procedure in C to find the Kth element in binary tee.

Here is an example of how to find the kth element in a binary tree using C:
struct Node
{
int data;
struct Node* left;
struct Node* right;
};

void kthSmallestUtil(struct Node* root, int k, int& count)

{
if (root == NULL || count >= k)
return;

kthSmallestUtil(root->left, k, count);

count++;

if (count == k)
{
printf("%d", root->data);
return;
}

kthSmallestUtil(root->right, k, count);
}

void kthSmallest(struct Node* root, int k)

{
int count = 0;
kthSmallestUtil(root, k, count);
}

This code defines a Node struct with data, left, and right attributes.

The kthSmallestUtil function takes a root node, an integer k, and a reference to an
integer count. It recursively traverses the tree using an in-order traversal until it finds the kth
smallest element. The kthSmallest function initializes the count variable and calls
the kthSmallestUtil function.

PART III

UNIVERSITY EXAM QUESTION PATTERN– 6 MARK (EACH QUESTIONCARRIES 2

MARKS)

ANSWER ANY 10QUESTION

1. Define B tree.
A B-tree is a self-balancing tree data structure that maintains sorted data and allows searches,
sequential access, insertions, and deletions in logarithmic time. It is a generalized form of a
binary search tree. Unlike traditional binary search trees, B-Trees are characterized by the
large number of keys that they can store in a single node, which is why they are also known
as “large key” trees

2. Define sentinel.
In data structures, a sentinel is a special value that is used to indicate the end of a list or array.
It is used to simplify the code for operations that traverse the list or array. For example, when
traversing a linked list, a sentinel can be used to indicate the end of the list instead of
checking for null pointers.

3. Define a heap. How can it be used to represent a priority queue?

A heap is a tree-based data structure that satisfies the heap property. The heap property states
that for every node i in the heap, the value of the node is greater than or equal to the value of
its parent1. A priority queue is an abstract data type that is similar to a queue but with each
element having a priority level. Elements with higher priority are dequeued first2. A heap can
be used to implement a priority queue by storing elements in the heap and dequeuing them
based on their priority level

4. Give any two applications of binary heaps.

Binary heaps have several applications. One of the most common applications is as a priority
queue12. Binary heaps can also be used in sorting-based applications3 and graph algorithms2

5. What are the methods for avoiding collision?

There are several methods for avoiding collision. Some of the most common methods include
recognizing the hazard, understanding the defense, and acting in time1. Other methods
include route planning, path planning, and reactive collision avoidance.

6. Define priority queue.

A priority queue is a data structure that stores a collection of elements and each element has a
priority associated with it. The priority of the elements determines the order in which they are
processed.

7. Define AVL tree.

An AVL tree is a self-balancing binary search tree. It was the first such data structure to be
invented. In an AVL tree, the heights of the two child subtrees of any node differ by at most
one; if at any time they differ by more than one, rebalancing is done to restore this property.

8. Define single rotation on AVL tree.

A single rotation on an AVL tree is a type of rotation that is used to keep the tree balanced.
There are two types of single rotations: left rotation and right rotation.
A left rotation is performed when a node is added into the right subtree of the right subtree. If
the tree gets out of balance, we do a single left rotation. A right rotation is performed when a
node is added to the left subtree of the left subtree. If the AVL tree gets out of balance, we do
a single right rotation

9. What is the minimum number of nodes in an AVL tree of height 15?

The minimum number of nodes in an AVL tree of height 15 is 987.
The minimum number of nodes in an AVL tree of height H is given by a recursive relation- N
(H) = N (H-1) + N (H-2) + 1. The base conditions for this recursive relation are- N (0) = 1
and N (1) = 2. Thus, the minimum number of nodes in an AVL tree of height-3 is 4, and the
maximum number of nodes that can be inserted is 15
10. Define binary heap.
A binary heap is a heap data structure that takes the form of a binary tree. Binary heaps are a
common way of implementing priority queues. A binary heap is defined as a binary tree with
two additional constraints:
 Shape property: a binary heap is a complete binary tree; that is, all levels of the tree,
except possibly the last one (deepest) are fully filled, and, if the last level of the tree is
not complete, the nodes of that level are filled from left to right.
 Heap property: the key stored in each node is either greater than or equal to (≥) or less
than or equal to (≤) the keys in the node’s children, according to some total order1

11. What are the methods used for implementing priority queue?
There are several ways to implement a priority queue, including using an array, linked list,
heap, or binary search tree. Each method has its own advantages and disadvantages, and the
best choice will depend on the specific needs of your application

12. Define hashing functions.

A hash function is any function that can be used to map data of arbitrary size to fixed-size
values. The values returned by a hash function are called hash values, hash codes, digests, or
simply hashes

13. List out the structural Properties of B Trees

The structural properties of B-trees are as follows:
 Every node in B-Tree will hold maximum m children.
 Every node except root and leaves can hold at least m/2 children.
 The root nodes must have at least two children.
 All leaf nodes must have at the same level

14. What is percolating Up and percolating down?

Percolating up and percolating down are operations performed on a heap data structure. In a
heap data structure, the root node is always the minimum or maximum element. When an
element is added to the heap, it is added to the bottom level of the heap and then percolated
up until it reaches its correct position. This process is called percolating up. When an element
is removed from the heap, the last element in the heap is moved to the root position and then
percolated down until it reaches its correct position. This process is called percolating down

15. What is a balance factor?

In a binary tree, the balance factor of a node is defined to be the height difference between its
left and right subtrees. The balance factor of a node is calculated as the height of the left
subtree minus the height of the right subtree or vice versa1

16. Difference between B tree and B+ tree.

B-tree and B+ tree are both self-balancing trees that help in maintaining and sorting data
while also allowing for searching, insertions, deletions, and sequential access. The B+ tree is
an extension of the B tree that helps in reducing the drawbacks linked with the B tree123.
The primary difference between a B-tree and a B+ tree is that in a B-tree, the keys and data
can be stored in both the internal and leaf nodes, whereas in a B+ tree, the data and keys can
only be stored in the leaf nodes
17. List the different ways of implementing priority queue.
There are several ways to implement a priority queue, including using an array, linked list,
heap, or binary search tree. Each method has its own advantages and disadvantages, and the
best choice will depend on the specific needs of your application1.
The priority queue can be implemented in four ways that include arrays, linked list, heap data
structure and binary search tree. The heap data structure is the most efficient way of
implementing the priority queue

18. What is Min heap and Max heap?

A min-heap is used to access the minimum element in the heap whereas the Max-heap is used
when accessing the maximum element in the heap.

PART IIIA

UNIVERSITY EXAM QUESTION PATTERN– 6 MARK (EACH QUESTIONCARRIES 6

MARKS)
ANSWER ALLQUESTION

1. Define AVL Trees. Explain its rotation operations with example.

AVL trees are self-balancing binary search trees. The balance factor of a node is the height of
its right subtree minus the height of its left subtree. A binary tree is said to be balanced if the
balance factor of each node is -1, 0 or +1. If the balance factor of any node is greater than 1
or less than -1, then the tree is unbalanced and we need to balance it.
There are two types of rotations in AVL trees: Left Rotation and Right Rotation. In Left
Rotation, the arrangement of the nodes on the right is transformed into the arrangements on
the left node. In Right Rotation, the arrangement of the nodes on the left is transformed into
the arrangements on the right node.
Here’s an example of how rotation operations work in AVL trees:
Suppose we have an AVL tree with nodes 7, 6, 9, 3, 8 and 10 arranged as follows:

7 (0)
/\
6 (+1) 9 (0)
/\
8 (0) 10 (0)

The balance factor of node 6 is +1 and that of node 9 is +2. This means that we do a right
rotation and pull the 7 above the 9 as shown below:

9 (0)
/\
7 (-1) 10 (0)
/\
6 (0) 8 (0)

2. Write an algorithm to perform single rotation in AVL tree.

Here’s an algorithm to perform a single rotation in AVL tree:
Algorithm SingleRotation (A, B, C)
 1. If A is the root of the tree, then make B the root.
2. Else if A is the left child of its parent, then make B the left child of A's parent.
3. Else make B the right child of A's parent.
4. Set A's left child to be B's right child.
5. Set B's right child to be A.
6. Update the height of A and B.
Here, A is the node that needs to be rotated down, B is its child that will replace it as the root
of the subtree and C is the grandchild that will become a child of B.

3. Write down an algorithm to insert a given elementin a binary tree and AVL structure.
Here’s an algorithm to insert an element in AVL tree:
Algorithm Insert (T, x)
1. Perform the standard BST insertion for x.
2. Starting from x, travel up and find the first unbalanced node.
3. Let z be the first unbalanced node, y be the child of z that comes on the path
from x to z and x be the grandchild of z that comes on the path from x to z.
4. Re-balance the tree by performing appropriate rotations on the subtree rooted
at z.
5. Update the height of z and y.
6. Return the new root of the subtree.
Here, T is the AVL tree and x is the element that needs to be inserted.

4. Write down an algorithm to find the max and smallest elementin a tree structure.
Here’s an algorithm to find the maximum and minimum element in a binary tree:
Algorithm FindMaxMin (T)
1. If T is empty, return null.
2. If T has no left child, return T.
3. Recursively find the minimum element in the left subtree of T.
4. If T has no right child, return T.
5. Recursively find the maximum element in the right subtree of T.
Here, T is the binary tree.

5. Explain how arithmetic expressions are manipulated using binary trees. Illustrate with
example.
Arithmetic expressions can be manipulated using binary trees. An arithmetic expression tree
is a binary tree in which each internal node corresponds to an operator and each leaf node
corresponds to an operand. The general strategy for producing an algebraic expression from a
binary expression tree is to recursively produce a parenthesized left expression, then print out
the operator at the root, and finally recursively produce a parenthesized right
expression. This general strategy (left, node, right) is known as an in-order traversal 1.
Here’s an example:
Expression Tree for 3 + ((5+9)*2)

+
/ \
3 *
/ \
+ 2
/\
5 9
6. Write an algorithm to perform basic operations in priority queue.
Here are the basic operations of a priority queue:
 Insertion: This operation inserts an item into the queue. The item can be inserted at
the end of the queue or at the front of the queue or at the middle based on the priority
value.
 Deletion: This operation deletes the item with the highest priority from the queue.
 Peek: This operation retrieves, but does not remove, the head of this queue, or returns
null if this queue is empty 1.
Here’s an algorithm to perform basic operations in priority queue:
Algorithm PriorityQueue:
1. Create a new empty priority queue.
2. Insert an item into the priority queue.
3. Remove an item from the priority queue.
4. Retrieve but do not remove the head of the priority queue.

7. Design a simple model and implement binary heap.

A binary heap is a complete binary tree that satisfies the heap property. The heap property
states that each parent node is either greater than or equal to (in a max heap) or less than or
equal to (in a min heap) its children nodes. A binary heap can
be efficiently implemented using an array (static or dynamic). To implement a binary
heap of height h, we need O(2^h) memory blocks and we insert the items in the array
following level-order (breadth first) of a tree1.

Here is an example implementation of binary heap in Python:

class BinaryHeap:
def __init__(self):
self.heap = []

def insert(self, value):

self.heap.append(value)
self._bubble_up(len(self.heap) - 1)

def _bubble_up(self, index):

parent = (index - 1) // 2
if index == 0:
return
elif self.heap[index] < self.heap[parent]:
self.heap[index], self.heap[parent] = self.heap[parent], self.heap[index]
self._bubble_up(parent)

def extract_min(self):
if len(self.heap) == 0:
return None
elif len(self.heap) == 1:
return self.heap.pop()
else:
min_val = self.heap[0]
self.heap[0] = self.heap.pop()
self._bubble_down(0)
 return min_val

def _bubble_down(self, index):

left_child = 2 * index + 1
right_child = 2 * index + 2
smallest_child = index

if left_child < len(self.heap) and self.heap[left_child] < self.heap[smallest_child]:

smallest_child = left_child

if right_child < len(self.heap) and self.heap[right_child] < self.heap[smallest_child]:

smallest_child = right_child

if smallest_child != index:
self.heap[index], self.heap[smallest_child] = self.heap[smallest_child],
self.heap[index]
self._bubble_down(smallest_child)

8. Write routines for ADT operation of AVL tree.

Here are some of the operations that can be performed on an AVL tree:
 Rotating the subtrees in an AVL Tree: In rotation operation, the positions of the nodes of
a subtree are interchanged. There are two types of rotations: Left Rotate and Right Rotate.
 Insertion: The insert operation is performed in the same way as in a binary search tree.
However, after insertion, the balance factor of every node is checked since insertions may
violate the property of AVL tree.
 Deletion: The delete operation is performed in the same way as in a binary search
tree. However, after deletion, the balance factor of every node is checked since deletions
may violate the property of AVL tree 

PART IV

UNIVERSITY EXAM QUESTION PATTERN– 6 MARK (EACH QUESTIONCARRIES 2

MARKS)

ANSWER ANY 10QUESTION

1. Define graph.
A graph is a collection of vertices (also called nodes) and edges that connect pairs of vertices.
A graph can be directed or undirected, depending on whether the edges have a direction or
not. In a directed graph, the edges have a direction and are represented by arrows. In an
undirected graph, the edges do not have a direction and are represented by lines .

2. Define node edge, vertex, degree and cycle of a graph.

 Node: A node is a point of intersection/connection within a network. In graph theory,
a node is usually called a vertex.
 Edge: An edge is a line or arc that connects two nodes in a graph.
 Vertex: A vertex is a point in a graph that represents an object or a concept. In graph
theory, vertices are usually called nodes.
 Degree: The degree of a vertex is the number of edges that are connected to it.
 Cycle: A cycle is a path in a graph that starts and ends at the same vertex
3. Define tree graph.
A tree is an undirected graph in which any two vertices are connected by exactly one path, or
equivalently a connected acyclic undirected graph 1. A tree represents hierarchical structure in
a graphical form. The elements of trees are called their nodes and the edges of the tree are
called branches.

4. Define digraph, directed graph and undirected graph with an example

A directed graph (digraph) is a graph that is made up of a set of vertices connected by edges,
where the edges have a direction associated with them . In other words, each edge has an
arrow that indicates the direction of the connection between two vertices. A directed graph
can be represented by an adjacency matrix or an adjacency list .
A directed graph is also called a digraph. A directed graph is a graph in which all edges are
directed from one vertex to another . For example, if we have two vertices A and B, and there
is an edge from A to B but no edge from B to A, then we have a directed graph.
An undirected graph is a graph in which all edges are bidirectional . In other words, if there is
an edge between vertices A and B, then there is also an edge between vertices B and A. An
undirected graph can be represented by an adjacency matrix or an adjacency list .

5. Define connected graph. Say when a graph G issaid to be complete.

A connected graph is a graph in which there is a path between any two vertices. In other
words, a connected graph is a graph that cannot be divided into two or more disconnected
graphs. A connected graph can be represented by an adjacency matrix or an adjacency list .
A complete graph is a graph in which every pair of vertices is connected by an edge. In other
words, a complete graph is a graph in which there are no isolated vertices. A complete graph
can be represented by an adjacency matrix or an adjacency list .

6. Define strongly connected and weakly connected graph.

A directed graph is strongly connected if there is a path between any two vertices in the
graph. In other words, a directed graph is strongly connected if it is possible to reach any
vertex from any other vertex by following the direction of the edges. A directed graph is
weakly connected if replacing all of its directed edges with undirected edges produces a
connected (undirected) graph .

7. Define adjacency matrix for graph G with example.

An adjacency matrix is a square matrix used to represent a finite graph. The elements of the
matrix indicate whether pairs of vertices are adjacent or not in the graph. In other words, if
there is an edge between vertices i and j, then the element (i,j) of the matrix is 1; otherwise it
is 0. For example, consider the following graph:
1 -- 2
| |
3 -- 4
The adjacency matrix for this graph would be:
0110
1001
1001
0110

8. Name the two standard ways of maintaining graph inmemory.

There are two standard ways of maintaining a graph in memory:
 1. Adjacency matrix representation: In this representation, we use a 2D array to
represent the graph. The rows and columns of the matrix represent the vertices of the
graph, and the elements of the matrix represent the edges between the vertices. If
there is an edge between vertex i and vertex j, then the element (i,j) of the matrix is 1;
otherwise it is 0.
2. Adjacency list representation: In this representation, we use an array of linked lists to
represent the graph. Each element of the array represents a vertex of the graph, and
the linked list associated with each vertex contains all the vertices that are adjacent to
it.

9. Define spanning tree.

A spanning tree of an undirected graph is a subgraph that is a tree which includes all of the
vertices of the graph. In other words, it is a connected acyclic subgraph of the original graph
that contains all the vertices of the original graph. A spanning tree consists of (n-1) edges,
where ‘n’ is the number of vertices (or nodes) in the graph. There may be several spanning
trees for a given graph.

10. Give the various types of graph traversal methods.

There are two types of graph traversal methods:
1. Breadth-first search (BFS): In this method, we visit all the vertices at the same level
before moving on to the next level. We start at the root node and visit all its neighbors
before visiting their neighbors.
2. Depth-first search (DFS): In this method, we visit all the vertices in a branch before
backtracking. We start at the root node and visit its first neighbor. We then visit the
first neighbor’s first neighbor, and so on until we reach a dead end. We then backtrack
to the last vertex with an unvisited neighbor and continue until all vertices have been
visited.

11. What is NP –Hard problem?

NP-hardness (non-deterministic polynomial-time hardness) is the defining property of a class
of problems that are informally “at least as hard as the hardest problems in NP”. A problem is
NP-hard if an algorithm for solving it can be translated into one for solving any NP-problem
(nondeterministic polynomial time) problem. NP-hard therefore means “at least as hard as
any NP-problem,” although it might, in fact, be harder

12. Write short notes on NP complete problem.

NP-complete problems are a class of problems that can be verified in polynomial time, but no
efficient solution algorithm has been found for them. They are as hard as any problem in NP,
meaning that any NP problem can be reduced to an NP-complete problem in polynomial
time. Examples of NP-complete problems include the traveling salesman problem and the
Hamiltonian cycle problem. If P and NP are unequal, then NP-complete problems do not
have a fast algorithm.

13. Give the properties of NP Hard and NP completeness

NP-hard problems are as hard as NP-complete problems. NP-Hard Problem need not be in
NP class. If every problem of NP can be polynomial time reduced to it called as NP Hard. A
lot of times takes the particular problem solve and reducing different problems. Example:
Hamiltonian cycle, optimization problem, shortest path.
NP-complete problems are a class of problems that can be verified in polynomial time, but no
efficient solution algorithm has been found for them. They are as hard as any problem in NP,
meaning that any NP problem can be reduced to an NP-complete problem in polynomial
time. Examples of NP-complete problems include the traveling salesman problem and the
Hamiltonian cycle problem. If P and NP are unequal, then NP-complete problems do not
have a fast algorithm

14. Define Topological sorting. Give algorithm.

Topological sorting is an algorithm that orders a directed acyclic graph in a way such that
each node appears before all the nodes it points to in the returned order. Essentially,
topological sort is an algorithm which sorts a directed graph by returning an array or a vector,
or a list, that consists of nodes where each node appears before all the nodes it points to.
Here’s how it works:
1. Compute in-degree (number of incoming edges) for each of the vertex present in the
DAG.
2. Pick all the vertices with in-degree as 0 and add them into a queue (Enqueue
operation)
3. Remove a vertex from the queue (Dequeue operation) and then.
o Increment count of visited nodes by 1.
o Decrease in-degree by 1 for all its neighboring nodes.
o If in-degree of a neighboring nodes is reduced to zero, then add it to the queue.
4. Repeat Step 3 until the queue is empty.

15. List out the applications of DFS and BFS

Depth-first search (DFS) and breadth-first search (BFS) are two popular algorithms used to
traverse/search a graph. Here are some applications of DFS and BFS:
Applications of DFS:
 Finding connected components in a graph.
 Topological sorting of a directed acyclic graph.
 Finding strongly connected components in a directed graph.
 Solving puzzles with only one solution, such as mazes.
 Generating permutations or combinations of a set of values.
 Detecting cycles in a graph.
 Applications of BFS:
 Finding the shortest path between two nodes in an unweighted graph.
 Finding the minimum spanning tree of an undirected weighted graph.
 Testing if a graph is bipartite.
 Finding all nodes within one connected component.

16. What is the worst case running time for Dijikstra’s Algorithm?
The worst case running time for Dijkstra’s Algorithm is O((|E|+|V|)log|V|) when using a
binary min-heap as a priority queue1. However, the worst case for Dijkstra binary heap
implementation is O(V log V + E log V) in the case of a sparse graph that has a lot of lone
vertices
 PART IVA

UNIVERSITY EXAM QUESTION PATTERN– 6 MARK (EACH QUESTIONCARRIES 6

MARKS)
ANSWER ALLQUESTION

1. Explain the spanning tree algorithm with example

The Spanning Tree Algorithm is used to find a minimum spanning tree for a connected
weighted graph. A minimum spanning tree is a tree that spans all the vertices of the graph and
has the minimum possible total edge weight. There are two popular algorithms to implement
the spanning tree: Prim’s and Kruskal algorithm².
Here's an example of how the algorithm works:
Suppose we have a graph with 5 vertices and 7 edges as shown below:

1
/\
2-3
/\/\
4-5-6

The algorithm starts by selecting an arbitrary vertex, say vertex 1. Then it selects the edge
with the smallest weight that connects vertex 1 to another vertex, say vertex 2. The algorithm
then adds vertex 2 to the tree and repeats the process until all vertices are included in the
tree³.
In this example, the minimum spanning tree would be:

1
\
2
/\
4-5
/\
3-6

2. Write an algorithm for Depth-firstsearch? Explain.

Depth-first search (DFS) is an algorithm for traversing or searching tree or graph data
structures. The algorithm starts at the root node (selecting some arbitrary node as the root
node in the case of a graph) and explores as far as possible along each branch before
backtracking¹.
Here's an example of how the algorithm works:
Suppose we have a graph with 5 vertices and 7 edges as shown below:

1
/\
2-3
/\/\
4-5-6

The DFS algorithm starts at vertex 1 and visits all vertices in the following order: 1, 2, 4, 5, 3,
6².
Here's an implementation of DFS in Python:

def dfs(graph, start):

visited = set()
stack = [start]

while stack:
vertex = stack.pop()

if vertex not in visited:

visited.add(vertex)
stack.extend(graph[vertex] - visited)

return visited

3. Write an algorithm for Breadth -firstsearch? Explain.

Breadth-first search (BFS) is an algorithm for searching a tree data structure for a node that
satisfies a given property. It starts at the tree root and explores all nodes at the present depth
prior to moving on to the nodes at the next depth level¹.
Here's an example of how the algorithm works:
Suppose we have a graph with 5 vertices and 7 edges as shown below:

1
/\
2-3
/\/\
4-5-6

The BFS algorithm starts at vertex 1 and visits all vertices in the following order: 1, 2, 3, 4, 5,
6².

Here's an implementation of BFS in Python:

def bfs(graph, start):

visited = set()
queue = [start]

while queue:
vertex = queue.pop(0)

if vertex not in visited:

visited.add(vertex)
queue.extend(graph[vertex] - visited)

return visited

4. Describe an algorithm to find a minimum spanning tree of a weighted graph G.

Here is an algorithm to find a minimum spanning tree of a weighted graph G:
 1. Sort all the edges in non-decreasing order of their weight.
2. Pick the smallest edge. Check if it forms a cycle with the spanning tree formed so
far. If cycle is not formed, include this edge. Else, discard it.
3. Repeat step#2 until there are (V-1) edges in the spanning tree.
4. This algorithm is known as Kruskal’s Algorithm.

5. Explain traversal techniques for graphs.

Graph traversal is a technique used for searching vertex in a graph. The graph traversal is also
used to decide the order of vertices is visited in the search process. A graph traversal finds the
edges to be used in the search process without creating loops. This means that, with graph
traversal, we can visit all the vertices of the graph without getting into a looping path. There
are two graph traversal techniques: DFS (Depth First Search) and BFS (Breadth-First
Search)¹³.
DFS starts at the root node and explores as far as possible along each branch before
backtracking⁶. BFS starts at the tree root and explores all nodes at the present depth prior to
moving on to the nodes at the next depth level¹.

6. Explain the Dijikstra’s algorithm

Dijkstra’s algorithm is an algorithm for finding the shortest paths between nodes in a
weighted graph, which may represent, for example, road networks. It was conceived by
computer scientist Edsger W. Dijkstra in 1956 and published three years later1.
The algorithm exists in many variants; Dijkstra’s original variant found the shortest path
between two nodes, but a more common variant fixes a single node as the “source” node and
finds shortest paths from the source to all other nodes in the graph, producing a shortest-path
tree

7. Explain the Kruskal’s algorithm for constructing MST.

Kruskal’s algorithm is a minimum-spanning-tree algorithm which finds an edge of the least
possible weight that connects any two trees in the forest. It is a greedy algorithm in graph
theory as it finds a minimum spanning tree for a connected weighted graph adding increasing
cost arcs at each step1.
The steps for finding MST using Kruskal’s algorithm are as follows1:
1. Sort all the edges in non-decreasing order of their weight.
2. Pick the smallest edge. Check if it forms a cycle with the spanning tree formed so far.
If the cycle is not formed, include this edge. Else, discard it.
3. Repeat step#2 until there are (V-1) edges in the spanning tree.

8. Write pseudocode for unweighted shortest path algorithm.

Here is the pseudocode for unweighted shortest path algorithm:
1. Create a queue and enqueue the starting vertex.
2. Create a visited array and mark the starting vertex as visited.
3. While the queue is not empty:
a) Dequeue a vertex from the queue.
b) For each neighbor of the vertex that has not been visited:
i. Mark the neighbor as visited.
ii. Enqueue the neighbor.
iii. Set the distance of the neighbor to the distance of the current vertex + 1.

9. Write a program to perform topological sort on a graph.

Here is a C program to perform topological sort on a graph using Depth First Search (DFS)
algorithm²:

#include<stdio.h>
#include<stdlib.h>
#define MAX 100
int n,a[MAX][MAX],visited[MAX],stack[MAX],top=-1;
void dfs(int v)
{
int i;
visited[v]=1;
for(i=1;i<=n;i++)
if(a[v][i] && !visited[i])
dfs(i);
stack[++top]=v;
}
void topological_sort()
{
int i;
for(i=1;i<=n;i++)
visited[i]=0;
for(i=1;i<=n;i++)
if(!visited[i])
dfs(i);
printf("\nTopological order:");
for(i=top;i>=0;i--)
printf("%d ",stack[i]);
}
int main()
{
int i,j;
printf("Enter number of vertices:");
scanf("%d",&n);
printf("\nEnter the adjacency matrix:\n");
for(i=1;i<=n;i++)
for(j=1;j<=n;j++)
scanf("%d",&a[i][j]);
topological_sort();
return 0;
}
 PART V

UNIVERSITY EXAM QUESTION PATTERN– 6 MARK (EACH QUESTIONCARRIES 2

MARKS)

ANSWER ANY 10QUESTION

1. Define Program.
A program is a set of instructions that a computer uses to perform a specific function. It
contains a list of ingredients (called variables, which can represent numeric data, text, or
images) and a list of directions (called statements) that tell the computer how to execute a
specific task.

2. Define Algorithm.
An algorithm is a set of instructions that are followed in order to solve a problem or perform
a task. It is essentially a step-by-step procedure that outlines exactly what needs to be done to
complete the task at hand

3. Define Problem Definition Phase

The problem definition phase is an essential initiating phase of any product development. In
this phase, you must understand the existing problem, associate available data, images, and
fundamental principles with it; generate strategies and methodology; critically evaluate state-
of-the-art technologies, other machines and components available on the market

4. What are the problem solving strategies?

There are many problem-solving strategies that can be used to solve problems. Some of the
most common strategies include trial and error, brainstorming, breaking down the problem
into smaller parts, using analogies, and using algorithms.

5. Define Top Down Design.

Top-down design is a programming style in which design begins by specifying complex
pieces and then dividing them into successively smaller pieces. The technique for writing a
program using top–down methods is to write a main procedure that names all the major
functions it will need.

6. What is the basic idea behind Divide &Conquer Strategy?

The basic idea behind the Divide and Conquer strategy is to break down a larger problem into
smaller sub-problems that are easier to solve. The sub-problems are then solved
independently, and the solutions are combined to solve the original problem.

7. Define Program Verification.

Program verification is the process of checking that a software program meets its
specification and fulfills its intended purpose. Verification is typically done by testing the
program against a set of test cases that are designed to exercise all of its features and
functions.

8. Define Input&Output Assertion.

Input and Output Assertion is a type of assertion that checks the input and output values of a
program. It is used to verify that the program is producing the correct output for a given input
9. Define Symbolic Execution
Symbolic execution is a software testing technique that is useful to aid the generation of test
data and in proving the program quality. It is a means of analyzing a program to determine
what inputs cause each part of a program to execute 1. An interpreter follows the program,
assuming symbolic values for inputs rather than obtaining actual inputs as normal execution
of the program would.

10. Define Verification Condition

A verification condition is a logical formula that represents the correctness of a program. It is
used to prove that a program meets its specification and fulfills its intended purpose.

11. Define the qualities of good algorithm.

The following are the primary factors that are often used to judge the quality of the
algorithms1:
 Precision – the steps are precisely stated (defined).
 Uniqueness – results of each step are uniquely defined and only depend on the input
and the result of the preceding steps.
 Finiteness – the algorithm stops after a finite number of instructions are executed.
 Clarity – the algorithm is easy to understand.
 Generality – the algorithm is applicable to a wide range of problems.
 Efficiency – the algorithm is fast and uses minimal resources.

12. Define Computational Complexity.

Computational complexity is a measure of the amount of resources, such as time and space,
that an algorithm needs to solve a problem. It helps computer scientists predict and compare
the efficiency of different algorithms for various tasks. Computational complexity theory also
studies the fundamental limitations and capabilities of computation, and the relationships
between different classes of problems

13. What is O–notation?

O-notation is used to describe the performance or complexity of an algorithm. It is commonly
used when discussing time complexity.
The O-notation is used to describe the upper bound of the time complexity of an algorithm. It
is used to describe how the time required for an algorithm grows as the size of the input
grows. The O-notation is used to describe the worst-case scenario for an algorithm.

14. What is Recursion? Explain with an example.

Recursion is a technique in programming where a function calls itself. It is used to solve
problems that can be broken down into smaller, more manageable subproblems.

Here’s an example of recursion in Python:

def factorial(n):
if n == 1:
return 1
else:
return n * factorial(n-1)
This function calculates the factorial of a number using recursion. The base case is when n
equals 1, and the function returns 1. If n is greater than 1, the function calls itself with n-1 as
the argument.

15. List out the performance measures of an algorithm.

The performance measures of an algorithm are:
 Time complexity: This measures the amount of time an algorithm takes to complete its
task. It is usually measured in terms of the number of operations an algorithm performs as
a function of the size of its input.
 Space complexity: This measures the amount of memory an algorithm uses to complete
its task. It is usually measured in terms of the amount of memory an algorithm requires as
a function of the size of its input.
These two measures are used to compare different algorithms and determine which one is
more efficient for a given task

16. Define Algorithm &Notion of algorithm.

An algorithm is a set of instructions that are followed to solve a problem. It is a step-by-step
procedure for solving a problem or achieving a specific goal. Algorithms are used in
computer programming to solve problems and perform tasks.
The notion of an algorithm is not limited to computer programming. It can be applied to any
process that involves solving a problem or achieving a goal. For example, a recipe for baking
a cake is an algorithm. It provides step-by-step instructions for achieving the goal of baking a
cake

PART VA

UNIVERSITY EXAM QUESTION PATTERN– 6 MARK (EACH QUESTIONCARRIES 6

MARKS)

1. Explain in detail the types on analysis that can be performed on an algorithm.

There are several types of analysis that can be performed on an algorithm. The most common
types of analysis are:
1. Worst-case analysis: This type of analysis determines the maximum number of steps
taken on any instance of size n.
2. Best-case analysis: This type of analysis determines the minimum number of steps
taken on any instance of size n.
3. Average-case analysis: This type of analysis provides a prediction about the running
time of the algorithm on an average input.
4. Amortized analysis: This type of analysis is used for algorithms that have a high
worst-case complexity but a low average-case complexity.
5. Empirical analysis: This type of analysis involves running the algorithm on a large
number of inputs and measuring its performance.

2. Design an algorithm that accepts a positive integer and reverse the order of its digits.
Here is an algorithm that accepts a positive integer and reverses the order of its digits:
1. Get the least significant digit (right-most digit) of the number.
2. Append it at the end of the reverse number.
3. Remove the right-most digit from the number.
4. Repeat steps 1-3 until all digits have been processed.
 5. Here is an example of how this algorithm works:
6. Suppose we want to reverse the digits of 1234.
7. The least significant digit is 4. Append it to the end of the reverse number, which is
initially 0. The reverse number becomes 4.
8. Remove the right-most digit from 1234, which gives us 123.
9. The least significant digit of 123 is 3. Append it to the end of the reverse number,
which is now 4. The reverse number becomes 43.
10. Remove the right-most digit from 123, which gives us 12.
11. The least significant digit of 12 is 2. Append it to the end of the reverse number,
which is now 43. The reverse number becomes 432.
12. Remove the right-most digit from 12, which gives us 1.
13. The least significant digit of 1 is 1. Append it to the end of the reverse number, which
is now 432. The reverse number becomes 4321.
14. So, if we apply this algorithm to the positive integer 1234, we get the reversed integer
4321.

3. Explain the Base conversion algorithm to convert a decimal integer to its corresponding
octal representation.
To convert a decimal integer to its corresponding octal representation, you can use the
repeated division and remainder algorithm. Here are the steps:
1. Divide the decimal number by 8.
2. Save the result and the remainder.
3. Repeat step 1, but this time, divide the result from the last calculation.
4. Once again, save the result and the remainder.
5. Repeat until the result reaches 0.
6. Take the remainders in reversed order.
For example, let’s say we want to convert the decimal integer 123 to its corresponding octal
representation.
1. 123 / 8 = 15 remainder 3
2. Save 3 as the first digit of the octal representation.
3. 15 / 8 = 1 remainder 7
4. Save 7 as the second digit of the octal representation.
5. 1 / 8 = 0 remainder 1
6. Save 1 as the third digit of the octal representation.
7. So, the octal representation of decimal integer 123 is 173.

4. Explain in detail about Greedy algorithm with an example.

A greedy algorithm is an algorithmic paradigm that follows the problem-solving heuristic of
making the locally optimal choice at each stage with the hope of finding a global optimum. In
other words, a greedy algorithm never reconsiders its choices. This is the main difference
from dynamic programming algorithms that may re-use solutions to sub-problems.
A classic example of a problem that can be solved using a greedy algorithm is the “coin
change” problem. The problem is to make change for a given amount of money using the
least possible number of coins. Suppose we have coins of denominations 1, 5, 10, and 25
cents. To make change for 41 cents, we can use one 25-cent coin, one 10-cent coin, and one
5-cent coin.
Another example of a problem that can be solved using a greedy algorithm is the “interval
scheduling” problem. The problem is to schedule as many tasks as possible on a single
processor given that each task has a start time and an end time. The greedy algorithm sorts
the tasks by their end times and then schedules them in order of increasing end times.
 5. Explain in detail about Divide and conquer algorithm with an example alsomark the
difference between Greedy and divide and conquer algorithm.
Divide and conquer is an algorithmic paradigm that works by recursively breaking down a
problem into two or more sub-problems of the same or related type, until these become
simple enough to be solved directly. The solutions to the sub-problems are then combined to
solve the original problem.
A classic example of a problem that can be solved using a divide-and-conquer algorithm is
the “merge sort” algorithm. The problem is to sort an array of n elements. The divide-and-
conquer algorithm works by dividing the array into two halves, sorting each half recursively,
and then merging the two sorted halves.
The main difference between greedy algorithms and divide-and-conquer algorithms is that
greedy algorithms make locally optimal choices at each step with the hope of finding a global
optimum, while divide-and-conquer algorithms break down a problem into smaller sub-
problems that can be solved independently and then combine their solutions to solve the
original problem.

6. Describe the backtracking problem using knapsack problem.

The knapsack problem is a classic example of a problem that can be solved using
backtracking. The problem is to fill a knapsack with items of different weights and values so
as to maximize the total value of the knapsack while keeping the total weight of the items in
the knapsack below a certain limit.
The backtracking algorithm works by recursively building up a solution one item at a time.
At each step, the algorithm chooses whether or not to include the next item in the knapsack.
If including the item would cause the weight limit to be exceeded, then the algorithm
backtracks and tries another option.
For example, suppose we have a knapsack with a weight limit of 10 and three items with
weights and values as follows:
Item Weight Value

1 6 30

2 3 14

3 4 16
The backtracking algorithm would start by considering whether or not to include item 1 in the
knapsack. If it does include item 1, then it would consider whether or not to include item 2. If
it does include item 2, then it would consider whether or not to include item 3. If it does not
include item 3, then it would backtrack and try another option.
The main difference between backtracking algorithms and dynamic programming algorithms
is that backtracking algorithms explore all possible solutions to a problem, while dynamic
programming algorithms only explore those solutions that are necessary to solve the problem.

7. Discuss briefly the various asymptotic notations used in algorithm analysis

Asymptotic notation is used to describe the running time of an algorithm in terms of the input
size. There are three main asymptotic notations used in algorithm analysis:
1. Big O notation: This notation is used to describe the upper bound on the running time
of an algorithm. It represents the worst-case scenario for the algorithm’s running time.
2. Omega notation: This notation is used to describe the lower bound on the running
time of an algorithm. It represents the best-case scenario for the algorithm’s running
time.
 3. Theta notation: This notation is used to describe both the upper and lower bounds on
the running time of an algorithm. It represents the average-case scenario for the
algorithm’s running time.
For example, suppose we have an algorithm that takes n^2 steps to complete. We can say that
the running time of this algorithm is O(n^2), which means that it takes no more than n^2
steps to complete. We can also say that the running time of this algorithm is Omega(n^2),
which means that it takes at least n^2 steps to complete. Finally, we can say that the running
time of this algorithm is Theta(n^2), which means that it takes exactly n^2 steps to complete.

8. Write a greedy algorithm to solve job sequencing with deadline problem.

The job sequencing with deadline problem is a classic optimization problem that can be
solved using the greedy algorithm. The problem is to find the maximum profit subset of jobs
that can be completed within their deadlines. Here is how the greedy algorithm works:
1. Sort the jobs in decreasing order of their profits.
2. For each job, starting from the first one in the sorted list, assign it to the latest possible
time slot that is available.
3. If there is no available time slot for a job, skip it.
This algorithm has a time complexity of O(n^2) and a space complexity of O(n), where n is
the number of jobs.