Scribd
Upload
6 views2 pages

Design and Analysis of Algorithms Exam

This document outlines the CAT-11 examination for the Design and Analysis of Algorithm course at Thangavelu Engineering College, detailing the structure of the exam, including Part A with short answer questions and Part B with longer, detailed questions. Topics covered include dynamic programming, knapsack problems, Dijkstra’s algorithm, and various graph theories. The exam is scheduled for October 24, 2024, with a total of 100 marks available.

Uploaded by

petri.success
Copyright
© All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as DOCX, PDF, TXT or read online on Scribd
6 views2 pages

Design and Analysis of Algorithms Exam

This document outlines the CAT-11 examination for the Design and Analysis of Algorithm course at Thangavelu Engineering College, detailing the structure of the exam, including Part A with short answer questions and Part B with longer, detailed questions. Topics covered include dynamic programming, knapsack problems, Dijkstra’s algorithm, and various graph theories. The exam is scheduled for October 24, 2024, with a total of 100 marks available.

Uploaded by

petri.success
Copyright
© All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as DOCX, PDF, TXT or read online on Scribd

THANGAVELU ENGINERING COLLEGE

KARAPAKKAM, CHENNAI -97.


CAT –11 EXAMINATION
DESIGN AND ANALYSIS OF ALGORITHM

Sub code: AD3351 Time:3 Hrs


Sub Name: Design and analysis of algorithm
Date: 24-10-2024
Maximum:100 marks
PART - A ( 5x 2 = 20 marks)
[Link] the general procedure of dynamic programming?
[Link] are the variants of knapsack problem?
[Link] how dynamic programming solves the complex problems?
[Link] the application that makes use of dynamic programming for the solution?
[Link] with an example where the principles of optimality do not hold.
[Link] the iterative improvement techniques.
[Link] is linear programming problem?
[Link] is bipartite graph?
[Link] is maximum cardinality matching?
[Link] is the purpose of Dijkstra’s algorithm?

PART - B ( 5x13 = 65 marks)


11.a). Write down and explain the algorithm to solve all pair shortest path algorithm(13)

(OR)
11.b) Write the algorithm to compute the Knapsack problem using dynamic programming
and explain (13)

12.a). Write an algorithm to construct an optimal binary search tree with suitable example.
(13)
(OR)
12.b) Explain in detail about Dijkstra’s Algorithm (13)
13.a). Discuss in detail about stable marriage problem (13)
(OR)
13.b). Explain about simplex method with suitable examples. (13)

14.a). Explain about bipartite graph with a suitable example. (13)


(OR)
14.b) Explain about Huffman tree and coding with suitable examples (13)

15.a). Explain about coin changing problem. (13)


(OR)
15.b) Write detail notes for Warshall’s and Floyd algorithm (13)
PART-C (1*15=15)
16.a). State and prove Maximum Flow Min cut theorem (15)
(OR)
16.b).Explain - travelling salesman algorithm with suitable problem and find a solution
(15)

You might also like