Question Bank 1

 

 Basic Questions for Practise : Part 1 : 

---

 

• What is an algorithm?
  → Define what an algorithm is and its basic characteristics.

• What are the different types of algorithm design techniques?
  → Examples: Divide and Conquer, Dynamic Programming, Greedy Method, Backtracking, etc.

• What is time complexity?
  → Explain how the running time of an algorithm is measured.

• What is space complexity?
  → Define how much memory an algorithm uses during execution.

• What is Big O notation?
  → Explain its use in representing the upper bound of an algorithm’s growth rate.

• What is the difference between best case, worst case, and average case complexity?
  → Describe with examples (like linear search or binary search).

• What is Divide and Conquer technique? Give an example.
  → Example: Merge Sort, Quick Sort, Binary Search.

• What is a greedy algorithm? Give an example.
  → Example: Kruskal’s or Prim’s algorithm for Minimum Spanning Tree.

• What is Dynamic Programming?
  → Explain with an example such as Fibonacci series or shortest path (Floyd-Warshall).

---

 

Part 2: 

                                                                                                  

1. Define Algorithms and its Design Strategies.

---

 

2. What is the recurrence relation of Merge Sort? Derive its time complexity for best and worst case.

---

 

3. List the properties of Binomial Tree.

---

 

4. Define Greedy Method.

---

 

5. Sort the following array by counting sort. A= {2,5,3,0,2,3,0,3}

---

 

6. What is the stable sorting algorithm? Which of the sorting algorithms(in our syllabus) are stable and which are unstable?

---

 

7. Explain B-trees and its properties. Also write the algorithm for deletion cases with example.

---

 

8. Insert the following elements using RB tree. {61,58,51,32,39,29}

---

 

9. Write a pseudocode for Dijkstra’s algorithm for single source shortest path with the help of an example.

---

 

10. Write the Pseudocode of partitioning algorithm of Quick Sort.  Use Quick Sort to sort {4,3,1,2,5,9,7,1,6}

---

 

11. Describe the Master’s theorem. Solve the following recurrence relations by using Master’s theorem.

a)T(n)=4T(n/2)+n

b)T(n)=2T(n/2)+nlogn

---

 

12. What is Skip List? Explain the Search operations in Skip List with the help of an example.

---

 

13. Explain the different conditions of getting union of two existing Binomial Heaps. Also write algorithm for union of two Binomial Heaps. What is its complexity?

---

 

14. Discuss about fractional knapsack problem. Consider the following instance of knapsack problem:

n=3 and m=20, Profits: (p1,p2,p3)=(25,24,15)Weights: (w1,w2,w3)=(18,15,10)

---

 

15. Obtain the optimal solution using greedy approach.

---

 

16. Prove that if the weights on the edge of the connected undirected graph are distinct, then there is a unique Minimum Spanning Tree. Give an example in this regard. Also discuss Prim’s Minimum Spanning Tree Algorithm in detail.

    ---

     

17. Write algorithm for Bubble sort .

    ---

     

 

18. Explain the logic  for insertion and merge sort .