ANALYSIS & DESIGN OF ALGORITHMS (BCS401)
Comprehensive Module-Wise Question Repeatability & Priority Analysis (Compiled from VTU Previous Year
Papers)
Module 1 — Introduction & Analysis Framework
PRIORITY LEVEL QUESTION / CORE CURRICULAR CONCEPT FREQUENCY
Highly Repeated Asymptotic Notations: Define algorithm and explain asymptotic notations 4 Times
(Big-O, Big-Omega, Big-Theta) with definitions, formal graphical
representations, and numerical examples/proofs.
Highly Repeated Sequential Search Analysis: Design an algorithm to search for an 3 Times
element in an array using sequential search. Derive and discuss its Best-
case, Worst-case, and Average-case time efficiencies.
Highly Repeated Mathematical Analysis of Recursive Algorithms: Explain the general 3 Times
plan for analyzing the time efficiency of recursive algorithms. Suggest an
algorithm and analyze its complexity framework (e.g., Tower of Hanoi,
Factorial computation).
Repeated Algorithm Design Process: Explain the various fundamental steps 2 Times
involved in the algorithm design and analysis process in detail with a neat
structure/flow diagram.
Low / Non- Mathematical Analysis of Non-Recursive Algorithms: Explain the 1 Time
Repeated general plan for analyzing non-recursive algorithms. Suggest an algorithm
to find the maximum element in a given list of $n$ numbers and derive its
efficiency.
Low / Non- Bubble Sort Efficiency: Write the algorithm or detail the analytical 1 Time
Repeated process to derive the worst-case efficiency of the Bubble Sort algorithm.
Low / Non- Asymptotic Growth Proof: Prove mathematically that if t_1(n) ∈ 1 Time
Repeated O(g_1(n)) and t_2(n) ∈ O(g_2(n)), then t_1(n) + t_2(n) ∈ O(max{g_1(n),
g_2(n)}).
Module 2 — Divide-and-Conquer & Decrease-and-Conquer
PRIORITY LEVEL QUESTION / CORE CURRICULAR CONCEPT FREQUENCY
Highly Repeated Quick Sort: Design the Quick Sort algorithm utilizing the divide-and- 4 Times
conquer strategy. Trace its execution on a given character/numeric list
(e.g., 5, 3, 1, 9, 8, 2, 4, 7 or E, X, A, M, P, L, E) and analyze its best, average,
and worst-case efficiencies.
ADA (BCS401) — Module-Wise Repeatability Analysis Page 1 of 4
PRIORITY LEVEL QUESTION / CORE CURRICULAR CONCEPT FREQUENCY
Highly Repeated Strassen’s Matrix Multiplication: Explain Strassen's matrix multiplication 3 Times
approach, derive its recurrence relation and time complexity, and apply it
to multiply basic $2 imes 2$ matrices.
Highly Repeated Topological Sorting: Define topological sorting. Detail and execute the 3 Times
two major approaches to obtain the topological order for a given graph: (i)
Source Removal Method, and (ii) Depth-First Search (DFS) Method.
Repeated Merge Sort: Develop the full Merge Sort algorithm. Analyze its structural 2 Times
recurrence relation to establish time efficiency, and trace the algorithm
step-by-step using an array/character list.
Repeated Insertion Sort: Design an algorithm to sort numbers using Insertion Sort. 2 Times
Discuss its computational complexity/efficiency, and apply it to an arbitrary
set of input integers.
Low / Non- Design Technique Comparison: Distinguish clearly between the 1 Time
Repeated Decrease-and-Conquer technique and the Divide-and-Conquer algorithm
design framework using block diagrams.
Low / Non- Tree Traversals: Write systematic algorithms for the classical structural 1 Time
Repeated traversals of a tree: Pre-order, In-order, and Post-order. Trace and list the
output for a provided binary tree.
Module 3 — Space-Time Trade-offs & Dynamic Trees
PRIORITY LEVEL QUESTION / CORE CURRICULAR CONCEPT FREQUENCY
Highly Repeated Horspool’s String Matching: Design and write Horspool’s string 4 Times
matching algorithm. Apply it explicitly to find a pattern (e.g., BARBER)
within a target body text (e.g., JIM_SAW_ME_IN_A_BARBERSHOP) by
detailing shift table updates.
Highly Repeated AVL Tree Construction: Define an AVL Tree, its balancing constraints, 3 Times
and explain its four major structural rotation types (LL, RR, LR, RL).
Construct an AVL tree step-by-step from a specified sequence of numeric
keys.
Highly Repeated Heap Sort & Heap Construction: Define the heap structure, max/min 3 Times
heap properties, and its array representation. Detail the bottom-up heap
construction algorithm and apply Heap Sort to sort a list in ascending
order.
Repeated 2-3 Tree Analysis: Define a 2-3 Tree and state the worst-case operational 2 Times
time efficiency metrics. Construct a 2-3 tree for a given sequence of keys,
clearly indicating each data insertion step and node split phase.
ADA (BCS401) — Module-Wise Repeatability Analysis Page 2 of 4
PRIORITY LEVEL QUESTION / CORE CURRICULAR CONCEPT FREQUENCY
Low / Non- Comparison Counting Sort: Write the algorithmic steps for the 1 Time
Repeated Comparison Counting Sort method and discuss its overall time and space
efficiencies.
Module 4 — Greedy Method & Dynamic Programming
PRIORITY LEVEL QUESTION / CORE CURRICULAR CONCEPT FREQUENCY
Highly Repeated Dijkstra’s Algorithm: State and write Dijkstra's algorithm for single-source 4 Times
shortest paths. Apply it systematically to find the shortest distances from a
designated source vertex on a weighted graph.
Highly Repeated Huffman Trees & Codes: Explain the structural logic of Huffman Trees. 4 Times
Given a list of characters and their frequencies/probabilities, construct the
optimal Huffman tree, define the resulting codewords, and perform sample
text encoding/decoding.
Highly Repeated Kruskal’s Algorithm: State the minimum spanning tree problem definition 3 Times
and write Kruskal's algorithm. Illustrate its path-selection sequence step-
by-step on a provided undirected weighted graph.
Repeated Warshall’s Algorithm (Transitive Closure): Define the transitive closure 2 Times
of a directed graph. Write Warshall's algorithm and apply it to compute the
complete transitive closure matrix for a given directed graph structure.
Low / Non- Floyd’s Algorithm (All-Pairs Shortest Path): Explain the dynamic 1 Time
Repeated programming principles of Floyd's algorithm. Apply it step-by-step to
calculate the all-pairs shortest path matrix from a given initial weight matrix
W.
Module 5 — Limitations of Algorithmic Power & State-Space Search
PRIORITY LEVEL QUESTION / CORE CURRICULAR CONCEPT FREQUENCY
Highly Repeated Sum of Subsets (Backtracking): Apply the backtracking methodology to 4 Times
find all valid subsets for a given numeric set S that sum to a target capacity
d (e.g., S={3,5,6,7}, d=15). Trace using an explicit state-space tree.
Highly Repeated 0/1 Knapsack (Branch and Bound): Solve an instance of the discrete 0/1 4 Times
Knapsack optimization problem using the Branch and Bound technique.
Detail lower bound calculations and construct the corresponding state-
space tree.
Highly Repeated N-Queens Problem: Explain the structural constraints of the N-Queens 4 Times
positioning puzzle using backtracking. Construct the complete,
unambiguous state-space tree to illustrate the classic 4-Queens problem.
ADA (BCS401) — Module-Wise Repeatability Analysis Page 3 of 4
PRIORITY LEVEL QUESTION / CORE CURRICULAR CONCEPT FREQUENCY
Highly Repeated Complexity Classes (P, NP, NPC, NPH): Define, analyze, and compare 3 Times
the underlying computational definitions for fundamental problem classes:
(i) P Problems, (ii) NP Problems, (iii) NP-Complete Problems, and (iv) NP-
Hard Problems. Provide concrete examples for each class.
Low / Non- Branch and Bound vs. Backtracking: Conduct a theoretical comparison 1 Time
Repeated to differentiate the core structural logic, bounding strategies, and tree
traversal schemas of Branch and Bound versus Backtracking techniques.
Low / Non- Decision Trees: Explain the fundamental concept of a sorting decision 1 Time
Repeated tree. Construct a fully branched sorting decision tree for a three-element
insertion sort scenario.
Low / Non- Greedy Approximation for Knapsack: Explain how the greedy 1 Time
Repeated approximation paradigm is adapted to handle or approximate solutions for
the discrete fractional/discrete knapsack optimization problem.
ADA (BCS401) — Module-Wise Repeatability Analysis Page 4 of 4