ADA

 Analysis  & Design of Algorithm

3150703

Important Question for GTU Final Exam

Chapters - 1& 2

Basics of Algorithms and Mathematics & Analysis of Algorithm

1. Define following terms (i) Quantifier (ii) Algorithm (iii) Big ‘Oh’ Notation (iv) Big ‘Omega’ Notation (v) ‘Theta’ Notation.
2. Explain an algorithm for Selection Sort Algorithm. Derive its best case, worst case and average case time complexity.
3. Sort the given elements with Heap Sort Method: 20, 50, 30, 75, 90, 60, 25, 10, 40.
4. Why do we use asymptotic notations in the study of algorithms? Briefly describe the commonly used asymptotic notations.
5. Apply the bubble sort algorithm for sorting {U,N,I,V,E,R,S}
6. Let f(n) and g(n) be asymptotically nonnegative functions. Using the basic definition of Θ-notation, prove that max(f(n), g(n)) = Θ (f(n) + g(n)).
7. Define an algorithm. List various criteria used for analyzing an algorithm.

Chapters - 3

     Divide and Conquer Algorithm

1. What is a recurrence? Solve recurrence equation T (n) =T (n-1) + n using forward substitution and backward substitution method.
2. Write an algorithm for quicksort and derive best case, worst case using divide and conquer technique also trace given data (3,1,4,5,9,2,6,5)
3. Explain the use of the Divide and Conquer Technique for Binary Search Method. What is the complexity of the Binary Search Method? Explain it with example.
4. Write a program/algorithm of Quick Sort Method and analyze it with example.
5. Solve the following recurrence using master method T(n) = 9T(n/3) +n.
6. Solve the following recurrence using master method T(n) = T(2n/3) + 1.
7. What do you mean by Divide & Conquer approach? List the advantages and disadvantages of it.
8. Solve the following recurrence relation using the iteration method. T(n) = 8T(n/2) + n2 . Here T(1) = 1.
9. Solve the following recurrence relation using the substitution method. T(n) = 2T(n/2) + n. Here T(1) = 1.
10. Multiply 981 by 1234 by divide and conquer method.
11. Sort the letters of word “EDUCATION” in alphabetical order using insertion sort.

Chapters - 4

Dynamic Programming

1. Write equation for Chained matrix multiplication using Dynamic programming. Find out optimal sequence for multiplication: A1 [5 × 4], A2 [4 × 6], A3 [6 × 2], and A4 [2 × 7]. Also give the optimal parenthesization of matrices.
2. Explain how to find out Longest Common Subsequence of two strings using Dynamic Programming method. Find any one Longest Common Subsequence of given two strings using Dynamic Programming.  X=abbacdcba & Y=bcdbbcaac
3. Solve Making Change problem using Dynamic Programming. (Denominations: d1=1, d2=4, d3=6). Give your answer for making change of Rs. 9.
4. Discuss Assembly Line Scheduling problem using dynamic programming with example.
5. Solve Making change problem using dynamic technique. D1 = 1, d2=3, d3=5, d4=6. Calculate for making change of Rs. 8.
6. Find optimal sequence of multiplication using dynamic programming of following matrices: A1[10x100], A2[100x5], A3[5x50] and A4[50x1]. List optimal number of multiplication and parenthesization of matrices.
7. Discuss and derive an equation for solving the 0/1 Knapsack problem using dynamic programming method.

Chapters - 5

Greedy Algorithm 

1. Using greedy algorithm find an optimal schedule for following jobs with n=6. Profits: (P1,P2,P3,P4,P5,P6) = (20, 15, 10, 7, 5, 3) Deadline: (d1,d2,d3,d4,d5,d6) =(3, 1, 1, 3, 1, 3).
2. Define MST. Explain Kruskal’s algorithm with example for construction of MST.
3. Explain Dijkstra algorithm to find the shortest path.
4. Explain in brief characteristics of greedy algorithms. Compare Greedy Method with Dynamic Programming Method
5. List applications of a minimum spanning tree. Find minimum spanning tree using PRIM’s algorithm of the following graph.
6. Prove that the fractional knapsack problem has the greedy-choice property.

Chapters - 6

Exploring Graphs

1. Explain Breath First Traversal Method for Graph with algorithm with example.
2. Explain Depth First Traversal Method for Graph with algorithm with example.
3. Explain: Articulation Point, Graph, and Tree.
4. Define graph. Describe strongly connected graph with example.
5. Given an adjacency-list representation of a directed graph, how long does it take to compute the out-degree of every vertex? How long does it take to compute the in-degrees?

Chapters - 7

Backtracking and Branch and Bound

1. Explain Backtracking Method. What is N-Queens Problem? Give solution of 4- Queens Problem using Backtracking Method.
2. Explain 4 queen problems with one of the solution.
3. Define backtracking. State types of constraints used in backtracking.

Chapters - 8 & 9

String Matching  & Introduction to NP-Completeness

1. What is Finite Automata? Explain use of finite automata for string matching with suitable example.
2. Define P, NP, NP complete and NP-Hard problems. Give examples of each.
3. Give and explain Rabin-Carp string matching algorithm with example.
4. What is the basic idea behind Rabin – Karp algorithm? What is expected running time of this algorithm? Explain it with example.
5. Explain naïve string matching algorithm with example.
6. Explain Traveling salesman problem with example.
7. Show the comparisons the naive string matcher makes for the pattern P=0001 in the text T=000010001010001.
8. Working modulo q=11, how many spurious hits does the Rabin-Karp matcher encounter in the text T=3141592653589793 when looking for the pattern P=26?