# Lecture Plans

UNIT-1

1. Define Algorithm & Notion of algorithm.

2. What is analysis framework?.

3. What are the algorithm design techniques?.

4. How is an algorithm’s time efficiency measured?.

5. Mention any four classes of algorithm efficiency.

6. Define Order of Growth.

7. State the following Terms.

(i) Time Complexity

(ii) Space Complexity

8. What are the various asymptotic Notations?

9. What are the important problem types?

10. Define algorithmic Strategy (or) Algorithmic Technique.

11. What are the various algorithm strategies (or) algorithm Techniques?.

12. What are the ways to specify an algorithm?.

13. Define Best case Time Complexity .

14. Define Worst case Time Complexity.

15. Define Average case time complexity.

16. Define Asymptotic Notation.

17- Describe the steps in analyzing & coding an algorithm.

18- Explain some of the problem types used in the design of algorithm.

19- Explain the various asymptotic notations used in algorithm design.

20. Describe briefly the notions of complexity of an algorithm.

UNIT-II

1. Explain Quick sort algorithm with suitable Example.

2. Find the number of comparisons made by the sequential Search in the worst & best case.

3. Give the time efficiency & Drawback of merge sort Algorithm.

4. What is the difference between DFS & BFS?

5. What is the Brute Force Algorithmic Strategy?

6. State the time complexity of following:

(i) Bubble sort

(ii) Selection sort

(iii) Sequential search

(iv) Brute force string matching

7. How efficient is prim’s algorithm?

8. Give any two strength & Weakness of Brute force algorithm.

9. Explain Brute force string matching algorithm.

10. Define “Divide & Conquer Technique”.

11. 12. Define Merge sort & explain three steps of Merge sort.

13. Define Quick sort & explain three steps of Quick sort.

14. Define Binary Search.

15. What are the applications of binary search?

16. State advantages & Disadvantages of binary search.

17. Explain Binary search tree.

18. What is the recurrence relation for divide & conquer?

19. Explain Decrease & Conquer.

20. What are the variations of Decrease & Conquer?

21. What are the applications of decrease by constant?

22. Write any four advantages of insertion sort.

23. What are the two types of searching algorithm?

UNIT-III

1. What is pre-sorting? Give examples.

2. How efficient is prim’s algorithm?.

3. Define concept of transform & conquer..

4. What are the three variations of transform & conquer?.

5. State the following terms:.

(i) Balanced Tree.

(ii) Unbalanced Tree.

6. What is height of balanced tree?.

7. What is balance factor?.

8. Define rotation & what are the four types of rotations?.

9. What are the drawbacks of AVL trees?.

10. What are 2-3 trees?.

11. Define Heap. & what are the two types heaps?.

12. What are the important properties of heap?.

13. Define complete binary tree..

14. What is the height of the tree?(or)depth of the tree?.

15. Define almost complete binary tree.

16. How to construct a heap?.

17. What are the features of heap sort?.

18. Define heap sort..

19. State the properties of AVL trees.

20. What is dynamic programming?.

21. Compare divide & conquer and Dynamic programming.

22. How the problems can be solved using dynamic programming?.

23. Define Warshall’s algorithm..

24. Define Floyd’s algorithm..

25. Give any two properties of dynamic programming approach.

26. Define principle of optimality.

27. Compare Greedy algorithm & Dynamic programming..

28-What is Traveling Salesman Problem (TSP)? Explain with an example.29-Give the Warshall’s.

algorithm and analyze the efficiency..

30-Explain how you solve the All-Pairs-Shortest-Paths problem with an example.

31-Give the Floyd’s algorithm and analyze the efficiency.

32-Explain LCS with Example?.

33- Explain Matrix multiplication Algorithm with Example?.

UNIT-IV

1. Define Backtracking.

2. What are the applications of backtracking?

3. What are the algorithm design techniques?

4. Define n-queens problem.

5. Define Hamiltonian Circuit problem.

6. Define sum of subset problem.

7. What is state space tree?

8. Define Branch & Bound method.

9. Define assignment problem.

10. What is promising & non-promising node?

11. Define Knapsack’s problem.

12. Define Travelling salesman problem.

13. State principle of backtracking.

14. Compare Backtracking & Branch and Bound techniques with an example.

15. What are the applications of branch & bound?(Or)

What are the examples of branch & bound?

16. In Backtracking method, how the problem can be categorized?

17. How should be determine the solution in backtracking algorithm?

18. Obtain all possible solutions to 4-Queen’s problem.

19. Generate at least 3-solutions for 5-Queen’s problem.

20. Give a suitable example & explain the Breadth first search & Depth first search.

Unit-V

1.Explain the concept of Backtracking with an example.

2.Define P, NP and NP-Complete problems.

3.Explain the Branch and Bound technique with an example.

4.Give the Approximation Algorithm for NP-Hard problems.

5.Show the difference between polynomial and non-polynomial time complexity.

6.What is Knapsack problem? Give the solution to solve it using dynamic programming

technique.

7.What is Traveling Salesman Problem (TSP)? Explain with an example.

8.Show the difference between NP-hard and NP- completeness.

9.What are the application of 0/1 knapsack problem?

10.Define Knapsack’s problem