Scribd
Upload
20 views

Alg Cse

Uploaded by

yuvashree.cse
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
20 views

Alg Cse

Uploaded by

yuvashree.cse
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
You are on page 1/ 1

13.

a) Using the divide and conquer approach to find the maximum and minimum in
MADHA INSTITUTE OF ENGINEERING & TECHNOLOGY a set of ‘n’ elements. Also find the recurrence relation for the number of elements
(Approved by AICTE & Affiliated to Anna University, Chennai) compared and solve the same.
Sadhanandhapuram, Erandamkattalai (OR)
Chennai – 600 128 b) i) Let A ={l/119,m/96,c/247,g/283,h/72,f/77,k/92,j/19} be the letters and its
MODEL EXAM Date: 11.06.2024 frequency of distribution in a text file. Compute a suitable Huffman coding to
Department of IT compress the data effectively.
Branch: CSE Year / Sem : II /04 Reg.no: ii)Write an algorithm to construct the optimal binary search tree
given the roots r(i,j) ,0≤i≤j≤n. Also prove that this could be
Course Code/Name: CS 3401- ALGORITHMS Marks: 100 performed in time O(n)
PART – A
ANSWER ALL THE QUESTIONS (10X02 = 20marks) 14. a) i)Explain the control abstraction for Backtracking method. Describe the
1. What do you mean by algorithm? backtracking solution to solve 8-Queens problem
2. Define recurrence ii) Let w= {5, 7, 10, 12, 15, 18, 20} and m=35.Find all possible subset of
3. Define a graph.. w whose sum is equivalent to m. Draw the portion of state space tree for
4. What is a Spanning Tree? this problem.
5. Give the general plan for divide-and-conquer algorithms. (OR)
6. Define dynamic programming b) i) Draw a decision tree and find the number of key comparisons in the worst
7. What is backtracking? and average cases for the three element bubble sort. (8) (NOV/DEC 2016)
8. Define state space tree (AN) (ii) Write backtracking algorithm for 4 queen’s problem and discuss the
9. What are NP- hard and NP-complete problems? possible solution..
10. Define P and NP problems. 15. a) Implement an algorithm for Knapsack problem using NP-Hard approach
(OR)
PART –B (5X13 = 65 Marks) b) Discuss the approximation algorithm for NP hard problem
11. a) Define the asymptotic notations used for best case average case and
worst case analysis? PART –C (1X15 = 15 Marks)
(OR) 16.a) Using backtracking, find the optimal solution to a knapsack problem for the
b) i) Explain how analysis of linear search is done with a suitable knapsack instance n=8, m=110,(p1…p7)=(11,21,31,33,43,53,55,65) and (w1…
illustration. w7)=(1,11,21,33,43,53,55,65)
ii) Define recurrence equation and explain how solving recurrence (OR)
equations are done b) Write the algorithm for quick sort. Provide a complete analysis of quick sort for
the given set of numbers 12,33,23,43,44,55,64,77 and 76.
12. a) How do you construct a minimum spanning tree using Kruskals
algorithm? Explain? ..ALL THE BEST..
(OR)
b) Explain Dijkstra’s algorithm using the following graph. Find the
shortest path between v1, v2, v3, v4, v5, v6 & v7..

You might also like