Design and Analysis of Algorithms Final Examination Paper:Chnadigarh University

📘 Chandigarh University – MCA/BCA/B.Tech

These Semester papers are part of the official examinations of Chandigarh University,
designed to test knowledge and practical understanding of core MCA, Computer Applications, and B.Tech subjects.

💡 Each paper encourages students to think critically, apply concepts, and showcase problem-solving skills — helping them prepare for real-world IT challenges.

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: 25MCA348
Semester: 1 | Time: 3 Hours | Max Marks: 60

Section A

(5 × 2 = 10 Marks)

What is pseudocode, and how is it used in algorithm design? (CO1)
Define the greedy method in algorithm design. (CO2)
State the minimum number of colors required to color a bipartite graph. (CO4)
State the time complexity of Warshall’s Algorithm. (CO4)
Explain the worst-case time complexity of the sum of subsets problem. (CO3)

Section B

(4 × 5 = 20 Marks)

List the steps of the linear search algorithm. (CO3)
Differentiate depth-first search (DFS) and breadth-first search (BFS) algorithms. (CO2)
Construct a Huffman Tree for the given set of characters:
{a: 5, b: 9, c: 12, d: 13, e: 16, f: 45}.
Draw the corresponding Huffman coding. (CO3)
Draw the control structure for the DAA Knapsack Problem using dynamic programming. (CO3)

Section C

(3 × 10 = 30 Marks)

Discuss the importance of heap construction. Explain how the heap property is maintained during the process of building a max-heap. (CO5)
Explain the process of building a max-heap from the following list: {4, 10, 3, 5, 1, 8, 9}. (CO5)
Define Warshall’s Algorithm for computing the transitive closure of a graph and demonstrate its working with an example. (CO3)
OR
How can graphs be represented using adjacency matrix and adjacency list? Discuss the advantages and disadvantages of each representation. Analyze the complexity of graph algorithms using these representations. (CO3)