Design and Analysis of Algorithms MST Paper:Chandigarh University 2024-25

Usage Condition:

• 📖 Papers are for reference and study purposes only.
• 🧑‍🎓 Students should use them responsibly and not for any malpractice.
• 📅 Availability depends on the course and year.

Design and Analysis of Algorithms

Subject Code: 24CAT-611
Semester: 2 | Time: 1 Hour | Max Marks: 20

Section A

(5 × 2 = 10 Marks)

1. Define the general method of divide and conquer. (CO1 – BT1)
2. State greedy choice in the Fractional Knapsack problem. (CO2 – BT2)
3. Define minimum spanning tree and write down the time complexity of Prim’s algorithm. (CO3 – BT2)
4. List the algorithms used to solve the single-source shortest path problem. (CO3 – BT1)
5. Mention the typical applications of Huffman Trees in computer science. (CO3 – BT2)

Section B

(2 × 5 = 10 Marks)

6. Give five differences between max-heaps and min-heaps. (CO3 – BT3)
7. Apply the greedy strategy to determine the optimal solution for a fractional knapsack problem. (CO3 – BT3)