DAA Review Questions

This section contains important Design and Analysis of Algorithms (DAA) review questions covering algorithm analysis, asymptotic notations, divide and conquer, sorting algorithms, recurrence relations, heaps, Red-Black Trees, B-Trees and Tries.

These questions are useful for B.Tech, AKTU examinations, university examinations, viva preparation and DAA revision. Each question is followed by a detailed explanation and, wherever required, suitable examples, pseudocode and step-by-step solutions.

Index – Review Questions

Question 1: What is an Algorithm? Explain the characteristics of a good algorithm.

Answer

An algorithm is a finite sequence of well-defined and unambiguous steps used to solve a particular problem or to perform a particular task. An algorithm accepts input, processes it according to a defined procedure and produces the required output.

For example, an algorithm for finding the largest number in an array examines the elements one by one and keeps track of the largest element found so far.

Characteristics of a Good Algorithm

1. Input: An algorithm may accept zero or more inputs.
2. Output: It should produce at least one clearly defined output.
3. Definiteness: Every step must be precise and unambiguous.
4. Finiteness: The algorithm must terminate after a finite number of steps.
5. Effectiveness: Every operation should be basic enough to be performed in a finite amount of time.
6. Correctness: The algorithm should produce the correct result for valid inputs.
7. Efficiency: It should use reasonable amounts of time and memory.

Question 2: What is the difference between Time Complexity and Space Complexity?

Answer

Algorithm efficiency is generally measured using time complexity and space complexity.

Time Complexity

Time complexity represents the amount of computational work performed by an algorithm as the input size n increases.

It is generally represented using asymptotic notation such as O(n), O(n²) or O(log n).

Space Complexity

Space complexity represents the amount of memory required by an algorithm as a function of the input size.

Auxiliary space refers to the extra memory used by the algorithm apart from the input data.

Example

for(i = 0; i < n; i++)
{
    printf("%d", i);
}

The loop executes n times. Therefore its time complexity is O(n). If only a fixed number of variables are used, the auxiliary space complexity is O(1).

Question 3: What are Asymptotic Notations? Explain Big-O, Big-Ω and Big-Θ.

Answer

Asymptotic notation is used to describe the growth rate of an algorithm when the input size becomes very large. It ignores constants and lower-order terms.

1. Big-O Notation

Big-O represents an upper asymptotic bound.

If:

then f(n) does not grow faster than a constant multiple of g(n), for sufficiently large values of n.

Example:

2. Big-Ω Notation

Big-Ω represents a lower asymptotic bound.

3. Big-Θ Notation

Big-Θ represents a tight asymptotic bound. A function is Θ(g(n)) when it is both O(g(n)) and Ω(g(n)).

Question 4: Explain the Divide and Conquer technique with suitable examples.

Answer

Divide and Conquer is an algorithm design technique in which a large problem is divided into smaller subproblems. The smaller problems are solved and their results are combined to obtain the final solution.

Three Main Steps

1. Divide: Divide the original problem into smaller subproblems.
2. Conquer: Solve the subproblems recursively.
3. Combine: Combine the solutions of the subproblems.

Examples

• Merge Sort
• Quick Sort
• Binary Search

For example, Merge Sort divides an array into two halves, recursively sorts both halves and then merges the sorted halves.

Therefore:

Question 5: What is the difference between Greedy Method and Dynamic Programming?

Answer

Both Greedy Method and Dynamic Programming are important algorithm design techniques. They are used for optimization problems but approach the problem differently.

Greedy Method

The greedy method makes the locally best choice at every step with the intention of obtaining a globally optimal solution.

Examples:

• Kruskal's Algorithm
• Prim's Algorithm
• Dijkstra's Algorithm for non-negative edge weights

Dynamic Programming

Dynamic Programming divides a problem into overlapping subproblems and stores their solutions so that they are not calculated repeatedly.

Examples:

• 0/1 Knapsack
• Matrix Chain Multiplication
• Longest Common Subsequence

Question 6: Define time complexity and space complexity of an algorithm.

Answer

Time complexity is the asymptotic measure of the number of basic operations performed by an algorithm as a function of input size n.

Space complexity is the asymptotic measure of the memory required by an algorithm as a function of n.

Example

sum = 0;

for(i = 0; i < n; i++)
{
    sum = sum + A[i];
}

The loop executes n times, so the time complexity is Θ(n). Only a few additional variables are used, so the auxiliary space complexity is Θ(1).

Question 7: Explain little-oh (o) and little-omega (ω) notations.

