Analysis and Design of Algorithm Question bank with objective type

Objective Type Questions:

1. The time complexity of an algorithm quantifies the amount of time taken by an algorithm to run according to ____.

a. number of space                                                                                              b. number of inputs

c. number of outputs                                                                                          d. number of characters

2. Which is not a criterion of algorithm design?

a. Finiteness                                                                                                         b. Durability        

c. Definiteness                                                                                                     d. Efficient

3. What is the full form of RAM model?

a. Ready Action Machine                                                                                   b. Random Access Memory

c. Random Access Machine                                                                              d. None of these

4. Two main measures for the efficiency of an algorithm are

a. Processor and memory                                                                                 b. Complexity and capacity
c. Time and space                                                                                               d. Data and space

5. The time factor when determining the efficiency of algorithm is measured by

a. Counting microseconds                                                                                 b. Counting the number of key operations
c. Counting the number of statements                                                            d. Counting the kilobytes of algorithm

6. The space factor when determining the efficiency of algorithm is measured by

a. Counting the maximum memory needed by the algorithm
b. Counting the minimum memory needed by the algorithm
c. Counting the average memory needed by the algorithm
d. Counting the maximum disk space needed by the algorithm

7. Which of the following case does not exist in complexity theory

a. Best case                                                                                                           b. Worst case
c. Average case                                                                                                    d. Null case

8. The Worst case occur in linear search algorithm when

a. Item is somewhere in the middle of the array
b. Item is not in the array at all
c. Item is the last element in the array
d. Item is the last element in the array or is not there at all

9. The Average case occur in linear search algorithm

a. When Item is somewhere in the middle of the array
b. When Item is not in the array at all
c. When Item is the last element in the array
d. When Item is the last element in the array or is not there at all

10. The complexity of the average case of an algorithm is

a. Much more complicated to analyze than that of worst case
b. Much more simpler to analyze than that of worst case
c. Sometimes more complicated and some other times simpler than that of worst case
d. None or above

11. O-notation provides an asymptotic

a. upper bound                                                                                                     b. lower bound

c. light bound                                                                                                       d. none of these

12. An algorithm lacks which of these features?

a. computes a function                                                                                       b. is deterministic

c. may take an unreasonably long time                                                          d. works in discrete steps

13. Algorithms solve problems that are associated with

a. services                                                                                                             b. protocols

c. irrational numbers                                                                                         d. functions

14. Input to an algorithm is

a. necessarily atomic                                                                                         b. obtained before algorithm execution

c. obtained during execution                                                                            d. necessarily compound

15. An algorithm is a(n)

a. program                                                                                                            b. plan

c. structure                                                                                                           d. service.

16. The running time of insertion sort is

a. O(n²)                                                                                                                  b. O(n)

c. O(logn)                                                                                                              c. O(nlogn)

17. The way a card game player arranges his cards as he picks them one by one can be compared to

a. Quick sort                                                                                                         b. Merge sort

c. Insertion sort                                                                                                   d. Bubble sort

18. Which among the following is the best when the list is already sorted?

a. Selection sort                                                                                                   b. Merge sort

c. Insertion sort                                                                                                   d. Bubble sort

Short Answer Type:

1. Explain asymptotic notation.

2. Write the pseudo code for insertion sort and analyze time complexity for best case.

3. What are the criteria of algorithm, define them?

4. Solve the recurrence relation using substitution method: T(n)=T(n-1)+1

5. Solve recurrence relation using Master method: T(n)=2T(n/2)+n

6. What are the basic points should be in mind to analyze an algorithm?

7. Write Master method and all three cases?

8. Write about all three case analyses.

9. Write definition of Time complexity, Space complexity and I/O complexity.

Long Answer Type:

1. List all the algorithm design strategies; explain any two, with example.

2. Solve recurrence relation using substitution: T(n)=2T(n/2)+n

3. What are the important points to cover to writing or designing of an algorithm?

4. Write the case study of the analysis of Insertion sort algorithm.

5. Solve the recurrence relation:

a. T(n)=3T(n/3)+1                                                                                              b. T(n)=T(n-1)+1/n

6. Short notes:

a. Big Oh!                                                              b. Worst Case Analysis                                                      c. Definition of Algorithm