Analysis and Design of Algorithm Question Bank

Objective Type Questions:

1. The complexity of linear search algorithm is

a. O(n)                                                   b. O(log n)                                            c. O(n²)                                                  d. O(n log n)

2. The complexity of Binary search algorithm is

a. O(n)                                                   b. O(log n )                                           c. O(n²)                                                  d. O(n log n)

3. The complexity of merge sort algorithm is

a. O(n)                                                   b. O(log n)                                            c. O(n²)                                                  d. O(n log n)

4. Matrix multiplication by brute force requires

a. O(n) time                                          b. O(1) time                                          c. O(log n) time                                   d. nested loops

5. The linear search is what kind of algorithm?

a. divide and conquer                         b. greedy                                               c. brute force                                        d. dynamic programming

6. What is the running time of a brute-force algorithm that tells whether an array is sorted?

a. O(logn)                                              b. O(n)                                                   c. O(n log n)                                         d. O(n²)

7. Selection sort is O(___)

a. 1                                                          b. lg n                                                     c. n                                                          d. n²

8. Selection sort uses

a. divide and conquer                         b. brute force                                        c. the greedy approach                       d. dynamic programming

9. How many multiplication performed by Strassen’s algorithm for matrix multiplication?

a. 8                                                          b. 9                                                         c. 11                                                       d. 7

10. What is the time complexity to add two matrix of n x n?

a. O(n²)                                                  b. O(n log n)                                         c. O(n)                                                   d. O(logn)

Short Answer Type:

1. Write algorithm for selection sort and explain.

2. Write algorithm for sequential search and explain.

3. Write pseudo code for merge sort and explain.

4. Write pseudo code for quick sort and explain.

5. Write pseudo code for binary search and explain.

6. Explain what divide-and-conquer strategy is.

7. Write the C programming logic for matrix multiplication in brute force technique.

8. What is brute force method for algorithm designing.

Long Answer Type:

1. Write the parametric equations given by Strassen’s method for Matrix Multiplication for sum matrix, product matrix and resultant matrix. Determine its time complexity.

2. Multiply below matrices using Strassen’s algorithm.

A=2   3                   B= 4   5

     3   5                         6   8

3. Write Strassen’s algorithm for Matrix Multiplication.

4. Short notes:

a. Selection sort                                   b. Sequential search                            c. Binary search                                   d. Merge sort

5. Explain the rationale and algorithm for partition of quick sort.

6. Write problem statement, rationale, parameter and algorithm for merge sort.