SVKM’s

D. J. Sanghvi College of Engineering

Program: B.Tech in Information Academic Year: 2022 Duration: 3 hours

Instructions: Candidates should read carefully the instructions printed on the question paper and
on the cover page of the Answer Book, which is provided for their use.
(1) This question paper contains two pages.
(2) All Questions are Compulsory.
(3) All questions carry equal marks.
(4) Answer to each new question is to be started on a fresh page.
(5) Figures in the brackets on the right indicate full marks.
(6) Assume suitable data wherever required, but justify it.
(7) Draw the neat labelled diagrams, wherever necessary.
Question Max.
No. Marks
Q1 (a) Write an algorithm to merge two sorted linked lists to create a new one. Take any 10
two sample sorted linked lists and trace your algorithm on it.
OR
Write an algorithm to insert a node into a sorted doubly linked list. Trace your
algorithm on sample sorted doubly linked list
Q1 (b) Write an algorithm to find the length of a circular linked list 05
Q2 (a) Write down an algorithm, which will take a string ‘S’ as input. The string S is 10
formed using alphabets {a, b, c} only. Find whether the input string is from the set
L = {anbmck | n = m + k and n, m, k  1}. E.g., aaabbc,aaaabccc  L and abbc,
aabccc  L. Use appropriate data structure and justify it. Trace your algorithm on
sample input given in the example.
Q2 (b) Consider the following three claims 05
I. (n + k)m = Θ(nm) where k and m are constants
II. 2n+1 = O(2n)
III. 22n = O(22n)
Which of these claims are correct? Justify you answer.
OR
There are n unsorted arrays: A1, A2, ..., An. Assume that n is odd. Each of A1, A2,
..., An contains n distinct elements. There are no common elements between any
two arrays. Find the worst-case time complexity of computing the median of the
medians of A1, A2, ..., An? Justify your answer.
Q3 (a) Write down an algorithm for finding the depth of a node X in the binary search 05
tree.

********** 1 **********
Q3 (b) Write down the algorithm to perform following operations on Double Ended 10
Queue, which is to be implemented using circular array.
Enqueue_Rear(x), Enqueue_Front(x), Dequeue_Front(), Dequeue_Rear().
OR
In the Josephus problem from antiquity, n people are in a crisis and agree to the
following strategy to reduce the population. They arrange themselves in a circle
(at positions numbered from 0 to n - 1) and proceed around the circle, eliminating
every mth person until only one person is left. Legend has it that Josephus figured
out where to sit to avoid being eliminated. Using appropriate data structure, write
a program that takes two integer command-line arguments m and n, and prints the
order in which people are eliminated (and thus would show Josephus where to sit
in the circle).
Q4 (a) Give an algorithm for checking whether a given graph G has simple path from 08
source s to destination d. Assume that the graph G is represented using the adjacent
matrix. Trace your algorithm on any graph.
OR

Explain briefly: priority queue. Which is the best way to implement the priority
queue? Justify your answer. State various applications of priority queue.
Q4 (b) Sort the letters of word “EXAMPLE” in alphabetical order using insertion sort. 07
Q5 (a) Consider AVL Tree given below 07

Perform following operations on it. Calculate balance factor of each node after
every operation.
I. Insert keys {14, 3, 2, 98, 76}
II. Delete keys: {12, 8}
OR

Write down an algorithm for finding the mirror of BST and trace the algorithm on
AVL tree given in Q5a.
Q5 (b) Consider following four hash functions on integers. 08
h(i) =i2 mod 10, h(i) =i3 mod 10, h(i) = (11 ∗ i2) mod 10, h(i) = (12 ∗ i) mod 10
Which function from the above four will distribute keys most uniformly over 10
buckets numbered 0 to 9 for i ranging from 0 to 9? Justify your answer.

********** 2 **********