Scribd
Upload
35 views2 pages

Algorithm Design Lab Viva Questions With Answers

The document outlines fundamental algorithm concepts, including definitions and characteristics of algorithms, time complexity, and Big O notation. It covers various algorithm design paradigms such as Divide and Conquer, Greedy Algorithms, Dynamic Programming, Graph Algorithms, and Backtracking, providing examples and explanations of key algorithms like Merge Sort, Kruskal’s Algorithm, and Dijkstra’s Algorithm. Additionally, it discusses complexity classes, specifically P and NP problems, and their relationship.

Uploaded by

oppokinga58
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd
35 views2 pages

Algorithm Design Lab Viva Questions With Answers

The document outlines fundamental algorithm concepts, including definitions and characteristics of algorithms, time complexity, and Big O notation. It covers various algorithm design paradigms such as Divide and Conquer, Greedy Algorithms, Dynamic Programming, Graph Algorithms, and Backtracking, providing examples and explanations of key algorithms like Merge Sort, Kruskal’s Algorithm, and Dijkstra’s Algorithm. Additionally, it discusses complexity classes, specifically P and NP problems, and their relationship.

Uploaded by

oppokinga58
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd
You are on page 1/ 2

1.

Basic Algorithm Concepts

Q1. What is an algorithm?


An algorithm is a step-by-step procedure or a set of rules to solve a particular problem in a finite
amount of time.
Q2. What are the characteristics of a good algorithm?
Input and output clearly defined, finiteness, effectiveness, definiteness, and efficiency.
Q3. What is time complexity?
Time complexity is a function that describes the amount of time an algorithm takes to run as a
function of the input size (n).
Q4. What is Big O notation?
Big O notation represents the worst-case time complexity of an algorithm, showing how it scales as
the input size increases.

2. Divide and Conquer

Q5. What is Divide and Conquer?


It’s an algorithm design paradigm that divides the problem into subproblems, solves them
recursively, and then combines the solutions.
Q6. Explain Merge Sort and its time complexity.
Merge Sort divides the array into halves, recursively sorts them, and merges. Time Complexity: O(n
log n), Space Complexity: O(n).
Q7. What is the time complexity of Binary Search?
O(log n) in the best and average case, O(1) in best case if the element is at the middle index.

3. Greedy Algorithms

Q8. What is a greedy algorithm?


A greedy algorithm makes the locally optimal choice at each step with the hope of finding the global
optimum.
Q9. Give an example where greedy fails.
The 0/1 Knapsack Problem — Greedy doesn't guarantee the optimal solution.
Q10. What is Kruskal’s Algorithm?
Kruskal’s algorithm finds the minimum spanning tree using a greedy approach by selecting edges
with the least weight and avoiding cycles.

4. Dynamic Programming

Q11. What is dynamic programming?


It’s an optimization technique that solves problems by breaking them into overlapping subproblems
and storing their solutions to avoid recalculations.
Q12. Difference between DP and recursion?
Recursion solves subproblems again and again, while DP stores results and avoids recomputation
using memoization or tabulation.
Q13. Explain 0/1 Knapsack using DP.
Use a 2D table where dp[i][j] represents the maximum value for the first i items with capacity j.
Include or exclude item based on capacity.

5. Graph Algorithms

Q14. Difference between DFS and BFS?


DFS uses a stack and explores deep into the graph. BFS uses a queue and explores layer-wise.
BFS finds the shortest path in unweighted graphs.
Q15. What is Dijkstra’s algorithm?
It's used to find the shortest path from a source to all other vertices in a graph with non-negative
edge weights.
Q16. What is a minimum spanning tree?
A spanning tree with the minimum total edge weight that connects all vertices without cycles.

6. Backtracking

Q17. What is backtracking?


A method to find all possible solutions by exploring all options and discarding those that violate
constraints.
Q18. Explain N-Queens Problem.
Place N queens on an N×N chessboard such that no two queens attack each other — solved using
backtracking.

7. Complexity Classes

Q19. What are P and NP problems?


P: Solvable in polynomial time. NP: Verifiable in polynomial time. NP-Complete: Problems in NP to
which every other NP problem reduces.
Q20. Is every P problem also NP?
Yes. All P problems are also in NP because if a problem can be solved in polynomial time, its
solution can also be verified in polynomial time.

You might also like