Answer

Little-o Notation

Little-o describes a function that grows strictly slower than another function.

If the limit exists:

Example:

Little-Omega Notation

Little-omega describes a function that grows strictly faster than another function.

Example:

Thus, little-o and little-omega indicate strict asymptotic separation, whereas Big-O and Big-Ω allow equality in asymptotic order.

Question 8: List the properties of a Binomial Heap and state the maximum number of Binomial Trees it can contain for n nodes.

Answer

A Binomial Heap is a collection of binomial trees satisfying the heap-order property.

Properties of Binomial Heap

1. There is at most one binomial tree of any particular degree.
2. Every binomial tree satisfies the heap-order property.
3. A binomial tree B_k contains 2^k nodes.
4. A B_k tree has degree k.
5. The roots are normally maintained in increasing order of degree.

The number of binomial trees corresponds to the number of 1s in the binary representation of n.

Therefore, the maximum number of binomial trees that a binomial heap can contain is:

For example, if n = 13:

Therefore, the heap contains B₃, B₂ and B₀.

Question 9: State the best-case and worst-case time complexity of Quick Sort. Name one in-place and one non-in-place sorting algorithm.

Answer

Quick Sort is a divide-and-conquer sorting algorithm. Its performance depends strongly on the choice of pivot.

The worst case occurs when the pivot repeatedly creates highly unbalanced partitions, such as sizes 0 and n−1.

In-Place Sorting

Quick Sort is a common example of an in-place sorting algorithm.

Non-In-Place Sorting

Merge Sort is a common example because its standard array implementation requires additional Θ(n) storage.

Question 10: Arrange the following functions in increasing order of growth rate.

Question

Arrange:

Answer

The increasing order is:

Justification

Logarithmic functions grow more slowly than polynomial functions. Among polynomial functions, a smaller exponent grows more slowly. Exponential functions such as 2ⁿ eventually grow faster than any fixed-degree polynomial.

Diagrammatic Comparison

Two functions can be compared by plotting their values against n on the same graph. The function whose curve increases more rapidly for large values of n has the higher asymptotic growth rate.

Question 11: Explain best, average and worst-case analysis. Determine the bounds for f(n) = 5n² + 3n + 7.

Answer

Best Case

Best-case analysis determines the minimum amount of work required by an algorithm for inputs of size n.

Worst Case

Worst-case analysis determines the maximum amount of work required for inputs of size n.

Average Case

Average-case analysis determines the expected performance over inputs according to a specified probability distribution.

Example – Linear Search

• Best case: element found at first position → Θ(1)
• Worst case: element at last position or absent → Θ(n)
• Average case: expected linear number of comparisons under the usual uniform-position assumption → Θ(n)

Bounds of 5n² + 3n + 7

The dominant term is 5n². Constants and lower-order terms are ignored for asymptotic analysis.

Question 12: Write the pseudo-code of Heap Sort and illustrate it on A = {19, 4, 31, 12, 8, 27, 45, 6}.

Answer

Heap Sort uses a binary heap to sort the elements. For ascending order, a Max Heap is generally used.

Heap Sort Pseudocode

HEAPSORT(A)

BUILD-MAX-HEAP(A)

for i = length(A) downto 2
    exchange A[1] and A[i]
    heap-size = heap-size - 1
    MAX-HEAPIFY(A, 1)

Complexity

Given Array

After constructing a Max Heap, one possible heap representation is:

Repeatedly remove the maximum element and restore the heap property. Finally, the sorted array is:

In-Place Sorting

An in-place sorting algorithm rearranges the elements using only a small amount of additional memory apart from the input array.

Question 13: Analyze Quick Sort comparisons for the given inputs.

Question

Quick Sort uses the last element as pivot.

Find t₁ and t₂ for:

Answer

First Input

Input:

The last element 1 is selected as pivot. It is compared with the other four elements.

Therefore:

Second Input

First pivot = 2. It requires 4 comparisons. The remaining right partition is {3,5,4}. Pivot = 4 requires 2 further comparisons.

Quick Sort Pseudocode

QUICKSORT(A, p, r)

if p < r
    q = PARTITION(A, p, r)
    QUICKSORT(A, p, q - 1)
    QUICKSORT(A, q + 1, r)

Partition Procedure

PARTITION(A, p, r)

x = A[r]
i = p - 1

for j = p to r - 1
    if A[j] <= x
        i = i + 1
        exchange A[i] and A[j]

exchange A[i + 1] and A[r]

return i + 1

Recurrence

