**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

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

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

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

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

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

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

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

^{2}) 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
## No comments:

Post a Comment