All questions of Algorithms for Computer Science Engineering (CSE) Exam
Which of the following standard algorithms is not Dynamic Programming based.- a)Bellman–Ford Algorithm for single source shortest path
- b)Floyd Warshall Algorithm for all pairs shortest paths
- c)0-1 Knapsack problem
- d)Prim’s Minimum Spanning Tree
Correct answer is option 'D'. Can you explain this answer?
Which of the following standard algorithms is not Dynamic Programming based.
a)
Bellman–Ford Algorithm for single source shortest path
b)
Floyd Warshall Algorithm for all pairs shortest paths
c)
0-1 Knapsack problem
d)
Prim’s Minimum Spanning Tree
|
Sudhir Patel answered |
Prim’s Minimum Spanning Tree is a Greedy Algorithm. All other are dynamic programming based.
| 1 Crore+ students have signed up on EduRev. Have you? Download the App |
Which of the following is not a backtracking algorithm?- a)Knight tour problem
- b)N queen problem
- c)Tower of hanoi
- d)M coloring problem
Correct answer is option 'C'. Can you explain this answer?
Which of the following is not a backtracking algorithm?
a)
Knight tour problem
b)
N queen problem
c)
Tower of hanoi
d)
M coloring problem
|
Ipsita Patel answered |
Backtracking Algorithms
Backtracking algorithms are a type of recursive algorithm used to solve problems that involve searching through a large number of possibilities. These algorithms work by exploring all possible paths through a problem space, but only keep track of the most promising paths. If a promising path leads to a dead end, the algorithm backs up and tries another path.
Examples of Backtracking Algorithms
1. Knight Tour Problem
- A chessboard is an 8x8 grid with 64 squares.
- The problem is to move a knight piece around the board, visiting each square once.
- The knight moves in an L-shape, two squares in one direction and then one square in a perpendicular direction.
- This problem can be solved using a backtracking algorithm.
2. N Queen Problem
- The problem is to place N queens on an N x N chessboard in such a way that no two queens attack each other.
- A queen can attack any other piece that lies on the same row, column, or diagonal.
- This problem can be solved using a backtracking algorithm.
3. M Coloring Problem
- The problem is to color a graph with M colors in such a way that no two adjacent vertices have the same color.
- This problem can be solved using a backtracking algorithm.
4. Tower of Hanoi
- The Tower of Hanoi is a puzzle that consists of three pegs and a set of disks of different sizes.
- The objective is to move the entire stack to another peg, obeying the following simple rules:
- Only one disk can be moved at a time.
- Each move consists of taking the upper disk from one of the stacks and placing it on top of another stack or on an empty peg.
- No disk may be placed on top of a smaller disk.
- This problem can be solved using a recursive backtracking algorithm.
Answer
The correct answer is option C, Tower of Hanoi. This is because the Tower of Hanoi problem can be solved using a recursive algorithm, but it does not involve backtracking. Backtracking algorithms are used to solve problems that involve searching through a large number of possibilities and keeping track of the most promising paths. The Tower of Hanoi problem does not involve searching through a large number of possibilities or keeping track of the most promising paths, so it does not require a backtracking algorithm.
Backtracking algorithms are a type of recursive algorithm used to solve problems that involve searching through a large number of possibilities. These algorithms work by exploring all possible paths through a problem space, but only keep track of the most promising paths. If a promising path leads to a dead end, the algorithm backs up and tries another path.
Examples of Backtracking Algorithms
1. Knight Tour Problem
- A chessboard is an 8x8 grid with 64 squares.
- The problem is to move a knight piece around the board, visiting each square once.
- The knight moves in an L-shape, two squares in one direction and then one square in a perpendicular direction.
- This problem can be solved using a backtracking algorithm.
2. N Queen Problem
- The problem is to place N queens on an N x N chessboard in such a way that no two queens attack each other.
- A queen can attack any other piece that lies on the same row, column, or diagonal.
- This problem can be solved using a backtracking algorithm.
3. M Coloring Problem
- The problem is to color a graph with M colors in such a way that no two adjacent vertices have the same color.
- This problem can be solved using a backtracking algorithm.
4. Tower of Hanoi
- The Tower of Hanoi is a puzzle that consists of three pegs and a set of disks of different sizes.
- The objective is to move the entire stack to another peg, obeying the following simple rules:
- Only one disk can be moved at a time.
- Each move consists of taking the upper disk from one of the stacks and placing it on top of another stack or on an empty peg.
- No disk may be placed on top of a smaller disk.
- This problem can be solved using a recursive backtracking algorithm.
Answer
The correct answer is option C, Tower of Hanoi. This is because the Tower of Hanoi problem can be solved using a recursive algorithm, but it does not involve backtracking. Backtracking algorithms are used to solve problems that involve searching through a large number of possibilities and keeping track of the most promising paths. The Tower of Hanoi problem does not involve searching through a large number of possibilities or keeping track of the most promising paths, so it does not require a backtracking algorithm.
Which of the following is not O(n^2)?- a)(15^10) * n + 12099
- b)n^1.98
- c)n^3 / (sqrt(n))
- d)(2^20) * n
Correct answer is option 'C'. Can you explain this answer?
Which of the following is not O(n^2)?
a)
(15^10) * n + 12099
b)
n^1.98
c)
n^3 / (sqrt(n))
d)
(2^20) * n
|
Aryan Saha answered |
Explanation:
O(n^2) denotes that the time complexity of an algorithm is proportional to the square of the size of the input data.
a) (15^10) * n - This is O(n^2) because the n term dominates the constant term.
b) n^1.98 - This is not O(n^2) because the power of n is less than 2.
c) n^3 / (sqrt(n)) - This is not O(n^2) because the square root term is less than the n^2 term.
d) (2^20) * n - This is O(n^2) because the n term dominates the constant term.
Therefore, option C is not O(n^2).
O(n^2) denotes that the time complexity of an algorithm is proportional to the square of the size of the input data.
a) (15^10) * n - This is O(n^2) because the n term dominates the constant term.
b) n^1.98 - This is not O(n^2) because the power of n is less than 2.
c) n^3 / (sqrt(n)) - This is not O(n^2) because the square root term is less than the n^2 term.
d) (2^20) * n - This is O(n^2) because the n term dominates the constant term.
Therefore, option C is not O(n^2).
Consider two strings A = “qpqrr” and B = “pqprqrp”. Let x be the length of the longest common subsequence (not necessarily contiguous) between A and B and let y be the number of such longest common subsequences between A and B. Then x + 10y = ___.- a)33
- b)23
- c)43
- d)34
Correct answer is option 'D'. Can you explain this answer?
Consider two strings A = “qpqrr” and B = “pqprqrp”. Let x be the length of the longest common subsequence (not necessarily contiguous) between A and B and let y be the number of such longest common subsequences between A and B. Then x + 10y = ___.
a)
33
b)
23
c)
43
d)
34
|
Amrutha Sharma answered |
"hello" and B = "world".
Let SHAM3 be the problem of finding a Hamiltonian cycle in a graph G = (V,E) with V divisible by 3 and DHAM3 be the problem of determining if a Hamiltonian cycle exists in such graphs. Which one of the following is true?- a)Both DHAM3 and SHAM3 are NP-hard
- b)SHAM3 is NP-hard, but DHAM3 is not
- c)DHAM3 is NP-hard, but SHAM3 is not
- d)Neither DHAM3 nor SHAM3 is NP-hard
Correct answer is option 'A'. Can you explain this answer?
Let SHAM3 be the problem of finding a Hamiltonian cycle in a graph G = (V,E) with V divisible by 3 and DHAM3 be the problem of determining if a Hamiltonian cycle exists in such graphs. Which one of the following is true?
a)
Both DHAM3 and SHAM3 are NP-hard
b)
SHAM3 is NP-hard, but DHAM3 is not
c)
DHAM3 is NP-hard, but SHAM3 is not
d)
Neither DHAM3 nor SHAM3 is NP-hard
|
|
Sudhir Patel answered |
The problem of finding whether there exist a Hamiltonian Cycle or not is NP Hard and NP Complete Both.
Finding a Hamiltonian cycle in a graph G = (V,E) with V divisible by 3 is also NP Hard.
What is the time complexity of Floyd–Warshall algorithm to calculate all pair shortest path in a graph with n vertices?- a)O(n^2logn)
- b)θ(n^2logn)
- c)θ(n^4)
- d)θ(n^3)
Correct answer is option 'D'. Can you explain this answer?
What is the time complexity of Floyd–Warshall algorithm to calculate all pair shortest path in a graph with n vertices?
a)
O(n^2logn)
b)
θ(n^2logn)
c)
θ(n^4)
d)
θ(n^3)
|
Krithika Tiwari answered |
-Warshall algorithm?
The time complexity of Floyd-Warshall algorithm is O(n^3), where n is the number of vertices in the graph. It involves three nested loops, and for each vertex pair, it checks if there is a shorter path through an intermediate vertex. This algorithm is used to find the shortest path between all pairs of vertices in a weighted graph.
The time complexity of Floyd-Warshall algorithm is O(n^3), where n is the number of vertices in the graph. It involves three nested loops, and for each vertex pair, it checks if there is a shorter path through an intermediate vertex. This algorithm is used to find the shortest path between all pairs of vertices in a weighted graph.
Consider the following two problems of graph.
1. Given a graph, find if the graph has a cycle that visits every vertex exactly once except the first visited vertex which must be visited again to complete the cycle.
2. Given a graph, find if the graph has a cycle that visits every edge exactly once.
Which of the following is true about above two problems.- a)Problem 1 belongs NP Complete set and 2 belongs to P
- b)Problem 1 belongs to P set and 2 belongs to NP Complete set
- c)Both problems belong to P set
- d)Both problems belong to NP complete set
Correct answer is option 'A'. Can you explain this answer?
Consider the following two problems of graph.
1. Given a graph, find if the graph has a cycle that visits every vertex exactly once except the first visited vertex which must be visited again to complete the cycle.
2. Given a graph, find if the graph has a cycle that visits every edge exactly once.
Which of the following is true about above two problems.
1. Given a graph, find if the graph has a cycle that visits every vertex exactly once except the first visited vertex which must be visited again to complete the cycle.
2. Given a graph, find if the graph has a cycle that visits every edge exactly once.
Which of the following is true about above two problems.
a)
Problem 1 belongs NP Complete set and 2 belongs to P
b)
Problem 1 belongs to P set and 2 belongs to NP Complete set
c)
Both problems belong to P set
d)
Both problems belong to NP complete set
|
Aditi Pillai answered |
NP Complete Problems in Graph Theory
Problem 1: Hamiltonian Cycle Problem
The Hamiltonian cycle problem is an NP-complete problem in graph theory. The problem is to determine whether a given graph contains a cycle that visits every vertex exactly once, except for the first and last vertices, which are visited twice to form a closed loop.
Problem 2: Eulerian Cycle Problem
The Eulerian cycle problem is another NP-complete problem in graph theory. The problem is to determine whether a given graph contains a cycle that visits every edge exactly once.
Comparison of the two problems
Therefore, the correct answer is option A, which states that problem 1 belongs to the NP-complete set, and problem 2 belongs to the P set.
Problem 1: Hamiltonian Cycle Problem
The Hamiltonian cycle problem is an NP-complete problem in graph theory. The problem is to determine whether a given graph contains a cycle that visits every vertex exactly once, except for the first and last vertices, which are visited twice to form a closed loop.
- It is a decision problem that asks whether there exists a Hamiltonian cycle in an undirected graph.
- It is NP-complete, which means that it is at least as hard as any other NP problem and is unlikely to have an efficient algorithm for large inputs.
- It is a well-known problem in computer science and has been studied extensively.
- There are many algorithms for solving this problem, but none of them are known to be efficient for all instances of the problem.
Problem 2: Eulerian Cycle Problem
The Eulerian cycle problem is another NP-complete problem in graph theory. The problem is to determine whether a given graph contains a cycle that visits every edge exactly once.
- It is a decision problem that asks whether there exists an Eulerian cycle in a directed or undirected graph.
- It is NP-complete, which means that it is at least as hard as any other NP problem and is unlikely to have an efficient algorithm for large inputs.
- It is also a well-known problem in computer science and has been studied extensively.
- There are many algorithms for solving this problem, but none of them are known to be efficient for all instances of the problem.
Comparison of the two problems
- Both problems are related to the existence of cycles in graphs.
- The Hamiltonian cycle problem is concerned with visiting every vertex exactly once, while the Eulerian cycle problem is concerned with visiting every edge exactly once.
- Both problems are NP-complete, which means that they are among the hardest problems in computer science and are unlikely to have efficient algorithms for large inputs.
- Both problems have been studied extensively and have many algorithms for solving them, but none of these algorithms are known to be efficient for all instances of the problems.
Therefore, the correct answer is option A, which states that problem 1 belongs to the NP-complete set, and problem 2 belongs to the P set.
Consider the following C programint main() { int x, y, m, n; scanf ("%d %d", &x, &y); /* x > 0 and y > 0 */ m = x; n = y; while (m != n) { if(m>n) m = m - n; else n = n - m; } printf("%d", n); }What does the program compute?- a)x + y using repeated subtraction
- b)x mod y using repeated subtraction
- c)the greatest common divisor of x and y
- d)the least common multiple of x and y
Correct answer is option 'C'. Can you explain this answer?
Consider the following C program
int main()
{
int x, y, m, n;
scanf ("%d %d", &x, &y);
/* x > 0 and y > 0 */
m = x; n = y;
while (m != n)
{
if(m>n)
m = m - n;
else
n = n - m;
}
printf("%d", n);
}
What does the program compute?
a)
x + y using repeated subtraction
b)
x mod y using repeated subtraction
c)
the greatest common divisor of x and y
d)
the least common multiple of x and y
|
|
Sudhir Patel answered |
This is an implementation of Euclid’s algorithm to find GCD
A system wherein items are added from one and removed from the other end.- a)Stack
- b)Queue
- c)Linked List
- d)Array
Correct answer is option 'B'. Can you explain this answer?
A system wherein items are added from one and removed from the other end.
a)
Stack
b)
Queue
c)
Linked List
d)
Array
|
|
Sudhir Patel answered |
In a queue, the items are inserted from the rear end and deleted from the front end.
If we use Radix Sort to sort n integers in the range (nk/2,nk], for some k>0 which is independent of n, the time taken would be?- a)Θ(n)
- b)Θ(kn)
- c)Θ(nlogn)
- d)Θ(n2)
Correct answer is option 'C'. Can you explain this answer?
If we use Radix Sort to sort n integers in the range (nk/2,nk], for some k>0 which is independent of n, the time taken would be?
a)
Θ(n)
b)
Θ(kn)
c)
Θ(nlogn)
d)
Θ(n2)
|
|
Sudhir Patel answered |
Radix sort time complexity = O(wn)
for n keys of word size= w
=>w = log(nk)
O(wn)=O(klogn.n)
=> kO(nlogn)
for n keys of word size= w
=>w = log(nk)
O(wn)=O(klogn.n)
=> kO(nlogn)
Chapter doubts & questions for Algorithms - GATE Computer Science Engineering(CSE) 2025 Mock Test Series 2024 is part of Computer Science Engineering (CSE) exam preparation. The chapters have been prepared according to the Computer Science Engineering (CSE) exam syllabus. The Chapter doubts & questions, notes, tests & MCQs are made for Computer Science Engineering (CSE) 2024 Exam. Find important definitions, questions, notes, meanings, examples, exercises, MCQs and online tests here.
Chapter doubts & questions of Algorithms - GATE Computer Science Engineering(CSE) 2025 Mock Test Series in English & Hindi are available as part of Computer Science Engineering (CSE) exam.
Download more important topics, notes, lectures and mock test series for Computer Science Engineering (CSE) Exam by signing up for free.
Signup to see your scores go up within 7 days!
Study with 1000+ FREE Docs, Videos & Tests
10M+ students study on EduRev
|
© EduRev
|
Education Revolution
|
Follow Us
|
Signup to see your scores
go up within 7 days!
Access 1000+ FREE Docs, Videos and Tests
Takes less than 10 seconds to signup