Algorithm Viva Q&A – A Complete Guide for Computer Science Students

Algorithm Viva Questions and Answers

Algorithm Viva Questions and Detailed Answers

2. Divide and Conquer Approach

Q1. What is the Divide and Conquer strategy?

It is an algorithmic paradigm that breaks a problem into subproblems, solves them recursively, and then combines their results. Examples include Merge Sort, Quick Sort, and Binary Search.

Q2. Explain Finding Minimum and Maximum using Divide and Conquer.

The array is split into halves. Recursively, min and max of each half are found, and finally the overall min and max are determined using a comparison of results from the halves.

Q3. Describe Merge Sort.

Merge Sort divides the list into halves, recursively sorts them, and merges the sorted halves. It has a time complexity of O(n log n) and is stable but not in-place.

Q4. Explain Quick Sort.

Quick Sort selects a pivot, partitions the array such that elements lesser are on the left and greater on the right, then recursively sorts the partitions. Its average time complexity is O(n log n).

Q5. How does Binary Search work?

Binary Search works on sorted arrays by repeatedly dividing the search interval in half and comparing the target value to the middle element. Time complexity is O(log n).

3. Greedy Method Approach

Q6. What is the Greedy Method?

The greedy method builds a solution step by step, choosing the best local option at each step, hoping to find the global optimum.

Q7. Explain Dijkstra's Algorithm.

Dijkstra's algorithm finds the shortest path from a single source to all vertices in a graph with non-negative weights. It uses a priority queue to select the next minimum distance vertex.

Q8. What is the Fractional Knapsack problem?

It is a greedy problem where items can be broken to maximize profit. Sort items by value/weight ratio and take portions of items to fill the knapsack to capacity.

Q9. Describe Job Sequencing with Deadlines.

This problem involves scheduling jobs to maximize profit such that each job is completed within its deadline. Jobs are sorted by profit and scheduled if a free slot is available before the deadline.

Q10. What are Kruskal and Prim’s Algorithms?

Kruskal's algorithm selects the smallest weight edge that doesn't form a cycle. Prim's algorithm starts from a node and grows the spanning tree by adding the smallest edge connecting the tree to a new vertex.

4. Dynamic Programming Approach

Q11. Explain Bellman-Ford Algorithm.

Bellman-Ford finds shortest paths from a single source to all vertices, even with negative weights. It relaxes all edges repeatedly for V-1 times.

Q12. Describe Floyd-Warshall Algorithm.

Floyd-Warshall finds shortest paths between all pairs of vertices. It uses a dynamic programming table that is updated considering each vertex as an intermediate point.

Q13. What is the 0/1 Knapsack Problem?

Items cannot be broken and must be taken fully or not at all. A DP table is built where each cell represents the maximum value with a given weight and items subset.

Q14. Explain the Travelling Salesperson Problem (TSP).

TSP seeks the shortest route visiting all cities exactly once and returning to the origin. It is NP-Hard and solved using dynamic programming or approximation methods.

Q15. What is the Longest Common Subsequence (LCS)?

LCS finds the longest sequence present in the same order in both strings. It uses a DP table to compare characters and store intermediate results.

5. Backtracking and Branch and Bound

Q16. Describe the N-Queen Problem.

The goal is to place N queens on an N×N chessboard such that no two queens threaten each other. Backtracking is used to explore possible placements and backtrack on conflict.

Q17. What is the Sum of Subsets problem?

It involves finding subsets of numbers that sum up to a given target. Backtracking explores all subsets and prunes branches where the sum exceeds the target.

Q18. Explain Graph Coloring using Backtracking.

Graph coloring assigns colors to vertices so that no two adjacent vertices have the same color. Backtracking tries all color assignments and backtracks on conflicts.

6. String Matching Algorithms

Q19. Describe the Naïve String Matching Algorithm.

This brute-force method compares the pattern with all substrings of the text. Time complexity is O(nm), where n is text length and m is pattern length.

Q20. Explain Rabin-Karp Algorithm.

It uses hashing to find patterns in text. It calculates the hash of the pattern and substrings, reducing comparisons with rolling hash functions. Time complexity is O(n+m) on average.

Q21. Describe the Knuth-Morris-Pratt (KMP) Algorithm.

KMP avoids redundant comparisons by using a prefix table (LPS array) to skip characters when a mismatch occurs. It has a time complexity of O(n).

Prepared by Dr. Radhika Nanda | HOD – Computer Engineering

Comments

Post a Comment

Popular posts from this blog

Analysis of algorithms viva questions / Interview questions - set1 /sorting algorithms

Top 10 Questions on Sorting Algorithms and Divide and Conquer Approach Top 10 Questions on Sorting Algorithms and Divide and Conquer Approach Understanding basic sorting algorithms and the divide and conquer approach is crucial for every computer science student. Below are the most frequently asked questions with answers from Module 1: Introduction to Algorithms . 1. What is Selection Sort and how does it work? Selection Sort is a comparison-based algorithm that divides the array into a sorted and unsorted part. It repeatedly selects the minimum element from the unsorted section and moves it to the beginning. Time Complexity: O(n²) Stable: No In-place: Yes 2. What are the steps involved in Insertion Sort? Insertion Sort builds the sorted array one element at a time by inserting each new element into its correct position among the previously sorted elements. Best Case: O(n) Worst Case: O(n²) Stable: Ye...
Read more

Operating System Viva questions/interview questions 2025

1. What is an Operating System? An Operating System (OS) is system software that acts as a bridge between users and computer hardware. It manages hardware resources and provides services to application software. An OS handles tasks like memory management, process scheduling, and device control. It ensures that programs and users can run smoothly without interfering with each other. Examples include Windows, Linux, macOS, and Android. The OS also provides a user interface, either graphical (GUI) or command-line (CLI). Without an OS, a computer would be unusable. It organizes files, maintains security, and manages system performance. In short, the OS is the heart of any computing device. 2. What are the main functions of an Operating System? The primary functions of an Operating System are process management, memory management, file system management, and device management. It ensures efficient execution of processes by scheduling CPU time. Memory management keeps track of ea...
Read more

Recommendation System viva questions/ Interview questions

Question 1: Can you provide an overview of the history of recommendation systems and their evolution over time? Answer: Recommendation systems have evolved significantly since their inception in the early 1990s. Initially, simple systems such as collaborative filtering and content-based filtering emerged, followed by more sophisticated techniques like matrix factorization and deep learning. The rise of e-commerce and streaming platforms in the late 1990s and early 2000s led to increased research and development in recommendation algorithms. Today, recommendation systems are ubiquitous across various domains, from e-commerce and entertainment to social media and content platforms, and continue to evolve with advancements in machine learning and artificial intelligence. Question 2: What are the main functions of a recommender system, and how do they contribute to enhancing user experience and engagement? Answer: The main functions of a recommender syste...
Read more