ALGORITHM DESIGN AND COMPLEXITY OF COMPUTING

1. An ___ is defined as a set of well- 2. The measure of the longest amount of

defined instructions used to accomplish a time possibly taken to complete an
particular task. algorithm is expressed as __.
a. Algorithm a. Little-O
b. Function b. Little-Omega
c. Program c. Big-Omega
d. Procedure d. Big-O
Answer (A) Answer (D)

3. A ___ is a compact, informal, and 4. ___ of an algorithm is the amount of

environment-independent description of time required for it to execute.
a computer programming algorithm. a. Time complexity
a. Stack b. Space complexity
b. Queue c. Compiling time
c. Psuedocode d. Best case
d. Non-linear data structure Answer (A)
Answer (C)

5. Potential function method is the 6. ___ is the maximum amount of time

technique that performs an amortized an algorithm takes to execute a specific
analysis based on ___. set of inputs.
a. Financial model a. Running time
b. Computational model b. Average case time complexity
c. Algorithm analysis c. Worst case time complexity
d. Energy model d. Best case time complexity
Answer (D) Answer (C)

7. ___ within the limit deals with the 8. Which one of the following helps in
behavior of a function for sufficiently calculating the longest amount of time
large values of its parameter. taken for the completion of the
a. Asymptotic notation algorithm?
b. Big-Oh notation a. Theta notation
c. Omega notation b. Big-Oh notation
d. Theta notation c. Omega notation
Answer (A) d. Time complexity
Answer (B)

9. For converting recursive algorithm to 10. The ___ is also known as an escape
non-recursive algorithm, store the values clause which is used to terminate the
of all ___ parameters in the stack. algorithm.
a. Negative a. Recursive step
b. Global b. Recursive function
c. Pass by reference c. Iterative step
d. Pass by value d. Base case
Answer (D) Answer (D)

11. In algorithm visualization of bubble 12. The recursive versions of binary

sort algorithm the non-linear curve of the search use a ___ structure.
sorted elements is close to ___. a. Branch and bound
 ALGORITHM DESIGN AND COMPLEXITY OF COMPUTING

a. 3n b. Dynamic programming
b. n3 c. Divide and conquer
c. 2n d. Simple recursive
d. n2 Answer (C)
Answer (D)

13. ___ are node-based data structures 14. Which method is practical to perform
used in many system programming a single search in an unsorted list of
applications for managing dynamic sets elements?
a. Stack a. Sequential search
b. Queue b. Bubble sort
c. Binary search trees c. Horspool’s method of string matching
d. List d. Brute force method of string matching
Answer (C)
Answer (A)
15. Which algorithm finds the solution for 16. Prim’s algorithm starts constructing a
the single-source shortest path problem minimum spanning tree from ___.
for a tree? a. An arbitary root vertex
a. Prim’s b. The shortest arc
b. Dijkstra’s c. The left most vertex
c. Kruskal’s d. The right most vertex
d. Huffman code Answer (A)
Answer (B)

17. Which method of encoding does not 18. In distribution counting to sorting
consider the probability of occurrence of elements in an array ___ is used.
symbols? a. Accumulated sum of frequencies
a. Static Huffman coding b. Frequency
b. Variable length coding c. Count of repeating elements in the
c. Adaptive Huffman coding array
d. Fixed length coding d. The length of the array
Answer (D) Answer (A)

19. ___ is a concept wherein larger 20. The basic operation of the ___
solutions for problems are found based algorithm is the comparison between the
upon the solution of a number of smaller element and the array given.
problems. a. Binary search
a. Decrease and conquer b. Greedy
b. Divide and conquer c. Brute force
c. Branch and bound d. Insertion sort
d. Backtracking Answer (D)
Answer (A)

21. In ___, one begins at the root of the 22. What is the mode for the following set
tree and then explores along each branch. numbers? 10,12,8,4,10, 6, 10,11,11,10,12
a. Topological sorting a. 11
b. Breadth-first search b. 12
c. Depth-first search c. 10
d. Insertion Sort d. 9
 ALGORITHM DESIGN AND COMPLEXITY OF COMPUTING

Answer (C) Answer (C)

23. ___ is not a balanced search tree. 24. The number of key comparisons in the
a. AVL tree worst case while forming a heap is using
b. Binary tree an array of n elements is ___.
c. Red-black tree a. nlog2(n+1)
d. B-tree b. 2(nlog(n+1))
Answer (B) c. 2(n-1)log2(n+1)
d. 2(n-log2(n+1))
Answer (D)

