Visvesvaraya Technological University

Belagavi, Karnataka -590018.

Scheme & Solutions

Signature Of Scrutinizer

Subject Title : Data Structure & Algorithms for problem solving Subject Code : MCS103

Question Marks
Number Solution Allocated
1 a. A Data Structure is a method of organizing and storing data in a computer so that it can be
used efficiently for operations such as searching, insertion, deletion, and updating(5m)

10M

Explanations(5m)

1 b. INSERTION CODE(5M)

10M
Return
}

DELETION CODE(5M)
Subject Title : Data Structure & Algorithms for problem solving Subject Code : MCS103

Question Marks
Number Solution Allocated

2 a. BUILDING OF OBST
BOTTOM UP Approach(3M) 10M

EXPLANATION(2M)
Subject Title : Data Structure & Algorithms for problem solving Subject Code : MCS103

Question Marks
Number Solution Allocated

TOP Down approach(3M)

Explainations(2M)
Subject Title : Data Structure & Algorithms for problem solving Subject Code : MCS103

Question Marks
Number Solution Allocated

2 b.

10M
Subject Title : Data Structure & Algorithms for problem solving Subject Code : MCS103

Question Marks
Number Solution Allocated

3 a. A Red-Black Tree is a self-balancing Binary Search Tree in which each node is colored
Red or Black. The coloring rules ensure that the tree remains approximately balanced, 10M
giving efficient search operations.(2M)

DAIGRAM(3M)
EXPLAINATIONS(5M)
Subject Title : Data Structure & Algorithms for problem solving Subject Code : MCS103

Question Marks
Number Solution Allocated

3b Constructions of tree interval

10M

DAIGRAM +EXPLANATION(5M+5M)

4 a. Orthogonal Range Trees (Peter Brass):Efficiently answer orthogonal range queries

— finding all points inside an axis-aligned rectangle in multidimensional space.
Structure:In 1D, it is a balanced binary search [Link] 2D, a BST on x-coordinates, 10M
with each node storing a secondary BST on [Link] d dimensions, recursively
nests trees on each coordinate.
Complexity:Preprocessing: O(n log ⁡d−1 n). Query: O(log ⁡d n+ k), where k is the number
of reported points.
Example: Given points ¿, a query rectangle ¿returns ¿.
(5M)
Significance (Brass): Orthogonal range trees are a canonical solution for
multidimensional range searching, balancing preprocessing cost with efficient query
time.
Definition: A semigroup is a set with an associative binary operation (like addition,
min, max).Restriction: Unlike groups, semigroups lack inverses — meaning
subtraction or undoing is not [Link] in Range Searching:
 Queries must be answered by combining stored values using the semigroup
operation.
 This models problems where only aggregation is possible.
Subject Title : Data Structure & Algorithms for problem solving Subject Code : MCS103

Question Marks
Number Solution Allocated

Example:
 Points with weights [ 2 ,5 , 7 , 3 ] .
 Operation: addition.
 Query: sum of weights in range [2,3] → 5+7=12.
 Works because addition is associative, but subtraction or averages are not
directly supported.
Significance (Brass): The semigroup model is used to analyze the limits of efficiency
in range searching problems, showing what can or cannot be achieved when only
associative operations are allowed. (5M)

4b. A search tree (like a balanced binary search tree) is designed for 1-dimensional data.
It supports queries such as: find all elements in an interval [ a , b ]. Complexity: 10M
Construction: O(n),Query: O(log ⁡n+k ), where k is the number of reported elements.
Limitation: It only handles one dimension efficiently.

Higher-Dimensional Segment Tree: A segment tree can be generalized to d

dimensions,instead of storing intervals only on one axis, it recursively stores structures
for each additional dimension.
 For example:In 2D, the top tree is built on x-intervals, and each node stores a
secondary segment tree on [Link] d dimensions, each node stores a
( d −1 ) -dimensional segment tree.
d−1 d
 Complexity (Brass): Construction: O(n log ⁡ n). Query: O(log ⁡ n+ k) .
Advantage: Efficient for orthogonal range queries in higher dimensions.
Limitation: Space usage grows significantly compared to normal search trees.

5 a.
A HEAP is defined as a specialized tree-based structure that satisfies the heap
property, most commonly implemented as a complete binary tree. In a min-heap, the
value of each node is less than or equal to the values of its children, ensuring that the 10M
smallest element is always at the root. Conversely, in a max-heap, the value of each
node is greater than or equal to the values of its children, so the largest element is at the
root. Because the tree is complete, heaps are efficiently stored in arrays, where parent
and child relationships can be determined by simple index calculations.
THEOREM
typedef struct {
key_t key;
object_t *object;
} heap_el_t;

