(SEM V) THEORY EXAMINATION 2021-22 DESIGN AND ANALYSIS OF ALGORITHM

DESIGN AND ANALYSIS OF ALGORITHM (KCS-503)

B.Tech (Sem V) – Exam Notes & Answers

SECTION A – Short Answer Type (2 Marks Each)

a. Performance Analysis of Algorithm
Algorithm performance is analyzed using best case, average case, and worst case based on input size and operations executed.

b. Time Complexity of Merge Sort
Merge sort follows divide and conquer.                Recurrence: T(n) = 2T(n/2) + O(n)
Time Complexity = O(n log n) in all cases.

c. Left Rotation in Red-Black Tree
Left rotation is used to balance the tree by rotating nodes to the left when right child becomes heavy.

d. Properties of Fibonacci Heap
It supports faster amortized time for operations like insert, decrease-key, and merge. It consists of a collection of heap-ordered trees.

e. Greedy Programming
Greedy algorithms make locally optimal choices at each step to reach a global solution.

f. Convex Hull
Convex hull is the smallest convex polygon that encloses all given points.

g. Floyd-Warshall Algorithm
It finds shortest paths between all pairs of vertices in a weighted graph.

h. Branch and Bound
It systematically explores solution space while pruning branches that cannot give optimal solutions.

i. Randomized Algorithm
Uses random numbers to make decisions and improves expected performance.

j. NP-Complete and NP-Hard
NP-Complete problems are in NP and NP-Hard. NP-Hard problems may not belong to NP.

SECTION B – Descriptive Answers (10 Marks Each)

Recurrence Relations

Using recursion tree and iteration methods, recurrence relations are solved to find time complexity.

Binomial Heap

A binomial heap is a collection of binomial trees.
Decrease-key operation adjusts heap order by swapping nodes upward.
Time complexity = O(log n).

Kruskal’s Algorithm

Kruskal’s algorithm finds Minimum Spanning Tree by selecting edges in increasing order of weight while avoiding cycles.

N-Queens Problem

The N-Queens problem places N queens on an N×N chessboard so that no two queens attack each other. Backtracking is used to solve it.

Rabin-Karp Algorithm

Uses hashing to match patterns efficiently. Spurious hits occur when hash values match but strings differ.

SECTION C – Long Answer Type

Merge Sort Example

Steps include dividing the list and merging sorted sublists until fully sorted.

Stable vs Unstable Sorting

Stable sorting preserves order of equal elements; unstable does not. Heap sort is unstable.

Red-Black Tree Insertion

Insertion maintains tree properties using recoloring and rotations.

Skip List

A probabilistic data structure allowing fast search, insert, and delete operations.

Fractional Knapsack Problem

Solved using greedy method by selecting items based on value/weight ratio.

Bellman-Ford Algorithm

Finds shortest path from single source and handles negative weights.
Time complexity = O(VE).

Travelling Salesman Problem (TSP)

TSP finds minimum cost tour visiting all cities exactly once. Branch and Bound reduces search space.

Hamiltonian Cycle

Backtracking checks all possible paths to find Hamiltonian cycle.

Vertex Cover Approximation Algorithm

Finds near-optimal vertex cover using greedy approach.

Knuth-Morris-Pratt (KMP) Algorithm

Uses prefix table to avoid re-matching characters.              Time complexity = O(n + m).