DESIGN AND ANALYSIS OF ALGORITHMS B.Tech. III Year I Sem JNTUH R18

• Define the following asymptotic notations and give an example of an algorithm for each: Big-Oh, Omega, Theta, and Little-oh.

• Describe the steps involved in the Divide and Conquer algorithm design strategy. Provide pseudocode examples for Merge Sort and Quick Sort.

• Explain the concept of time complexity and space complexity. For a given algorithm, analyze its time and space complexity.

UNIT - II Disjoint Sets and Backtracking

• What is a disjoint set data structure? How are 'union' and 'find' operations implemented using this structure?

• Discuss the Backtracking technique for problem-solving. Explain how it is applied to solve the N-Queens problem.

• Provide a scenario where using backtracking would be a suitable (or unsuitable) algorithmic approach. Justify your answer.

UNIT - III Dynamic Programming

• Differentiate between the Greedy method and the Dynamic Programming method. In what situations is Dynamic Programming a more appropriate problem-solving strategy?

• Write pseudocode for the 0/1 knapsack problem using Dynamic Programming.

• Describe how Dynamic Programming is applied to finding the optimal path in the Traveling Salesperson Problem (TSP).

UNIT - IV Greedy Method

• Explain the Greedy algorithm design technique. What are the potential drawbacks of using this approach?

• Describe the Kruskal's algorithm for finding the Minimum Cost Spanning Tree (MST) in a graph. Write the pseudocode and explain its logic.

• Apply the Greedy method to solve the Job Sequencing with Deadlines problem. Analyze the time complexity of your solution.

• Discuss the Activity Selection problem and explain why a simple Greedy approach might not always yield the optimal solution.

• Compare and contrast the Greedy method with Dynamic Programming, highlighting their key differences and areas of applicability.

UNIT - V Branch and Bound and NP-Hard and NP-Complete problems

1. Describe the Branch and Bound algorithm design paradigm. Explain how it is used to find optimal solutions for problems with exponential search space.

2. Differentiate between Least Cost (LC) Branch and Bound and First-In-First-Out (FIFO) Branch and Bound approaches. Discuss their advantages and disadvantages.

3. Define the terms P, NP, NP-Hard, and NP-Complete problems. Provide examples of problems belonging to each category.

4. Explain Cook's Theorem and its significance in the context of NP-completeness.

5. Prove the NP-completeness of a problem like the Vertex Cover Problem or the 3-SAT problem.