Design & Analysis of Algorithms B.Tech Question Bank : tits.ac.in

Name of the College : Turbomachinery Institute of Technology &Sciences (TITS)
University : JNTU Hyderabad
Department : Computer Science Engineering
Subject Name : Design And Analysis Of Algorithms
Degree : B.Tech
Year/Sem : II/II
Website : tits.ac.in
Document Type : Question Bank

Download Model Question Paper : https://www.pdfquestion.in/uploads/tits.ac.in/3050-daaqb.pdf

TITS Design & Analysis Of Algorithms Question Paper

UNIT – I

QUESTIONS:

Related : TITS Principles Of Programming Languages B.Tech Question Bank : www.pdfquestion.in/3063.html

1. A) Explain the asymptotic notations used in algorithm analysis. [Apr/May 2007]
B) Prove that f (n) =0(h (n)) where f (n) =0(g (n)) and g (n) =0(h (n)
2. A) Describe the performance analysis in detail. [Apr/May 2008] [Apr/May 2007]
B) Show that f1 (n) +f2 (n) = 0(max (g1(n), g2(n)) where f1(n) = 0(g1(n)) and f2(n) =0(g2(n)).
3. Define time complexity. Describe different notations used to represent there complexities. [Apr/May 2009] [Apr/May 2007] [Apr/May 2008] [Apr/May 2006] [Apr/May 2010]
4. Derive the function f(n)= 12n2+6n is 0(n3) and w(n).
5. Define an algorithm. Describe the characteristics of the algorithm? [Apr/May 2009] [Apr/May 2007]

6. Differentiate between profiling and debugging. . [Apr/May 2009] [Apr/May 2008]
7. Differentiate between priori analysis and posterior analysis. . [Apr/May 2009] [Apr/May 2008]
8. describe the various criteria’s used for analyzing the algorithms?
9. Write the non-recursive algorithm for finding the Fibonacci sequence and derive its time complexity. [Apr/May 2009] [Apr/May 2007] [Aug 2008]
10. Show that f(n) = 4n2-64n + 288 =(n)2. [Aug 2008]
11. Show that f(n)+g(n)=O (n2) where f(n) = 3n2 – n + 4 and g(n)=nlogn+5 [Apr/May 2009] [Aug 2008]
12. Explain how time complexity of an algorithm is computed.
13. Define omega notation. Explain the terms involved in it. Give an example.
14. What do you mean by input size of a problem? Explain its significance? [Apr/May 2006] [2007]

UNIT – II

QUESTIONS:
1. Explain the properties of strongly connected components? [Apr/May 2007]
2. Write a pseudo code for finding the strongly connected components of directed graph. Also analyze its time complexity? [Aug 2008]
3. Write an algorithm of bi connected components and also analyze its time complexity?
4. Find a necessary and sufficient condition for the root of a DFS for a connected graph to be an articulation point. Prove it? [Apr/May 2009] [Apr/May 2007] [Aug 2008]
5. Explain with an example how a graph can be transformed into a bi connected graph?
6. Explain the properties of strongly connected components? [Apr/May 2009] [Aug 2008]
7. Develop algorithms for UNION and FIND using weighing rule and collapsing rule respectively?
8. Write a pseudo code for the implementation of UNION using linked list? [Apr/May 2009] [Aug 2008]

UNIT – III

Syllabus :
Divide and conquer: General method, applications-Binary search, Quick sort, Merge sort, Strassen’s matrix multiplication.

Questions :
1. List some of the relative advantages and disadvantages of the partition algorithm? [Apr/May 2007]
2. Write the Quick sort algorithm? Analyze the time complexity in worst case?
3. Explain the Strassen’s matrix multiplication. [Apr/May 2009] [Apr/May 2007] [Aug 2008]
4. Write deletion algorithm, of Binary search tree.
4. Write and explain the control abstraction algorithm of divide and conquer? [Aug 2008]
5. Write and explain the control abstraction for Divide and conquer.
(b) Suggest refinements to merge sort to make it in-place.
6. Prove that the lower bound for the number of comparisons in any comparison sort (e.g. Heap Sort or Quick Sort or Merge Sort) is Ω (n log n). [Where log means 1og2]
7. Sort the following elements using quick sort? 12, 24,8,67,34,21,78
8. Give a detail note on divide and conquer method?
9. Write deletion algorithm of Binary search tree?
10. Derive the time complexity for binary search? [Aug 2008]
11. Analyze the average case time complexity of quick sort? [Apr/May 2009] [Aug 2008]
12. Give the time complexity of generic divide and conquer algorithm?
13. Compare and contrast divide and conquer approach and greedy approach?
14. Explain merge sort with example?

UNIT – IV

Syllabus :
Greedy method: General method, applications-Job sequencing with dead lines, 0/1 knapsack problem, Minimum cost spanning trees, Single source shortest path problem.

Questions :
1. How many comparisons of edge weights will be done by the minimum spanning tree algorithm, in total, if the input is a complete undirected graph with n vertices and vi is the start vertex. [Apr/May 2007]
2. Design a linear-time algorithm for solving the single source shortest path algorithm for directed a cyclic graphs represented by their adjacency linked lists.
3. Write Greedy algorithm to generate shortest path. [Apr/May 2009] [Apr/May 2007] [Aug 2008]
4. If p1/w1 _ p2/w2……… _ pn/wn prove that knapsack generates an optimal Solution to the given instance of the knapsack problem
5. Write a greedy algorithm to the Job sequencing with deadlines.
6. Prove that the edge with the smallest weight will be part of every minimum Spanning tree.