2023 question paper

Design and Analysis of Algorithms

24 questions

Q1a. Which of the following notations is used to represent the worst-case time complexity of an algorithm? (i) O-notation (ii) \Omega-notation (iii) \Theta-notation (iv) \delta-notation20232m
Module 1: Introduction
Which of the following notations is used to represent the worst-case time complexity of an algorithm?
(i) O-notation
(ii) $\Omega$ -notation
(iii) $\Theta$ -notation
(iv) $\delta$ -notation

View this question on its own page →
Search Google Ask AI
Q1b. Which of the following sorting algorithms has the best time complexity in the average case? (i) Bubble sort (ii) Insertion sort (iii) Quick sort (iv) Selection sort20232m
Module 2: Fundamental Algorithmic Strategies
Which of the following sorting algorithms has the best time complexity in the average case?
(i) Bubble sort
(ii) Insertion sort
(iii) Quick sort
(iv) Selection sort

View this question on its own page →
Search Google Ask AI
Q1c. Which of the following algorithms is used to find the minimum spanning tree in a weighted undirected graph? (i) Dijkstra's algorithm (ii) Kruskal's algorithm (iii) Bellman-Ford algorithm (iv) Floyd-Warshall algorithm20232m
Module 3: Graph and Tree Algorithms
Which of the following algorithms is used to find the minimum spanning tree in a weighted undirected graph?
(i) Dijkstra's algorithm
(ii) Kruskal's algorithm
(iii) Bellman-Ford algorithm
(iv) Floyd-Warshall algorithm

View this question on its own page →
Search Google Ask AI
Q1d. Which sorting algorithm is considered stable and has a time complexity of O(n^2)? (i) Quick sort (ii) Merge sort (iii) Insertion sort (iv) Selection sort20232m
Module 1: Introduction
Which sorting algorithm is considered stable and has a time complexity of $O(n^2)$ ?
(i) Quick sort
(ii) Merge sort
(iii) Insertion sort
(iv) Selection sort

View this question on its own page →
Search Google Ask AI
Q1e. What is the complexity of T(n) = 2T(n/4) + n^2 \log n? (i) \Theta(n^2 \log(\log n)) (ii) \Theta(n^3 \log n) (iii) \Theta(n^2 \log n) (iv) \Theta(n \log n)20232m
Module 1: Introduction
What is the complexity of $T(n) = 2T(n/4) + n^2 \log n$ ?
(i) $\Theta(n^2 \log(\log n))$
(ii) $\Theta(n^3 \log n)$
(iii) $\Theta(n^2 \log n)$
(iv) $\Theta(n \log n)$

View this question on its own page →
Search Google Ask AI
Q1f. In algorithm analysis, what does "space complexity" refer to? (i) The number of input elements (ii) The amount of physical memory used (iii) The number of recursive calls (iv) The number of lines of code in the algorithm20232m
Module 1: Introduction
In algorithm analysis, what does "space complexity" refer to?
(i) The number of input elements
(ii) The amount of physical memory used
(iii) The number of recursive calls
(iv) The number of lines of code in the algorithm

View this question on its own page →
Search Google Ask AI
Q1g. What is the primary advantage of dynamic programming over brute-force algorithms? (i) Dynamic programming guarantees finding the global optimum. (ii) Dynamic programming reduces the time complexity by avoiding redundant computations. (iii) Dynamic programming simplifies the problem by dividing it into smaller subproblems. (iv) Dynamic programming is more intuitive to implement.20232m
Module 2: Fundamental Algorithmic Strategies
What is the primary advantage of dynamic programming over brute-force algorithms?
(i) Dynamic programming guarantees finding the global optimum.
(ii) Dynamic programming reduces the time complexity by avoiding redundant computations.
(iii) Dynamic programming simplifies the problem by dividing it into smaller subproblems.
(iv) Dynamic programming is more intuitive to implement.

View this question on its own page →
Search Google Ask AI
Q1h. In which algorithmic strategy are problems systematically divided into smaller subproblems until the solution to the original problem is found? (i) Brute-force (ii) Greedy (iii) Dynamic programming (iv) Backtracking20232m
Module 2: Fundamental Algorithmic Strategies
In which algorithmic strategy are problems systematically divided into smaller subproblems until the solution to the original problem is found?
(i) Brute-force
(ii) Greedy
(iii) Dynamic programming
(iv) Backtracking

