Design and Analysis of Algorithms (DAA)

Master Paper
SECTION A: SHORT ANSWER QUESTIONS
Unit I: Introduction, Sorting, and Order Statistics
1. With an example, define an algorithm.

An algorithm is a finite sequence of well-defined instructions to solve a problem. For

example, a recipe to bake a cake is an algorithm.

2. Discuss the basic steps in the complete development of an algorithm.

1. Problem Definition: Understand the problem.

2. Algorithm Design: Choose a strategy and outline the steps.
3. Specification: Formally describe the algorithm (e.g., pseudocode).
4. Analysis: Determine time and space complexity.
5. Implementation: Write the code.
6. Testing: Verify correctness with various inputs.
7. Maintenance: Update as needed.
3. Explain how an algorithm's performance is analyzed and what is the importance of
average case analysis.

Performance is analyzed by its time complexity (execution time) and space complexity
(memory usage). Average case analysis is important because it measures an algorithm's
performance on typical, real-world inputs, providing a more realistic prediction than worst-
case or best-case scenarios.

4. What is asymptotic notation? Explain Big O and Omega (Ω) notations in brief.

Asymptotic notation describes the limiting behavior of a function.

● Big O (O): Represents the upper bound or worst-case time complexity.
● Omega (Ω): Represents the lower bound or best-case time complexity.
5. What do you understand by a stable sort?

A stable sorting algorithm maintains the original relative order of elements with equal values.

6. Derive the time complexity of Heap Sort.

Heap Sort consists of two main operations: building a max heap, which takes time, and
repeatedly extracting the maximum element and heapifying the rest, which takes for each of
the elements. This results in a total time complexity of .

7. Derive the time complexity of Merge sort.

Merge Sort follows the recurrence relation . Solving this using the Master Theorem or a
recursion tree shows that the work done at each of the levels is . Thus, the total time
complexity is .

Unit II: Advanced Data Structures

1. Explain left rotation in a Red-Black tree.

A left rotation is an operation that reorganizes nodes to maintain the tree's properties. It
pivots around a node x and its right child y, making y the new parent of x while preserving the
binary search tree order.

2. Write down the properties of B-Trees.

● All leaves are at the same level.
● Every node (except the root) is at least half-full.
● The root has at least two children (unless it's a leaf).
● An internal node with k children has k-1 keys.
● Keys in a node are sorted.

SECTION B: MEDIUM ANSWER QUESTIONS

Unit I: Introduction, Sorting, and Order Statistics
1. What is a recurrence relation? Explain how a recurrence is solved using the master's
theorem.
2. Solve the following recurrence using the recursion tree method: .
3. Solve the following recurrence relations:
a. T(n)=T(n−1)+n4
b. T(n)=T(n/4)+T(n/2)+n2
4. Write an algorithm for Insertion Sort and find its time complexity in all cases (best,
average, and worst).

SECTION C: LONG ANSWER QUESTIONS

Unit I: Introduction, Sorting, and Order Statistics
1. Write the Quick Sort algorithm and its partition algorithm. Drive the best and worst-case
time complexity of Quick Sort. Sort the sequence (25, 57, 48, 36, 12, 91, 86, 32) using this
method.
2. Write the Merge Sort algorithm. Illustrate the operation of Merge Sort on the array and
derive its time complexity.
3. Explain what you understand by stable and unstable sorting. Sort the following sequence
(25, 57, 48, 36, 12, 91, 86, 32) using Heap Sort.
4. Explain the algorithm for Counting Sort. Illustrate its operation on the array: .

Unit II: Advanced Data Structures

1. Discuss the various cases for insertion of a key in a Red-Black Tree. Illustrate the
insertion process for the sequence of keys {15, 13, 12, 16, 19, 23, 5, 8} into an empty Red-
Black Tree.
2. Perform the insertion operation using the keys F, S, Q, K, C, L, H, T, V, W, M, R, N, P, A, B
in order into an empty B-tree where the minimum degree, t, is 3.