Oct 17, 2017, 08:48 AM

## News:

IT Acumens Proudly Presents "Gin Gly": Sms Backup / Contacts Backup / Sms Grouping Website Used by Members 85,000 - SMS Backed up 7,25,000 - Contacts Stored  28,850. For 5 Years !!

## May - 2008 DESIGN & ANALYSIS OF ALGORITHMS Question paper

Started by ganeshbala, Apr 23, 2009, 03:49 AM

Go Down

#### ganeshbala

##### Apr 23, 2009, 03:49 AM
May - 2008 DESIGN & ANALYSIS OF ALGORITHMS Question paper

2008 OSMANIA UNIVERSITY M.C.A COMPUTER APPLICATIONS

MCA II YEAR II SEMESTER (New) MAIN EXAMINATION
May - 2008
DESIGN & ANALYSIS OF ALGORITHMS
CODE NO. : 3828/N
Time : 3 Hours
Max. Marks : 80
Note : Answer one question from each unit. All questions carry equal
marks.
UNIT - I
1. (a) Briefly explain how to analyze algorithms. [Marks 8]
(b) What is Heap ? How to delete an element from the Heap ? [Marks 8]
OR
2. (a) Define the following notations
(i) BigOh
(ii) Omega
(iii) Theta [Marks 8]
(b) Write an algorithm to add an element to a circular queue. [Marks 8]
UNIT - II
3. Write the quick sort algorithm using divide and conquer strategy. [Marks 16]
OR
4. What is minimum spanning tree ? Write Prim's algorithm for finding minimum
spanning tree. [Marks 16]
UNIT - III
5. Write BFS and DFS algorithms. Explain their working with suitable examples. [Marks
16]
OR
6. Write an algorithm to find an Optimal Binary Search tree using dynamic programming.
[Marks 16]
UNIT - IV
7. What is M-Colorability optimisation problem ? Write an algorithm that finds all MColorings
of a
Graph. [Marks 16]
OR
8. Explain how the branch and bound technique can be used to solve 0/1 Knapsack
problem. [Marks 16]
UNIT - V
9. State and prove Cook's Theorem. [Marks 16]
OR
10. What is Directed Hamiltonian Cycle ? Prove that CNF - Satisfiability reduces to
Directed Hamiltonian
Cycle. [Marks 16]

Go Up

With Quick-Reply you can write a post when viewing a topic without loading a new page. You can still use bulletin board code and smileys as you would in a normal post.

Warning: this topic has not been posted in for at least 120 days.
Unless you're sure you want to reply, please consider starting a new topic.

Note: this post will not display until it's been approved by a moderator.
Name:
Email:
Verification: