(SEM V) THEORY EXAMINATION 2020-21 DESIGN AND ANALYSIS OF ALGORITHM

SECTION A (Any 2 Questions Explained Briefly)
 

What is asymptotic notation? Explain Ω (Omega) notation.
Asymptotic notation is used to describe the performance of an algorithm in terms of time or space as input size grows. Omega (Ω) notation represents the lower bound of an algorithm, which means it shows the minimum time an algorithm will take in the best case or under ideal conditions.
 

What is recurrence relation?
A recurrence relation is an equation that defines the running time of a recursive algorithm in terms of smaller input sizes. It helps analyze divide and conquer algorithms by expressing the problem size reduction and combining cost.
 

SECTION B (Any 2 Questions Explained)
 

Explain the greedy approach using activity selection problem.
The greedy approach builds a solution step by step by choosing the locally optimal choice at each stage. In the activity selection problem, activities are selected based on earliest finish time to maximize the number of non-overlapping activities. This approach is efficient and produces an optimal solution.
 

Explain KMP algorithm for string matching.
The Knuth–Morris–Pratt (KMP) algorithm is used for efficient string matching. It avoids unnecessary comparisons by using a prefix table that stores information about previously matched characters. This reduces time complexity compared to the naïve string matching algorithm.
 

SECTION C (Any 2 Questions Explained)
 

Solve recurrence using Master’s Theorem.
Master’s theorem provides a direct method to solve recurrence relations of the form T(n)=aT(n/b)+f(n). By comparing f(n) with n^(log b a), the time complexity can be determined without expanding the recurrence fully.
 

Explain insertion sort and its time complexity.
Insertion sort is a simple sorting algorithm that builds the sorted list one element at a time by inserting elements in their correct position. Its best-case time complexity is O(n), while average and worst-case time complexity is O(n²). It is efficient for small datasets.
 

Most Questions in This PDF Are Related To
 

Most questions in the Design and Analysis of Algorithm (KCS-503) paper are related to time and space complexity analysis, recurrence relations, sorting and searching algorithms, greedy techniques, divide and conquer, dynamic programming, graph algorithms (MST, shortest path), backtracking, NP-complete problems, and approximation algorithms. The paper mainly focuses on algorithm design techniques and performance analysis.