typedef struct {
heap_el_t current_min;
tree_node_t *tree;
} heap_t;

heap_t *create_heap(void)
{
heap_t *hp;
 hp = (heap_t *) malloc(sizeof(heap_t));
hp->tree = create_tree();

return hp;
}

int heap_empty(heap_t *hp)

{
return (hp->tree->left == NULL);
}
}
insert(hp->tree, new_key, new_obj);
}

object_t *delete_min(heap_t *hp)

{
object_t *del_obj;
tree_node_t *tmp_node;

if (hp->tree->left == NULL)
return(NULL); /* heap empty */
else
{
del_obj = hp->current_min.object;
delete(hp->tree, hp->current_min.key);
tmp_node = hp->tree;

if (tmp_node->left != NULL)
/* update current_min */
{
while (tmp_node->right != NULL)
tmp_node = tmp_node->left;

hp->current_min.key = tmp_node->key;
hp->current_min.object = (object_t *)
tmp_node->left;
}
return(del_obj);
}
}

void remove_heap(heap_t *hp)

{
remove_tree(hp->tree);
free(hp);
}

Subject Title : Data Structure & Algorithms for problem solving Subject Code : MCS103
Question Marks
Number Solution Allocated

5 b.

10M

6 a. A leftist heap is a binary tree that satisfies two important properties.

The first is the min-heap order property, which states that the key stored at each node
is less than or equal to the keys stored in its children. Because of this property, the 10M
smallest element in the heap is always located at the root of the tree.
The second property is the leftist property, which requires that for every node, the
null path length of the left child is greater than or equal to that of the right child. This
property makes the tree left-heavy and ensures that the right subtree of any node is
relatively short.
The length of the rightmost path of a leftist heap with n nodes is at most O(log n). This
bound on the right path length plays a key role in determining the time complexity of
the heap operations.
The find-min operation simply returns the element stored at the root of the heap. Since
no traversal or modification of the heap is required and the minimum element is always
available at the root, this operation takes constant time, that is O(1).
The merge operation combines two leftist heaps into a single leftist heap. During
merging, the roots of the two heaps are compared, and the root with the smaller key
becomes the root of the merged heap.
The length of this path is at most O(log n), the merge operation takes O(log n) time.
The insert operation is performed by creating a new leftist heap containing a single
node and then merging it with the existing heap. Since insertion is implemented using
the merge operation, its time complexity is also O(log n).

Subject Title : Data Structure & Algorithms for problem solving Subject Code : MCS103
Question Marks
Number Solution Allocated

The delete-min operation removes the root node, which contains the minimum
element. After removing the root, the left and right subtrees of the root are merged to
form a new leftist heap. find-min in O(1) time and insert, merge, and delete-min in
O(log n) time. Hence, the theorem is proved.

6 b.
A Fibonacci heap is a collection of trees that satisfy the min-heap order property,
where the key of a parent node is less than or equal to the keys of its children. Unlike 10M
binary or leftist heaps, a Fibonacci heap is more relaxed in structure. It allows trees to
be loosely balanced and uses lazy consolidation, which improves the amortized
performance of operations.
In a Fibonacci heap, all trees are stored in a circular doubly linked list, and a pointer
is maintained to the node containing the minimum key. Each node keeps track of its
degree (number of children) and a mark bit, which is used during the decrease-key
operation.
The find-min operation simply returns the node pointed to by the minimum pointer.
Since no traversal or restructuring is required, this operation takes O(1) time.
The insert operation adds a new node by creating a single-node tree and inserting it
into the root list of the heap. The minimum pointer is updated if necessary. As this
operation involves only constant-time pointer updates and no restructuring, the insert
operation runs in O(1) time.
The merge (union) operation concatenates the root lists of two Fibonacci heaps and
updates the minimum pointer to the smaller of the two minima. Since this is done by
linking two circular doubly linked lists, the merge operation also takes O(1) time.
The decrease-key operation reduces the key value of a given node. If the min-heap
order property is violated, the node is cut from its parent and added to the root list. If
the parent had already lost a child earlier, a cascading cut is performed, cutting the
parent as well. Although multiple cuts may occur in a single operation, the use of mark
bits ensures that the total number of such cuts over a sequence of operations is limited.
Hence, when averaged over many operations, the amortized time complexity of
decrease-key is O(1).
The delete-min operation removes the node containing the minimum key. After
removal, all its children are added to the root list. The heap then performs
consolidation, where trees of the same degree are repeatedly linked together until no
two roots have the same degree. This process ensures that the maximum degree of any
node is O(log n). Since consolidation involves at most a logarithmic number of link
operations, the amortized time complexity of delete-min is O(log n).
Thus, due to the relaxed structure, lazy consolidation, and the use of amortized
analysis, Fibonacci heaps efficiently support find-min, insert, and merge in O(1)
time, decrease-key in amortized O(1) time, and delete-min in amortized O(log n)
time.