View this question on its own page →
Search Google Ask AI
Q1i. What is the time complexity of topological sorting of a directed acyclic graph (DAG) with V vertices and E edges using Depth-First Search (DFS)? (i) O(V^2) (ii) O(E^2) (iii) O(V+E) (iv) O(V.E)20232m
Module 3: Graph and Tree Algorithms
What is the time complexity of topological sorting of a directed acyclic graph (DAG) with $V$ vertices and $E$ edges using Depth-First Search (DFS)?
(i) $O(V^2)$
(ii) $O(E^2)$
(iii) $O(V+E)$
(iv) $O(V.E)$

View this question on its own page →
Search Google Ask AI
Q1j. What is the relationship between NP and P complexity classes? (i) P is a subset of NP (ii) NP is a subset of P (iii) P and NP are equivalent (iv) P and NP are disjoint sets20232m
Module 4: Tractable and Intractable Problems
What is the relationship between NP and P complexity classes?
(i) P is a subset of NP
(ii) NP is a subset of P
(iii) P and NP are equivalent
(iv) P and NP are disjoint sets

View this question on its own page →
Search Google Ask AI
Q2a. Explain the concept of asymptotic notation (Big O, Big Omega, and Big Theta) in algorithm analysis.20237m
Module 1: Introduction
Explain the concept of asymptotic notation (Big O, Big Omega, and Big Theta) in algorithm analysis.

View this question on its own page →
Search Google Ask AI
Q2b. Consider the following recurrence relation: T(n) = 2T(n/2) + n Use the substitution method to find an asymptotic upper bound for the function T(n).20237m
Module 1: Introduction
Consider the following recurrence relation:
$T(n) = 2T(n/2) + n$
Use the substitution method to find an asymptotic upper bound for the function $T(n)$ .

View this question on its own page →
Search Google Ask AI
Q3a. Apply the Master Theorem to determine the time complexity of the following recurrence relations. (i) T(n) = 4T(n/2) + n^3 (ii) T(n) = T(n/2) + 2^n20235m
Module 1: Introduction
Apply the Master Theorem to determine the time complexity of the following recurrence relations.
(i) $T(n) = 4T(n/2) + n^3$
(ii) $T(n) = T(n/2) + 2^n$

View this question on its own page →
Search Google Ask AI
Q3b. Write the step-by-step process of Quick Sort using an example. Write the advantages and disadvantages of Quick Sort compared to other sorting algorithms, such as Merge Sort and Bubble Sort.20239m
Module 2: Fundamental Algorithmic Strategies
Write the step-by-step process of Quick Sort using an example. Write the advantages and disadvantages of Quick Sort compared to other sorting algorithms, such as Merge Sort and Bubble Sort.

View this question on its own page →
Search Google Ask AI
Q4a. Apply the Linear Search algorithm to find the position of the target element 7 in the following array: A=[3, 5, 2, 8, 7, 1, 4]. Also, analyze the time and space complexity.20237m
Module 1: Introduction
Apply the Linear Search algorithm to find the position of the target element 7 in the following array: $A=[3, 5, 2, 8, 7, 1, 4]$ . Also, analyze the time and space complexity.

View this question on its own page →
Search Google Ask AI
Q4b. You are a thief planning to rob a jewelry store. The store contains 7 items, each with a profit P and weight W as follows: | Object | 1 | 2 | 3 | 4 | 5 | 6 | 7 | |---|---|---|---|---|---|---|---| | Profit (P) | 5 | 10 | 15 | 7 | 8 | 9 | 4 | | Weight (W) | 1 | 3 | 5 | 4 | 1 | 3 | 2 | You have a knapsack with a weight capacity of 15. Apply the step-by-step greedy approach to obtain the maximum profit.20237m
Module 2: Fundamental Algorithmic Strategies
You are a thief planning to rob a jewelry store. The store contains 7 items, each with a profit $P$ and weight $W$ as follows:

Object 1 2 3 4 5 6 7

Profit (P) 5 10 15 7 8 9 4

Weight (W) 1 3 5 4 1 3 2

You have a knapsack with a weight capacity of 15. Apply the step-by-step greedy approach to obtain the maximum profit.

View this question on its own page →
Search Google Ask AI
Q5a. Apply the backtracking approach and find the Hamiltonian cycle for the graph given in the form of matrix. Show all the steps to find the cycle. | | A | B | C | D | E | F | |---|---|---|---|---|---|---| | A | 0 | 1 | 1 | 0 | 0 | 1 | | B | 1 | 0 | 1 | 1 | 0 | 0 | | C | 1 | 1 | 0 | 0 | 1 | 0 | | D | 0 | 1 | 0 | 0 | 1 | 0 | | E | 0 | 0 | 1 | 1 | 0 | 1 | | F | 1 | 0 | 1 | 0 | 1 | 0 |202310m
Module 2: Fundamental Algorithmic Strategies
Apply the backtracking approach and find the Hamiltonian cycle for the graph given in the form of matrix. Show all the steps to find the cycle.

