daa

Daa imp question

Unit – 1

1. a) Define an algorithm. Describe the Characteristics of the algorithm.

    b) Explain the Significance of input size of a problem?

2. a) Define time complexity.

b) Explain about asymptotic notations Big ‘O’, omega, and theta with 2 examples for each.

3. Write a non-recursive algorithm for finding the Fibonacci sequence & derive its time complexity.

4. a) Write a Recursive solution for the bubble sort

    b) Show that f(n) = 4n2 - 64n + 288 = omega(n2)

5. Write an algorithm to find largest of given ‘n’ numbers. Derive its time complexity using big Oh notation.

Unit – 2

1. Explain the usefulness of the following fundamental operations on sets.

     i) FIND              ii) UNION

2. Develop algorithms for UNION & FIND using weighting rule & collapsing rule respectively.

3. a) What are bi connected components? Explain.

    b) Define bi connected graph. Develop an algorithm that determines a connected graph is bi connected graph is bi connected or not

4. a) Explain BFS (Breadth First Search) with an example.

    b) Develop a Breadth - First Search Algorithm to find a spanning tree of a connected graph.

Unit – 3

1. a) Write & explain control abstraction of divide & conquer?

    b) Map the algorithm to find counterfeit coin to various steps of the control abstraction.

2. a) Explain how the recursive binary search algorithm works?

    b) Derive its complexity by repeated substitution or explain intuitively.

3. a) Explain the recurrence Relation for the merge sort

    b) Derive time complexity of the above recurrence relation by repeated substitution.

4. What is the principle of partitioning in quick sort? Give algorithm & one example.

5. Show how procedure QUICKSORT sorts the following the sets of keys:

(1,1,1,1,1,1,1) and (5,5,8,3,4,3,2).

Unit – 4

1. Compare Greedy & Divide & Conquer methods with suitable examples for each.

2. Explain the Knapsack problem. For the following instance, n=3, m=6, (w1, w2, w3) = (2, 3, 4), (p1, p2, p3) = (1, 2, 5), Write all the possible feasible solutions. Which of these solutions yields the maximum profit?

3. Write prim’s algorithm for finding minimum cost spanning tree for a connected graph?

4. a) Explain the procedure of job sequencing with dead line with an example.

b) Map the Greedy algorithm to change making example with various steps of the control abstraction.

5. Write Diikstra’s greedy algorithm to generate single - source shortest paths?

download