25. ___ is an optimization technique for 26. The binomial coefficient is

particular classes of backtracking represented as ___.
algorithms that repeatedly solve sub- a. kCn
problems. b. nCk
a. Decrease and conquer c. n+1Ck
b. Dynamic programming d. nCk+1
c. Branch and bound Answer (B)
d. Divide and Conquer
Answer (B)

27. ___ is the technique by which we 28. The root node in the B-Tree technique
make a function perform faster by trading has ___ limit on the number of children?
space for time. a. Lower
a. Divide and conquer b. Upper and Lower
b. Greedy c. Upper
c. Memoization d. No
d. Recursion Answer (C)
Answer (C)

29. The shift table is to be initialized to 30. Each slot of the bucket array in
___ to compute the bad character shift. separate chaining stores ___.
a. The number of matches of the pattern a. Records
with the text b. A pointer to a linked list
b. The number of mismatches occurring c. Hash key values
c. Length of the pattern-1 d. Both b & c
d. Length of the pattern Answer (B)
Answer (D)

31. The best possible value of the problem 32. If we have materials of different
objective, written as a function of the values per unit volume and maximum
state, is called the ___. amounts, the ___ Knapsack problem
a. Value function finds the most valuable mix of materials
b. Control variables that fit in a knapsack of fixed volume.
c. Policy function a. Bounded
d. Principle of Optimality b. Binary
Answer (A) c. 0-1
d. Fractional
Answer (D)

33. We use ___ for finding solutions to 34. With respect to finding the time
 ALGORITHM DESIGN AND COMPLEXITY OF COMPUTING

sub-problems, so as to reduce complexity of Kruskal’s algorithm, which

recalculation. operation keeps track of the parent
a. Backtracking pointer until it reaches the root parent?
b. Recursion a. Makeset
c. Memoization b. Union
d. Branch and bound algorithms c. Find
Answer (C) d. Merge
Answer (C)

35. ___ means calculating the minimum 36. In a decision tree, a node represents a
amount of work required to solve the ___.
problem. a. Input value
a. Upper-bound b. Output value
b. Lower–bound c. Solution
c. Adversary d. Decision
d. Problem reduction Answer (D)
Answer (B)

37. An algorithm that defines every 38. ___ problems include counting of
operation exclusively is called ___ structures of a specific kind and
algorithm. identifying the largest, smallest or
a. NP-hard optimal objects.
b. Deterministic a. Combinatorial
c. Non-deterministic b. Traveling Salesman
d. NP-complete c. Knapsack problem
Answer (B) d. Use cases
Answer (A)

39. ___ is a sequence of data elements 40. organizes details of all candidate
connected to each other where every solutions and discards large subsets of
element has a link field referring to the fruitless candidates by using upper and lower
location of the next element. estimated bounds of the quantity being
optimized.
a. Array
b. Stack a. Approximation algorithms
c. List b. Dynamic programming
d. Queue c. Greedy algorithm
Answer (C) d. Branch and Bound
Answer (D)

41. Which one of the following statements 42. The two main conditions for theta
is true? notation are ___ and___.
a. An algorithm should have one or more a. f(n)=O(g(n)), f(n)≠Θ(g(n))
inputs externally and it should produce b. f(n)>O(g(n)), f(n)=Θ(g(n))
one or more output. c. f(n)≠O(g(n)), f(n)≥Θ(g(n))
b. An algorithm may or may not d. f(n)>O(g(n)), f(n)>Θ(g(n))
terminate after a finite number of steps. Answer (A)
c. To analyze an algorithm means to
determine the number of resources
necessary to execute it.
d. Procedure, function and subroutine are
synonyms for an algorithm.
 ALGORITHM DESIGN AND COMPLEXITY OF COMPUTING

Answer (C)

43. Identify the true and false statements 44. The two primitive operations of the
from the following with respect to function Fact(x) are ___ and ___.
measuring the running time of an a. Indexing an array, comparing two
algorithm. numbers
1. Firstly, recognize the basic operation of b. To check if the value of x is 1, To
an algorithm. multiply x and Fact(x-1)
2. Identifying the basic operation of an c. To check if the value of x is 1, To
algorithm is difficult. multiply x
a. 1-T, 2-F d. To multiply x and Fact(x-1), Compare
b. 1-T, 2-T two numbers
c. 1-F, 2-T
d. 1-F, 2-F Answer (B)

