Jawaharlal Nehru Technological University Hyderabad 2007 M.Tech Computer Science Design and Analysis of Algorithms - Question Paper

1.a) arrange the subsequent classes into inheritance hierarchies and where improper create new classes : Student, Lecturer, technician, Admin, Office, Lab, Post graduate student, undergraduate Student, Lecture and Building using C++ Syntax.
b) Write a C++ program to generate a fibbonacci series overloading a prefix operator
2.a) Develop a probabilistic algorithm to obtain the value of the integral dxx?-2024
b) provide the Big-oh notation definition and briefly explain the properties of such as notation with reference to commutative, Associate, reflexive, Symmetric and antisymmetric natures of the functions.
3.a) Show how matrix multiplication is carried out using the strassen’s method. obtain the complexity of the Strassen’s method.
b) Write the Binary search algorithm for deletion.
4.a) Show how prim’s algorithm can be implemented using heap.
b) discuss the job sequencing with deadlines with an example using the Greedy approach.
5. Consider a four – stage system with device kinds d1, d2, d3, d4. Let C1 = 30, C2 = 15, C3 = 20, C4 = 10. The cost of the system is C = 135. The reliabilities of the device kinds are
r1 = 0.9, r2 = 0.8, r3 = 0.5, r4 = 0.6.
6.a) Consider building a B-tree of degree four that is balanced four-way tree where every node can hold three data value and have 4 branches. Suppose it needs to contain the subsequent values
1,5,6,2,8,11,13,18,20,7,9
b) Show that the inorder and preorder sequences of a binary tree uniquely describe the binary tree.
7. Solve the Traveling salesperson issue having the subsequent cost-matrix using branch-and-bound technique.
8 seven three 12 8
3 eight six 14 9
5 eight 8 six 18
9 three five eight 11
18 14 nine eight 8
8.a) elaborate non deterministic algorithms. Devise a non-deterministic algorithm for the satisfiability issue.
b) Prove that decision issue (CDP) ? node cover decision issue.

Earning:   Approval pending.