Design and Analysis of Algorithms MCQ with Answers

1. An ___ is defined as a set of well-defined instructions used to accomplish a particular task.

a. Algorithm

b. Function

c. Program

d. Procedure

Ans: A

2. The measure of the longest amount of time possibly taken to complete an algorithm is expressed as
__.

a. Little-O

b. Little-Omega

c. Big-Omega

d. Big-O

Ans: D

3. A ___ is a compact, informal, and environment-independent description of a computer programming

algorithm.

a. Stack

b. Queue

c. Psuedocode

d. Non-linear data structure

Ans: C

4. ___ of an algorithm is the amount of time required for it to execute.

a. Time complexity

b. Space complexity

c. Compiling time

d. Best case

Ans: A

5. Potential function method is the technique that performs an amortized analysis based on ___.

a. Financial model

b. Computational model

c. Algorithm analysis

d. Energy model

Ans: D

6. ___ is the maximum amount of time an algorithm takes to execute a specific set of inputs.

a. Running time

b. Average case time complexity

c. Worst case time complexity

d. Best case time complexity

Ans: C

7. ___ within the limit deals with the behavior of a function for sufficiently large values of its parameter.

a. Asymptotic notation

b. Big-Oh notation

c. Omega notation
d. Theta notation

Ans: A

8. Which one of the following helps in calculating the longest amount of time taken for the completion
of the algorithm?

a. Theta notation

b. Big-Oh notation

c. Omega notation

d. Time complexity

Ans: B

9. For converting recursive algorithm to non-recursive algorithm, store the values of all ___ parameters
in the stack.

a. Negative

b. Global

c. Pass by reference

d. Pass by value

Ans: D

10. The ___ is also known as an escape clause which is used to terminate the algorithm.

a. Recursive step

b. Recursive function

c. Iterative step

d. Base case
Ans: D

11. In algorithm visualization of bubble sort algorithm the non-linear curve of the sorted elements is
close to ___.

a. 3n

b. n3

c. 2n

d. n2

Ans: D

12. The recursive versions of binary search use a ___ structure.

a. Branch and bound

b. Dynamic programming

c. Divide and conquer

d. Simple recursive

Ans: C

13. ___ are node-based data structures used in many system programming applications for managing
dynamic sets

a. Stack

b. Queue

c. Binary search trees

d. List

Ans: C
14. Which method is practical to perform a single search in an unsorted list of elements?

a. Sequential search

b. Bubble sort

c. Horspool’s method of string matching

d. Brute force method of string matching

Ans: A

15. Which algorithm finds the solution for the single-source shortest path problem for a tree?

a. Prim’s

b. Dijkstra’s

c. Kruskal’s

d. Huffman code

Ans: B

16. Prim’s algorithm starts constructing a minimum spanning tree from ___.

a. An arbitary root vertex

b. The shortest arc

c. The left most vertex

d. The right most vertex

Ans: A

17. Which method of encoding does not consider the probability of occurrence of symbols?

a. Static Huffman coding

b. Variable length coding

c. Adaptive Huffman coding

d. Fixed length coding

Ans: D

18. In distribution counting to sorting elements in an array ___ is used.

a. Accumulated sum of frequencies

b. Frequency

c. Count of repeating elements in the array

d. The length of the array

Ans: A

19. ___ is a concept wherein larger solutions for problems are found based upon the solution of a
number of smaller problems.

a. Decrease and conquer

b. Divide and conquer

c. Branch and bound

d. Backtracking

Ans: A

20. The basic operation of the ___ algorithm is the comparison between the element and the array
given.

a. Binary search

b. Greedy

c. Brute force

d. Insertion sort

Ans: D
21. In ___, one begins at the root of the tree and then explores along each branch.

a. Topological sorting

b. Breadth-first search

c. Depth-first search

d. Insertion Sort

Ans: C

22. What is the mode for the following set numbers? 10,12,8,4,10, 6, 10,11,11,10,12

a. 11

b. 12

c. 10

d. 9

Ans: C

23. ___ is not a balanced search tree.

a. AVL tree

b. Binary tree

c. Red-black tree

d. B-tree

Ans: B

24. The number of key comparisons in the worst case while forming a heap is using an array of n
elements is ___.

a. nlog2(n+1)

b. 2(nlog(n+1))
c. 2(n-1)log2(n+1)

d. 2(n-log2(n+1))

Ans: D

25. ___ is an optimization technique for particular classes of backtracking algorithms that repeatedly
solve sub-problems.

a. Decrease and conquer

b. Dynamic programming

c. Branch and bound

d. Divide and Conquer

Ans: B

26. The binomial coefficient is represented as ___.

a. kCn

b. nCk

c. n+1Ck

d. nCk+1

Ans: B

27. ___ is the technique by which we make a function perform faster by trading space for time.

a. Divide and conquer

b. Greedy

c. Memoization

d. Recursion

Ans: C
28. The root node in the B-Tree technique has ___ limit on the number of children?

a. Lower

b. Upper and Lower

c. Upper

d. No

Ans: C

29. The shift table is to be initialized to ___ to compute the bad character shift.

a. The number of matches of the pattern with the text

b. The number of mismatches occurring

c. Length of the pattern-1

d. Length of the pattern

Ans: D

30. Each slot of the bucket array in separate chaining stores ___.