Question 14: Explain Red-Black Tree insertion and insert 61, 58, 51, 32, 39, 29.

Answer

A Red-Black Tree is a self-balancing binary search tree in which every node is assigned either a red or black color.

Insertion Cases

1. If the parent of the inserted node is black, no violation occurs.
2. If the parent is red and the uncle is red, recolor the parent and uncle black and the grandparent red.
3. If the parent is red and the uncle is black and the node forms a triangle, perform a rotation at the parent.
4. If the parent is red and the uncle is black and the node forms a line, rotate at the grandparent and recolor the nodes.

The root is always made black after insertion.

Insertion Sequence

After applying the standard Red-Black Tree insertion rules, the final tree is:

             39(B)
            /     \
        32(R)     58(R)
        /         /   \
     29(B)     51(B) 61(B)

Here B represents Black and R represents Red.

Question 15: State the height bound and properties of a B-Tree. Construct the B-Tree for t = 3.

Answer

A B-Tree is a balanced multiway search tree commonly used in databases and file systems.

Height Bound

For a B-Tree of minimum degree t and n keys, the height grows logarithmically with n:

Important Properties

• Keys inside every node are stored in sorted order.
• All leaves are at the same level.
• Every non-root node contains at least t−1 keys.
• Every node contains at most 2t−1 keys.
• An internal node can have between t and 2t children.
• The root has at least one key.

For t = 3

Minimum number of keys in a non-root node:

Maximum number of keys:

Insertion

Keys:

Using standard B-Tree insertion and splitting full nodes when necessary, the final tree can be represented as:

                 [36]
                /    \
 [12,18,24,30]        [48,60,72,84,96]

Question 16: Apply Merge Sort to {38, 27, 43, 3, 9, 82, 10, 15}.

Answer

Divide Step

Merge Step

Final Merge

Recurrence Relation

At every level of the recursion tree, the total merging work is Θ(n). There are log₂n levels. Therefore:

Question 17: Explain Binomial Heap for n = 13 and compare it with Fibonacci Heap.

Answer

A Binomial Heap is a collection of binomial trees satisfying the heap-order property.

Binary Representation of 13

Therefore:

Since a B_k tree contains 2^k nodes, the heap contains:

• B₃ → 8 nodes
• B₂ → 4 nodes
• B₀ → 1 node

Binomial Heap vs Fibonacci Heap

Question 18: Solve the following recurrence relations.

(i) T(n) = 8T(n/2) + n²

Using Master's Theorem

Compare the recurrence with:

Here:

Calculate:

Since n² is polynomially smaller than n³, Master's Theorem Case 1 applies.

(ii) T(n) = T(n−1) + n³

Expand the recurrence:

Continuing until the base case gives:

Since the sum of cubes up to n is Θ(n⁴):

Comparison

Question 19: Explain the Trie data structure and construct a Trie for the given strings.

Question

Insert:

Answer

A Trie, also called a prefix tree, is a tree-based data structure used for storing and searching strings efficiently.

Each edge represents a character. Common prefixes are stored only once. A terminal marker is used to indicate that a complete word ends at a particular node.

Trie Construction

ROOT
 |
 +-- B
 |   |
 |   +-- A
 |   |   |
 |   |   +-- T*
 |   |   |   |
 |   |   |   +-- H*
 |   |   |
 |   |   +-- L
 |   |   |   |
 |   |   |   +-- L*
 |   |   |
 |   |   +-- S
 |   |   |   |
 |   |   |   +-- E*
 |   |   |
 |   |   +-- N
 |   |   |   |
 |   |   |   +-- D*
 |   |   |
 |   |   +-- G*
 |   |
 |   +-- E*
 |       |
 |       +-- A
 |       |   |
 |       |   +-- T*
 |       |
 |       +-- E*
 |
 +-- D
     |
     +-- O
         |
         +-- G*

Here * indicates the end of a complete word.

Number of Nodes

Counting the root and every distinct prefix node gives:

Important DAA Topics Covered

• Algorithm and characteristics of algorithms
• Time and Space Complexity
• Asymptotic Notations
• Big-O, Big-Ω and Big-Θ
• Little-o and Little-ω
• Growth of Functions
• Best, Average and Worst Case Analysis
• Divide and Conquer
• Greedy Method
• Dynamic Programming
• Quick Sort
• Merge Sort
• Heap Sort
• Recurrence Relations
• Master's Theorem
• Binomial Heap
• Fibonacci Heap
• Red-Black Tree
• B-Tree
• Trie