Question 1

Define Recurrence Relation.

Accepted Answer

A recurrence relation defines a sequence where each term is a function of one or more previous terms.

Question 2

What is Space Complexity?

Accepted Answer

Space Complexity is the amount of memory an algorithm uses as a function of input size.

Question 3

Define Heap.

Accepted Answer

A Heap is a complete binary tree satisfying the heap property: max-heap (parent ≥ children) or min-heap (parent ≤ children).

Question 4

What is Amortized Analysis?

Accepted Answer

Amortized Analysis determines the average cost per operation over a sequence of operations, smoothing out expensive occasional operations.

Question 5

Define Graph Traversal.

Accepted Answer

Graph traversal is the process of visiting all vertices in a graph in a systematic manner, either using BFS or DFS.

Question 6

What is Optimal Substructure?

Accepted Answer

Optimal Substructure means the optimal solution to a problem contains optimal solutions to its subproblems.

Question 7

Define Branch and Bound.

Accepted Answer

Branch and Bound is an algorithm design paradigm that systematically enumerates candidate solutions while using bounds to prune suboptimal branches.

Question 8

What is a Randomized Algorithm?

Accepted Answer

A Randomized Algorithm uses random numbers to make decisions during execution, giving good expected performance.

Question 9

Define Approximation Algorithm.

Accepted Answer

An Approximation Algorithm finds near-optimal solutions to NP-Hard optimization problems in polynomial time with a guaranteed performance ratio.

Question 10

What is Floyd-Warshall Algorithm?

Accepted Answer

Floyd-Warshall Algorithm finds shortest paths between all pairs of vertices in a weighted graph, including negative edges (but no negative cycles).

Question 11

Explain Heap Sort algorithm and its time complexity.

Accepted Answer

Heap Sort uses a max-heap to sort in O(n log n) time in-place with O(1) extra space.

Question 12

Describe Prim's Algorithm for Minimum Spanning Tree with an example.

Accepted Answer

Prim's algorithm grows the MST from a starting vertex by repeatedly adding the minimum-weight edge connecting the tree to a new vertex.

Question 13

Explain the activity selection problem using the Greedy approach.

Accepted Answer

The Activity Selection Problem greedily selects the maximum number of non-overlapping activities by always picking the activity that finishes earliest.

Question 14

Discuss the Longest Common Subsequence (LCS) problem using Dynamic Programming.

Accepted Answer

LCS finds the longest subsequence common to two sequences using DP with a 2D table, running in O(mn) time.

Question 15

Explain the concept of Graph Coloring and Hamiltonian Cycle.

Accepted Answer

Graph Coloring assigns colors to vertices so no adjacent vertices share a color. Hamiltonian Cycle visits every vertex exactly once and returns to start.

Question 16

Describe the Subset Sum problem using Backtracking.

Accepted Answer

Subset Sum problem finds subsets summing to a target value using backtracking to prune invalid branches early.

Question 17

Explain the concept of String Matching algorithms (Naive and KMP).

Accepted Answer

Naive string matching scans all positions in O(nm) time; KMP uses a failure function to skip redundant comparisons in O(n+m) time.

Question 18

(a) Explain the Strassen's Matrix Multiplication algorithm in detail.

Accepted Answer

Strassen's algorithm multiplies two n×n matrices in O(n^2.807) using 7 recursive multiplications instead of the conventional 8, reducing asymptotic complexity.

Question 19

(a) Explain the All-Pairs Shortest Path problem using the Floyd-Warshall algo…

Accepted Answer

Floyd-Warshall solves All-Pairs Shortest Path in O(V³) using DP by iteratively considering each vertex as an intermediate node.

Question 20

(a) Explain the concept of Huffman Coding using the Greedy approach.

Accepted Answer

Huffman Coding is a greedy optimal prefix-free encoding that assigns shorter codes to more frequent characters, minimizing total encoded length.

Question 21

Explain the concept of Dynamic Programming in detail. Solve the 0/1 Knapsack …

Accepted Answer

Dynamic Programming solves optimization problems with overlapping subproblems and optimal substructure. 0/1 Knapsack and Coin Change are classic DP problems solved with 2D and 1D tables respectively.

Question 22

(a) Explain the concept of Approximation Algorithms.

Accepted Answer

Approximation algorithms provide polynomial-time solutions with guaranteed quality bounds for NP-Hard problems. Vertex Cover has a 2-approximation; TSP has a 2-approximation for metric instances.

Design and Analysis of Algorithms