a. Records

b. A pointer to a linked list

c. Hash key values

d. Both b & c

Ans: B

31. The best possible value of the problem objective, written as a function of the state, is called the ___.

a. Value function

b. Control variables

c. Policy function
d. Principle of Optimality

Ans: A

32. If we have materials of different values per unit volume and maximum amounts, the ___ Knapsack
problem finds the most valuable mix of materials that fit in a knapsack of fixed volume.

a. Bounded

b. Binary

c. 0-1

d. Fractional

Ans: D

33. We use ___ for finding solutions to sub-problems, so as to reduce recalculation.

a. Backtracking

b. Recursion

c. Memoization

d. Branch and bound algorithms

Ans: C

34. With respect to finding the time complexity of Kruskal’s algorithm, which operation keeps track of
the parent pointer until it reaches the root parent?

a. Makeset

b. Union

c. Find

d. Merge

Ans: C
35. ___ means calculating the minimum amount of work required to solve the problem.

a. Upper-bound

b. Lower–bound

c. Adversary

d. Problem reduction

Ans: B

36. In a decision tree, a node represents a ___.

a. Input value

b. Output value

c. Solution

d. Decision

Ans: D

37. An algorithm that defines every operation exclusively is called ___ algorithm.

a. NP-hard

b. Deterministic

c. Non-deterministic

d. NP-complete

Ans: B

38. ___ problems include counting of structures of a specific kind and identifying the largest, smallest or
optimal objects.

a. Combinatorial

b. Traveling Salesman
c. Knapsack problem

d. Use cases

Ans: A

39. ___ is a sequence of data elements connected to each other where every element has a link field
referring to the location of the next element.

a. Array

b. Stack

c. List

d. Queue

Ans: C

40. ___ organizes details of all candidate solutions and discards large subsets of fruitless candidates by
using upper and lower estimated bounds of the quantity being optimized.

a. Approximation algorithms

b. Dynamic programming

c. Greedy algorithm

d. Branch and Bound

Ans: D

41. Which one of the following statements is true?

a. An algorithm should have one or more inputs externally and it should produce one or more output.

b. An algorithm may or may not terminate after a finite number of steps.

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.

Ans: C
42. The two main conditions for theta notation are ___ and___.

a. f(n)=O(g(n)), f(n)≠Θ(g(n))

b. f(n)>O(g(n)), f(n)=Θ(g(n))

c. f(n)≠O(g(n)), f(n)≥Θ(g(n))

d. f(n)>O(g(n)), f(n)>Θ(g(n))

Ans: A

43. Identify the true and false statements from the following with respect to measuring the running time
of an algorithm.

1. Firstly, recognize the basic operation of an algorithm.

2. Identifying the basic operation of an algorithm is difficult.

a. 1-T, 2-F

b. 1-T, 2-T

c. 1-F, 2-T

d. 1-F, 2-F

Ans: A

44. The two primitive operations of the function Fact(x) are ___ and ___.

a. Indexing an array, comparing two numbers

b. To check if the value of x is 1, To multiply x and Fact(x-1)

c. To check if the value of x is 1, To multiply x

d. To multiply x and Fact(x-1), Compare two numbers

Ans: B
45. The smoothness rule assumes that T(n) Є Θ(n2) if ___ is a smooth function and ___ is eventually
non-decreasing.

a. n2, T(n)

b. Θ(n2), T(n)

c. T(n), n2

d. Θ(n),n

Ans: A

46. In which method of coding does the code of a symbol not depend on the frequency of occurrence of
that symbol?

a. Variable length coding

b. Fixed length coding

c. Static Huffman coding

d. Adaptive Huffman coding

Ans: B

47. Which among the following is not a reason to perform the empirical analysis?

a. To check the accuracy of the algorithm.

b. To reduce the use of mathematical analysis and algorithm visualization.

c. To compare the efficiencies of different algorithms working to solve the same problem.

d. To develop the algorithm’s efficiency class.

Ans: B

48. In distribution counting, one array is used to store ___ value and another to store ___ list of
elements.

a. Frequency, Sorted

b. Distribution, Sorted
c. Frequency, Unsorted

d. Sorted, Unsorted

Ans: B

49. In a knapsack problem, if a set of items are given, each with a weight and a value, the goal is to find
the number of items that ___ the total weight and ___ the total value.

a. Minimizes, Minimizes

b. Maximizes, Maximizes

c. Maximizes, Minimizes

d. Minimizes, Maximizes

Ans: D

50. Identify true and false statements.

1. Insertion sort executes in O(n3) time.

2. Insertion sort is twice as fast as bubble sort.

a. 1-F, 2-F

b. 1-T, 2-F

c. 1-T, 2-T

d. 1-F, 2-T

Ans: D

Test Your IQ on Design and Analysis of Algorithms MCQs

Created on December 05, 2022 By Sofia Islam

ANALYSIS & DESIGN OF ALGORITHM QUIZ

At Eguardian India, we understand the importance of understanding the fundamentals of algorithm
design and analysis. To help students get a better grasp of the concepts, we have created an Analysis
and Design of an Algorithm Quiz.

This quiz will test your knowledge of algorithm design and analysis, and help you gain a better
understanding of the topic. So, why wait? Take the quiz now and find out how well you know your
algorithms!

FAQs

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.

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.