Scribd
Upload
9 views3 pages

Design and Analysis of Algorithms Exam

The document is a model examination paper for the Design and Analysis of Algorithms course at Meenakshi Sundararajan Engineering College. It includes three parts: Part A consists of 10 short answer questions, Part B contains 5 detailed questions with options, and Part C has 1 comprehensive problem. The exam covers various algorithmic concepts such as sorting, searching, optimization, and problem-solving techniques.

Uploaded by

j.priya
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
9 views3 pages

Design and Analysis of Algorithms Exam

The document is a model examination paper for the Design and Analysis of Algorithms course at Meenakshi Sundararajan Engineering College. It includes three parts: Part A consists of 10 short answer questions, Part B contains 5 detailed questions with options, and Part C has 1 comprehensive problem. The exam covers various algorithmic concepts such as sorting, searching, optimization, and problem-solving techniques.

Uploaded by

j.priya
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

MEENAKSHI SUNDARARAJAN ENGINEERING COLLEGE

CHENNAI 600 024


MODEL EXAMINATION – MAR 2019
Branch: IT Semester: IV
Subject Code:CS8451 Time:
Subject Name: Design and analysis of algorithm Maximum Marks: 100
Date:

PART A (10*2=20 Marks)


1. Design an algorithm to compute to find sum of n natural numbers
2. Define recurrence relation
3. Give the general strategy of divide and conquer approach
4. Differentiate linear search and binary search techniques
5. State the principle of optimality
6. How to calculate the efficiency of Dijikstra algorithm
7. What are explicit and implicit constraints
8. What is maximum cardinality matching
9. State the difference between LIFO and FIFO branch and bound problems
10. Define backtracking

PART B (5*13=65 Marks)


11.a. (i) Use the most appropriate notation to indicate the time efficiency class of
sequential search algorithm in the worst case,best case and average case(8)

(ii)State the general plan for analyzing the time efficiency of non-recursive algorithms and
explain with an example

(OR)

[Link] the fundamentals of algorithm problem solving

[Link] heap sort using divide and conquer strategy and perform the analysis of the
algorithm

(OR)

12.b. Explain the concept of binary search using divide and conquer and perform the analysis
of the algorithm

[Link] optimal binary search [Link] 4 elements a1<a2<a3<a4 with


q0=0.25,q1=3/16,q2=q3=q4=1/16.p1=1/4,p2=1/8,p3=p4=1/16

(OR)

[Link] kruskal’s algorithm to find the minimum spanning tree for the following graph
14.a. Explain stable marriage problem briefly

(OR)

14.b. Explain the steps in simplex method and explain the efficiency of same

[Link] 8-Queens problem with an algorithm. Explain why backtracking is the default
procedure for solving problems.

(OR)

15.b. Solve the following instance of knapsack problem by branch and bound algorithm

PART C (1*15=15Marks)

16.a.(i)Apply warshall algorithm to find the transitive closure of a digraph defined by the
following adjacency matrix.

(ii)Prove that the time efficiency is cubic


(OR)

16.b. (i)Using backtracking technique solve the following instance of the subset sum
Problems s= (1, 3, 4, 5) and d=11 (7)
(ii) Explain how job assignment problem could be solved, given n tasks and n agents
where each agent has a cost to complete each task using Branch and Bound technique. (6)

You might also like