Answer (A)
45. The smoothness rule assumes that 46. In which method of coding does the
T(n) Є Θ(n2) if ___ is a smooth function code of a symbol not depend on the
and ___ is eventually non-decreasing. frequency of occurrence of that symbol?
a. n2, T(n) a. Variable length coding
b. Θ(n2), T(n) b. Fixed length coding
c. T(n), n2 c. Static Huffman coding
d. Θ(n),n d. Adaptive Huffman coding

Answer (A) Answer (B)

47. Which among the following is not a 48. In distribution counting, one array is
reason to perform the empirical analysis? used to store ___ value and another to
a. To check the accuracy of the algorithm. store ___ list of elements.
b. To reduce the use of mathematical a. Frequency, Sorted
analysis and algorithm visualization. b. Distribution, Sorted
c. To compare the efficiencies of different c. Frequency, Unsorted
algorithms working to solve the same d. Sorted, Unsorted
problem.
d. To develop the algorithm’s efficiency Answer (B)
class.

Answer (B)

49. In a knapsack problem, if a set of 50. What describes a set of well-defined

items are given, each with a weight and a instructions used to accomplish a
value, the goal is to find the number of particular software function?
items that ___ the total weight and ___ a. Algorithm
the total value. b. Protocol
a. Minimizes, Minimizes c. Interface
b. Maximizes, Maximizes d. Framework
c. Maximizes, Minimizes
d. Minimizes, Maximizes Answer (A), Explanation: A set of
Answer (D) well-defined instructions used to
accomplish a particular software
function is referred to as an
 ALGORITHM DESIGN AND COMPLEXITY OF COMPUTING

algorithm.

Q1: What is the difference between a graph algorithm and a network

algorithm?

Ans: Graph algorithms are used for analyzing and manipulating data that is structured
as a graph, while network algorithms are used for analyzing and manipulating data that
is structured as a network.

Graph algorithms focus on finding solutions to problems related to the structure of the
graph, such as shortest paths or minimum spanning trees. Network algorithms focus on
optimizing communication between nodes in the network, such as routing protocols or
distributed consensus protocols.

Q2: What is the difference between an algorithm and a program?

Ans: An algorithm is a set of instructions for completing a task, while a program is an

implementation of an algorithm. An algorithm can be written in any language, while a
program must be written in a specific programming language.

Algorithms are often expressed as pseudocode, which is not executable code and cannot
be run on a computer. Programs are executable code and can be run on computers to
perform tasks.

Q3: What is the difference between a algorithm and a software algorithm?

Ans: An algorithm is a set of instructions for solving a problem, while a software

algorithm is an algorithm that has been coded into a computer program.

Software algorithms are used to automate processes and make them more efficient.
They can be used to solve complex problems quickly and accurately.

Q4: How can I choose the right algorithm for a problem?

Ans: First, you should understand the problem and the data available to you. Then,
research different algorithms that may be applicable and consider their strengths and
weaknesses.

Finally, experiment with different algorithms to see which one provides the best results
for your problem. Make sure to document your process so you can easily refer back to it
if needed.

Q5: What are some common algorithm design patterns?

Ans: Common algorithm design patterns include divide and conquer, dynamic
programming, greedy algorithms, and backtracking. Divide and conquer involves
breaking down a problem into smaller subproblems which are then solved
independently.
 ALGORITHM DESIGN AND COMPLEXITY OF COMPUTING

Dynamic programming is an optimization technique that solves subproblems to build

up a solution to the main problem. Greedy algorithms involve making the best decision
at each step in order to reach an optimal solution. Backtracking is a form of recursion
which explores all possible solutions before choosing the best one.

Q6: What is a Turing machine?

Ans: A Turing machine is a theoretical model of computation that was proposed by

Alan Turing in 1936. It consists of an infinite tape, a head which reads and writes
symbols, and a set of instructions that tell the head how to move around the tape. The
Turing machine can be used to solve any problem that can be described using an
algorithm.

Conclusion

This article has provided an overview of Design and Analysis of Algorithms MCQ with
Answers. We have explored the basic concepts, problems and their solutions related to
algorithms to gain a strong understanding of the topic.

Additionally, you can use this information in your day-to-day work as a programmer.