(SEM V) THEORY EXAMINATION 2024-25 DESIGN AND ANALYSIS OF ALGORITHM

Subject Code: BCS503
Maximum Marks: 70
Time: 3 Hours
Paper ID: 310680

Question Paper Overview

SECTION A (2 × 7 = 14 Marks)

(Short-answer questions — conceptual & definition-based)

a. Define an algorithm with an example. List a few algorithm design techniques.
b. Discuss the basic steps taken to design an algorithm.
c. Derive the time complexity of Heap Sort.
d. List the properties of a Binomial Heap.
e. With an example, explain the Convex Hull Problem.
f. Explain the concept of Branch and Bound with an example.
g. Describe Randomized Algorithms and list a few examples.

SECTION B (Attempt any three × 7 = 21 Marks)

a. Merge Sort: Illustrate the operation of Merge Sort on the array
A = (38, 27, 43, 3, 9, 82, 10) and derive its time complexity.
b. Define Binomial Heap. Write an algorithm for union of two Binomial Heaps and illustrate with an example.
c. Apply the Greedy Single Source Shortest Path Algorithm (Dijkstra’s Algorithm) on the given graph:

      (4)   1 ----- 4  / \     / 2   3 - 2 (2) (3) (1)

d. Write Floyd’s and Warshall’s Algorithms for all-pairs shortest paths and discuss their time complexity.
e. Explain the Vertex Cover Problem and solve it using an Approximation Algorithm.

SECTION C (Attempt one part from each question × 7 = 35 Marks)

Q3

(a) Write the Quick Sort Partition Algorithm and derive best- and worst-case complexities.
OR
(b) Find Upper, Lower, and Average bounds for f(n)=3n+2f(n) = 3n + 2f(n)=3n+2.

Q4

(a) Insert the following strings in an initially empty Trie:
DOG, DONE, CAT, CAN, RIGHT, DO, JUG, DAA, CA, CAME.
Also construct its Compressed Trie.
OR
(b) Design a Binomial Heap for
A = {7, 2, 4, 17, 1, 11, 6, 8, 15, 10, 20}.

Q5

(a) Write and explain Kruskal’s Algorithm to find the Minimum Spanning Tree (MST) with an example.
OR
(b) Solve the Fractional Knapsack Problem with
n=7n = 7n=7, m=15m = 15m=15.

Q6

(a) Illustrate the N-Queens Problem and draw the State Space Tree for a 4-Queens solution using backtracking.
OR
(b) Find the optimal solution of 0/1 Knapsack with
n=4,m=8n = 4, m = 8n=4,m=8, P={1,2,5,6},W={2,3,4,5}P = \{1, 2, 5, 6\}, W = \{2, 3, 4, 5\}P={1,2,5,6},W={2,3,4,5}.

Q7

(a) Explain P, NP, NP-Complete, and NP-Hard complexity classes and show how they are related.
OR
(b) Write the Knuth-Morris-Pratt (KMP) string matching algorithm and compute the prefix function π for the pattern:

ababbabbabbababbabb 

where the alphabet Σ = {a, b}.

Key Topics for Revision

1. Algorithm Design Techniques

Divide and Conquer: Merge Sort, Quick Sort.

Greedy Method: Kruskal’s, Prim’s, Dijkstra’s, Fractional Knapsack.

Dynamic Programming: Floyd-Warshall, 0/1 Knapsack.

Backtracking: N-Queens, Hamiltonian Cycle.

Branch and Bound: Travelling Salesman, Knapsack optimization.

2. Heap Sort

Complexity:                                                    Build Heap: O(n)

Deletion (n log n) → Total: O(n log n)            Steps: Build max-heap → extract largest → rebuild heap.

3. Binomial Heap

Properties:

Each Binomial Tree BkB_kBk​ has 2k2^k2k nodes.

Root degree = k; children are roots of B0,B1,...,Bk−1B_0, B_1, ..., B_{k-1}B0​,B1​,...,Bk−1​.

Operations: Union, Insertion, Extract-Min.

4. Convex Hull Problem

Smallest convex polygon containing all points.   Algorithms: Graham’s Scan (O(n log n)), Jarvis March.

5. Branch and Bound

Systematically explores decision trees.                Applications: Knapsack, Travelling Salesman Problem.

Uses upper/lower bound estimation to prune suboptimal solutions.

6. Randomized Algorithms

Use randomness for decision-making.

Examples: Randomized Quick Sort, Monte Carlo methods, Randomized Primality Testing.

7. Shortest Path Algorithms

Dijkstra’s: Single source, non-negative weights.    Floyd–Warshall: All-pairs shortest path, O(n³) time.

8. Knapsack Problems

9. N-Queens Problem

Place N queens on an N×N board so that no two attack each other.

Solved using Backtracking with recursive state-space exploration.

10. Complexity Classes

11. KMP Algorithm

Improvement over brute force string matching.

Builds prefix table (π) to skip unnecessary comparisons.

Time Complexity: O(n + m).