[go: up one dir, main page]
Scribd
Upload
41 views3 pages

Algorithm Questions Brief Answers

The document provides an overview of various algorithmic concepts including asymptotic analysis, complexity classes (P, NP, NP-Hard, NP-Complete), and specific algorithms like KMP, backtracking, binary search, quick sort, and greedy algorithms. It also discusses problem-solving techniques such as dynamic programming, divide and conquer, and branch and bound strategies, along with examples for clarity. Additionally, it differentiates between greedy and 0/1 knapsack problems, as well as divide and conquer versus dynamic programming approaches.

Uploaded by

yashpandey
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
41 views3 pages

Algorithm Questions Brief Answers

The document provides an overview of various algorithmic concepts including asymptotic analysis, complexity classes (P, NP, NP-Hard, NP-Complete), and specific algorithms like KMP, backtracking, binary search, quick sort, and greedy algorithms. It also discusses problem-solving techniques such as dynamic programming, divide and conquer, and branch and bound strategies, along with examples for clarity. Additionally, it differentiates between greedy and 0/1 knapsack problems, as well as divide and conquer versus dynamic programming approaches.

Uploaded by

yashpandey
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/ 3

Q1) What is Asymptotic analysis and define big O, big Omega and Theta notation?

Asymptotic analysis evaluates algorithm efficiency as input size grows. Big O: worst-case; Omega

(Omega): best-case; Theta (Theta): average-case or tight bound.

Q2) Define P class, NP class, NP hard, NP complete.

P: Problems solvable in polynomial time. NP: Verifiable in polynomial time. NP-Hard: At least as

hard as NP problems. NP-Complete: Both NP and NP-Hard.

Q3) What is Knuth Morris Pratt Method of pattern matching? Give examples.

KMP is a pattern matching algorithm using partial match table to avoid redundant checks. Example:

Searching 'ABABC' in 'ABABABC'.

Q4) Explain Backtracking with n-p queen problem.

Backtracking tries placing queens one by one, backtracks if conflicts arise. Solves N-Queens by

exploring valid positions recursively.

Q5) Explain Naive string machine algorithm with examples.

Naive algorithm checks pattern at each position in text. Example: Searching 'ABC' in 'AABCABC'

checks every position.

Q6) Explain binary search algorithm.

Binary search finds target in sorted array by repeatedly dividing search interval in half.

Q7) Explain Best case, Average case, and worst case.

Best: Minimum operations (ideal). Average: Expected operations. Worst: Maximum operations

(guaranteed upper bound).

Q8) What is greedy algorithm?

Greedy algorithm makes the locally optimal choice at each step, aiming for global optimum.

Q9) Explain quick sort algorithm with examples.

Quick sort partitions array around pivot, recursively sorts partitions. Example: [3,6,1] pivot=3 [1],

[6].

Q10) Explain multistage graph with example.

Multistage graph has stages and directed edges only to next stages. Used in shortest path
problems.

Q11) What is greedy algorithm?

Greedy algorithm builds up solution piece by piece choosing most promising option at each step.

Q12) Write an abstract algorithm for greedy design method.

1. Initialize solution set.

2. While feasible:

a. Select best option.

b. Add to solution.

3. Return solution.

Q13) Explain 0/1 knapsack problem using dynamic programming.

Choose items with max value under weight limit. DP stores max value for each weight limit and item

combination.

Q14) Write an algorithm to find the minimum and maximum value using divide and conquer and also

derive its complexity.

Divide array, find min/max in halves, combine. Complexity: O(n).

Q15) Explain recursion and various method to solve recurrences.

Recursion is when a function calls itself. Solve recurrences using substitution, recursion tree, or

master theorem.

Q16) Explain Job Sequencing with deadline with an example

Schedule jobs to maximize profit before deadlines. Example: Jobs with deadlines and profits are

sorted and scheduled greedily.

Q17) Explain 15-puzzle problem using branch and bound strategy.

Branch and bound solves by exploring states using heuristics and pruning unpromising branches to

reach goal state efficiently.

Q18) Differentiate between the following:

i) greedy knapsack and 0/1 knapsack.

ii) divide and conquer approach and dynamic programming.


i) Greedy takes items by ratio; 0/1 chooses entire item or none.

ii) Divide & conquer splits problems independently; DP solves overlapping subproblems.

You might also like