Advanced Data Structure & Analysis: Compiled Question Bank
This document compiles exam questions from the provided question papers, categorized according
to the modules outlined in the ADSA_TH_Syllabus.pdf1.
Source
Source PDF
Code
Advance-data-structures-and-analysisElective-I00055912Choice-based dec
A1
[Link]
A2 10026804_INFT5-Advanced-data-structure-and-analysis may [Link]
A3 10011895-advanced-data-structure-and-analysis dec [Link]
A4 Advance-data-structures-and-analysis-of-algorithms00055910 may [Link]
Advance-data-structures-and-analysis-of-algorithms00076932Elective-IChoice-
A5
base dec [Link]
Module I: Introduction to Analysis of Algorithms (CO1)
This module covers fundamentals of algorithm analysis, asymptotic notation, and recurrence
relations2.
Source
Question
PDF
What is Complexity? Explain in detail asymptotic notations (Big 'O', Theta '$\
A2, A3
Theta$').
Which are the different methods of solving recurrences? Explain with suitable A1, A2,
examples. A5
Find out the time complexity for the recurrence equation as follows: A3
$\quad \bullet$ $T(n)=T(n/2)+1$ A3
$\quad \bullet$ $T(n)=2T(n/2)+n$ A3
Give asymptotic upper bound for $T(n)$ for the following recurrence and verify
A4
your answer using Master's theorem: $T(n)=T(n-1)+n$.
Write short note on Master's theorem. A3
Compute the worst case complexity of the following program segment: void
A4
fun(int n, int arr[]) { int i=0, j=0; for(; i<n; ++i) while(j < n && arr[i] < arr[j]) j++; }
Explain with example how divide and conquer strategy is used in Binary Search? A1
Analyze Time complexity of Binary Search using Divide and Conquer. Also write
A3
the algorithm for the same.
Module II: Advanced Data Structures (CO2)
This module includes topics on AVL trees, B-trees, Red-Black Trees, and Graphs/Traversals 3.
Source
Question
PDF
Define AVL tree. Construct an AVL tree for the following data: $21, 26, 30, 9, 4,
A4
14, 28, 18, 15, 10, 2, 3, 7$.
Define AVL tree. Construct an AVL tree for the following data: $63, 9, 19, 27, 18,
A5
108, 99, 81$.
Write a note on AVL Tree. A1
Define B-tree. Explain insertion and deletion operations on a B-tree, with an
A2
example of each.
Create a B tree of order 5 by inserting the following elements: $3, 14, 7, 1, 8, 5,
A3
11, 17, 13, 6, 23, 12, 20, 26, 4, 16, 18, 24, 25, 19$.
A1, A4,
Write Short note on Red and Black Tree (Red Black Trees).
A5
Build a max heap for the following: $45, 65, 34, 25, 78, 56, 15$. A2
Build a max heap H from the given set of numbers: $45, 36, 54, 27, 63, 72, 61$
A3
and $18$. Also draw the memory representation of the heap.
Module III: Greedy Algorithms and Applications (CO3)
This module focuses on the Fractional Knapsack problem, Minimum Spanning Trees (Prim's and
Kruskal's), and Job Sequencing with deadlines4.
Source
Question
PDF
Explain greedy strategy of designing an algorithm. A3
Consider the instance of knapsack problem... Find maximum profit using
A2, A4
Fractional Knapsack.
Explain knapsack Problem with an example. A5
A1, A4,
Explain Huffman algorithm. Construct Huffman tree and find Huffman code for:
A5
$\quad \bullet$ message: MAHARASHTRA A1
$\quad \bullet$ set of frequencies: $a:1, b:1, c:2, d:3, e:5, f:8, g:13, h:21$
A4
(Optimal Huffman code based on first 8 Fibonacci numbers)
Explain Flow Shop Scheduling Technique (Explain flow shop scheduling). A1, A5
Explain Job sequencing with deadlines. Find feasible solution for $n=4$, $(p_1,
A1
p_2, p_3, p_4) = (100, 10, 15, 27)$ and $(d_1, d_2, d_3, d_4) = (2, 1, 2, 1)$.
What is the sequence of jobs, for the following sequence of job data, which will
A3
achieve maximum profit? (Data table provided)
Construct a minimum spanning tree shown in Figure 2 using Kruskal's and Prim's
A4
Algorithm and find out the cost with all intermediate steps.
Differentiate between Prim's and Kruskal's algorithms. A2
Explain coin changing problem. A5
Module IV: Backtracking and Maximum Flow Networks (CO4)
This module covers Backtracking techniques (N-Queens, Sum of Subsets, Graph Coloring,
Hamiltonian Cycles) and the Ford Fulkerson method5.
Source
Question
PDF
No questions found that directly map to the core topics of Backtracking or
N/A
Maximum Flow Networks.
Module V: Dynamic Algorithms (CO5)
This module includes Dijkstra's, Bellman Ford, Floyd Warshall, 0/1 Knapsack, and the Traveling
Salesman Problem6.
Source
Question
PDF
Differentiate between greedy method and Dynamic Programming. (Compare
A1, A2,
Greedy approach and Dynamic Programming approach for an algorithm
A4, A5
design).
Explain 0/1 knapsack problem using dynamic programming. A3
What is longest common subsequence problem? Find LCS for the following A1, A2,
strings: A4, A5
$\quad \bullet$ $X=ACBAED$, $Y=ABCABE$ A1, A4
$\quad \bullet$ $X=ABCDGH$, $Y=AEDFHR$ A5
$\quad \bullet$ $X=abcabcba$, $Y=babcbcab$ A2
Explain Matrix chain multiplication in detail. Find $m[1,4]$ using matrix chain
A1, A2, A3
multiplication.
Apply all pair shortest path on the following graph (Figure provided). A1
Describe algorithm and complexity of all pair shortest path. A3
What is optimal binary search tree? Explain with the help of an example. A4, A5
A traveler needs to visit all the cities from a list (Figure 1)... What is the shortest
A4
possible route? (Relates to Travelling Salesperson Problem (TSP)).
Module VI: String Matching Algorithms (CO6)
This module includes Naïve, Rabin-Karp, and Knuth-Morris-Pratt (KMP) algorithms 7.
Question Source PDF
Explain the Knuth-Morris-Pratt algorithm (KMP). (Describe, with the help of an A1, A2, A3,
example, KMP algorithm. Also, comment on complexity.) A5
Explain Rabin Karp Algorithm in detail. A1, A4, A5
Compute prefix function for the pattern: ababaca. A3
Describe naive string matching method. Write the algorithm for the same. A2
General/Other Algorithms
These questions cover general algorithms and paradigms not strictly mapped to the core advanced
modules.
Question Source PDF
A2, A3, A4,
Explain Genetic algorithms in detail.
A5
A1, A2, A3,
Sort the following numbers using Quick sort (and/or derive time complexity):
A5
$\quad \bullet$ $50, 31, 71, 38, 77, 81, 12, 33$ A3
$\quad \bullet$ $20, 30, 14, 56, 9, 72, 45, 5$ A2
$\quad \bullet$ $27, 10, 36, 18, 25, 45$ A1
Write Short notes on Merge Sort. A5
Explain approximation algorithms with an example. A2
Explain divide and conquer approach. Write a recursive algorithm to
A4
determine the max and min from given elements.
Write an algorithm for finding minimum and maximum number from a given
A1, A5
set.
Write Note on Topological Sort. A1