A B C D E F

A 0 1 1 0 0 1

B 1 0 1 1 0 0

C 1 1 0 0 1 0

D 0 1 0 0 1 0

E 0 0 1 1 0 1

F 1 0 1 0 1 0

View this question on its own page →
Search Google Ask AI
Q5b. Differentiate between backtracking and branch & bound.20234m
Module 2: Fundamental Algorithmic Strategies
Differentiate between backtracking and branch & bound.

View this question on its own page →
Search Google Ask AI
Q6a. In the below given weighted graph W (Given in form of matrix), apply Bellman Ford's algorithm to find the shortest distances from source node 3. Write the time complexity of Bellman Ford's algorithm. | | 1 | 2 | 3 | 4 | 5 | |---|---|---|---|---|---| | 1 | 0 | 1 | 8 | 1 | 4 | | 2 | 1 | 0 | 12 | 4 | 9 | | 3 | 8 | 12 | 0 | 7 | 3 | | 4 | 1 | 4 | 7 | 0 | 2 | | 5 | 4 | 9 | 3 | 2 | 0 |20237m
Module 3: Graph and Tree Algorithms
In the below given weighted graph W (Given in form of matrix), apply Bellman Ford's algorithm to find the shortest distances from source node 3. Write the time complexity of Bellman Ford's algorithm.

1 2 3 4 5

1 0 1 8 1 4

2 1 0 12 4 9

3 8 12 0 7 3

4 1 4 7 0 2

5 4 9 3 2 0

View this question on its own page →
Search Google Ask AI
Q6b. What is minimum spanning tree (MST)? Explain the steps of Prim's algorithm to find the MST using an example.20237m
Module 3: Graph and Tree Algorithms
What is minimum spanning tree (MST)? Explain the steps of Prim's algorithm to find the MST using an example.

View this question on its own page →
Search Google Ask AI
Q7a. Discuss the differences between BFS and DFS in terms of traversal order, memory usage, and their applications in real-world problems.20237m
Module 3: Graph and Tree Algorithms
Discuss the differences between BFS and DFS in terms of traversal order, memory usage, and their applications in real-world problems.

View this question on its own page →
Search Google Ask AI
Q7b. What is P, NP, NP hard, and NP complete? Write the relationship between all of them.20237m
Module 4: Tractable and Intractable Problems
What is P, NP, NP hard, and NP complete? Write the relationship between all of them.

View this question on its own page →
Search Google Ask AI
Q8. We are given the sequence \{4, 10, 3, 12, 20, \text{and } 7\}. The matrices have size 4 \times 10, 10 \times 3, 3 \times 12, 12 \times 20, 20 \times 7. Find the most efficient way to multiply these matrices together using dynamic programming. The efficient way is the one that involves the least number of multiplications. Write all the steps with time complexity.202314m
Module 2: Fundamental Algorithmic Strategies
We are given the sequence $\{4, 10, 3, 12, 20, \text{and } 7\}$ . The matrices have size $4 \times 10, 10 \times 3, 3 \times 12, 12 \times 20, 20 \times 7$ . Find the most efficient way to multiply these matrices together using dynamic programming. The efficient way is the one that involves the least number of multiplications. Write all the steps with time complexity.

View this question on its own page →
Search Google Ask AI
Q9. Write the short note on the following: (a) Cook's theorm (b) Randomized algorithms (c) Bin Packing202314m
Module 5: Advanced Topics
Write the short note on the following:
(a) Cook's theorm
(b) Randomized algorithms
(c) Bin Packing

View this question on its own page →
Search Google Ask AI

Object	1	2	3	4	5	6	7
Profit (P)	5	10	15	7	8	9	4
Weight (W)	1	3	5	4	1	3	2

	A	B	C	D	E	F
A	0	1	1	0	0	1
B	1	0	1	1	0	0
C	1	1	0	0	1	0
D	0	1	0	0	1	0
E	0	0	1	1	0	1
F	1	0	1	0	1	0

	1	2	3	4	5
1	0	1	8	1	4
2	1	0	12	4	9
3	8	12	0	7	3
4	1	4	7	0	2
5	4	9	3	2	0

Previous year2022 Next year2024