Subject Title : Data Structure & Algorithms for problem solving Subject Code : MCS103
Question Marks
Number Solution Allocated

7 a. ALGORITHEM OF BELLMEN FORD (5M)

10M

SOLUTION(5M)

The result Graph

ALGORITHEM ACG
7 b.

10M

Subject Title : Data Structure & Algorithms for problem solving Subject Code : MCS103
Question Marks
Number Solution Allocated

The Result Graph is

8 a.
ALGORITHEM
10M

THE RESULT GRAPH IS

Subject Title : Data Structure & Algorithms for problem solving Subject Code : MCS103
Question Marks
Number Solution Allocated

8 b. Floyd-Warshall algorithm

10M

explanation

Johnson’s algorithm for sparse graphs

Subject Title : Data Structure & Algorithms for problem solving Subject Code : MCS103
Question Marks
Number Solution Allocated

9 a.

10M

solutions

The Result graph is

9 b. A polynomial is a mathematical expression consisting of variables and

constants combined using addition, subtraction, and multiplication, where
the variables are raised only to non-negative integer powers.
General form: 10M
2 n
P(x )=a 0+ a1 x + a2 x +⋯+a n x
where
 a 0 , a 1 , … , an are constants (coefficients)
 x is the variable
 n is a non-negative integer (degree of the polynomial)

Subject Title : Data Structure & Algorithms for problem solving Subject Code : MCS103
Question Marks
Number Solution Allocated

DFT (Discrete Fourier Transform) FFT (Fast Fourier Transform)

DFT is a mathematical transformation FFT is an algorithm to compute DFT
Converts time-domain signal to frequency
domain Efficiently computes the same frequency domain
result

Computational complexity is O(N²) Computational complexity is O(N log N)

Slow for large input size Very fast for large input size
Direct calculation using formula Uses divide-and-conquer approach
High computation time Reduced computation time
Used for small data sizes Preferred for large data sizes
Not optimized Highly optimized
Basic concept in signal processing Practical implementation in signal processing
Less efficient in real-time systems Efficient in real-time systems

10 a. Rabin–Karp algorithm is a string matching algorithm used to find a

pattern within a given text by comparing hash values of the pattern and
substrings of the text. 10M
It uses a rolling hash technique to efficiently compute and update hash
values, allowing fast comparison and reducing unnecessary character-by-
character checks.
ALGORITHM

EXPLANATIONS

Subject Title : Data Structure & Algorithms for problem solving Subject Code :MCS103
Question Marks
Number Solution Allocated

10b.
Knuth-Morries-Pratt Algorithem
The Knuth–Morris–Pratt (KMP) algorithm is a string matching algorithm used to find
occurrences of a pattern in a text efficiently.
It avoids unnecessary comparisons by using a prefix function (LPS – Longest Proper
Prefix which is also Suffix) to determine how much the pattern can be shifted after a
mismatch. 10M

EXPLAINATIONS

Subject Title : Subject Code :

Question Marks
Number Solution Allocated

Subject Title : Subject Code :

Question Marks
Number Solution Allocated

Subject Title : Subject Code :

Question Marks
Number Solution Allocated

Subject Title : Subject Code :

Question Marks
Number Solution Allocated

Subject Title : Subject Code :

Question Marks
Number Solution Allocated

Subject Title : Subject Code :

Question Marks
Number Solution Allocated

Subject Title : Subject Code :

Question Marks
Number Solution Allocated

Subject Title : Subject Code :

Question Marks
Number Solution Allocated

Subject Title : Subject Code :

Question Marks
Number Solution Allocated

Subject Title : Subject Code :

Question Marks
Number Solution Allocated

Subject Title : Subject Code :

Question Marks
Number Solution Allocated

Subject Title : Subject Code :

Question Marks
Number Solution Allocated

Subject Title : Subject Code :

Question Marks
Number Solution Allocated

Subject Title : Subject Code :

Question Marks
Number Solution Allocated

Subject Title : Subject Code :

Question Marks
Number Solution Allocated

Subject Title : Subject Code :

Question Marks
Number Solution Allocated