Cerocks.files.wordpress.com



Charotar Institute of Technology-Changa

U. & P. U. Patel Department of Computer Engineering

Question Bank

Subject Name: Algorithm Analysis & Design

Subject Code: 150703

|UNIT 1: Basics of Algorithms and Analysis |

|Sr. No |Question |Marks |

| |What is an elementary operation? |1 |

| |What is a program step? |1 |

| |What is Asymptotic Notation? |1 |

| |How do we divide algorithms? How algorithms do validated? How algorithms do analyzed? |2 |

| |Compare the two functions n2 and 2n/4 for various values of n. Determine when the second becomes larger than the |2 |

| |first. | |

| |What does O (1) mean? |2 |

| |Prove that if f (n) is O (n) then (f (n)) 2 is O (n2). |2 |

| |Define: 1. Space Complexity 2. Time Complexity |2 |

| |Differentiate: a priori estimates and a posteriori testing. |2 |

| |Define: Big “oh”, Omega, Theta |2 |

| |What do you mean by correct algorithm? What do you mean by instance of a problem? |2 |

| |What is an algorithm? List out the criteria that all algorithms must satisfy. On what bases will you consider |2 |

| |algorithm A is better than algorithm B? | |

| |What kinds of problems are solved by algorithms? |2 |

| |What is the smallest value of n such that an algorithm whose running time is 100n2 runs faster than an algorithm |2 |

| |whose running time is 2n on the same machine? | |

| |Suppose we are comparing implementations of insertion sort and merge sort on the same machine. For input of size n, |3 |

| |insertion sort runs in 8n2 steps, while merge sort runs in 64n lg n steps. For which values of n does insertion sort| |

| |beat merge sort? | |

| |How can we modify almost any algorithm to have a good best-case running time? |3 |

| |Is 2n+1 = O (2n)? Is 22n = O (2n)? |3 |

| |Explain why the statement, “The running time of algorithm A is at least O (n2),” is meaningless. |3 |

| |Solve the following recurrence: |4 |

| |[Homogeneous recurrences] | |

| |fn = n if n=0 or n=1 | |

| |fn =f n-1 + f n-2 otherwise | |

| |[Homogeneous recurrences] |4 |

| |tn=0 if n=0 | |

| |=5 if n=1 | |

| |=3tn-1 + 4tn-2 otherwise | |

| |[Inhomogeneous recurrences] |4 |

| |tn-2tn-1=3n | |

| |[change of variable] |4 |

| |T(n) = 4 T(n/2)+n2 | |

|UNIT 2: Greedy Algorithm |

| |The fractional problem can be solved greedily while the 0-1 problem cannot be solved with a greedy approach. Justify|2 |

| |the sentence. | |

| |Dynamic programming can be overkill; greedy algorithms tend to be easier to code. Justify the sentence. |2 |

| |Is Prim’s algorithm greedy? Why? |2 |

| |Is Kruskal’s algorithm greedy? Why? |2 |

| |What will be the running time of Prim’s algorithm? |2 |

| |What will be the running time of Kruskal’s algorithm? |2 |

| |List out the various properties for Shortest Path. |2 |

| |What are the difference between greedy algorithm and dynamic programming? |4 |

| |What is meant by greedy Algorithm? What is the application of it? |4 |

| |What are the general characteristics of Greedy algorithms? |4 |

| |Explain Amortized Analysis with example. |4 |

| |Which edges form the minimum spanning tree (MST) of the below graph? |4 |

| | | |

| |[pic] | |

| |How the optimal solution to the fractional knapsack problem can be found with a greedy algorithm? |6 |

| |MST (Minimum Spanning Tree) problem has optimal substructure. Prove it |6 |

| |Write an algorithm for depth first search of a graph and explain with an example |6 |

| |Prove that any weighted connected graph with distinct weights has exactly one minimum spanning tree. |6 |

| |Describe Dijkstra's algorithm for single source shortest path problem. |6 |

|UNIT 3: Divide and Conquer Algorithm |

| |The divide-and-conquer approach doesn’t always give you the best solution. Justify the sentence. |2 |

| |What will be the best case and worst case for quick sort algorithm? |2 |

| |Which do you think is better, quick sort or BST Sort? Why? |2 |

| |What operations must a priority queue have? |2 |

| |Write a pseudo code for a divide and conquer algorithm for finding values of both the largest and the smallest |4 |

| |elements in any array of n numbers | |

| |Apply quick sort algorithm to sort the list E, X, A, M, P, L, E in alphabetical order. Draw the tree of recursive |4 |

| |calls made | |

| |How does divide and conquer improve the efficiency of searching in binary search? |4 |

| |Sort the following list in increasing order of numbers |4 |

| |9, 94, 45, 47, 28, 98, 65, 42, 78, 4, 11, 88, 6 | |

| |Using each of the following methods. | |

| |a. Quick Sort. | |

| |b. Merge Sort. | |

| |How does divide and conquer improve the efficiency of searching in binary search? |6 |

| |Suppose you have a divide and conquer algorithm for multiplying large matrices. Suppose your algorithm divides each |6 |

| |of the original n by n matrices into n/3 by n/3 matrices. Suppose that you have a way of multiplying and recombining| |

| |the n/3 matrices into the n by n product that requires 8 matrix multiplications and 5 matrix additions. What is the | |

| |complexity of your new algorithm (use Equation 7.1)? Does your algorithm perform better than Strassen's algorithm? | |

| |Draw the recursion tree for the merge-sort procedure on an array of 16 elements. Explain why memorization is |6 |

| |ineffective in speeding up a good divide-and-conquer algorithm such as merge-sort? | |

| |Which of these two functions given below is more efficient and Why? |6 |

| |What is the running time of TreeSearch() function? | |

| | | |

| |A. TreeSearch(x, k) | |

| |if (x = NULL or k = key[x]) | |

| |return x; | |

| |if (k < key[x]) | |

| |return TreeSearch(left[x], k); | |

| |else | |

| |return TreeSearch(right[x], k); | |

| | | |

| |B. TreeSearch(x, k) | |

| |while (x != NULL and k != key[x]) | |

| |if (k < key[x]) | |

| |x = left[x]; | |

| |else | |

| |x = right[x]; | |

| |return x; | |

|UNIT 4: Dynamic Programming |

| |What is the basic concept of dynamic programming? |1 |

| |List the sequence of development of dynamic programming. |2 |

| |Explain the elements of dynamic programming in brief. |4 |

| |Solve the following task assignment problem instance. |6 |

| | | |

| |1 | |

| |2 | |

| |3 | |

| | | |

| |a | |

| |4 | |

| |7 | |

| |3 | |

| | | |

| |b | |

| |2 | |

| |6 | |

| |1 | |

| | | |

| |c | |

| |3 | |

| |9 | |

| |4 | |

| | | |

| |How the Assembly line scheduling can be solved using dynamic programming? |6 |

| |How matrix chain multiplication problem can be solved using dynamic programming? |6 |

| |Given the following matrix dimensions, calculate the ‘m’ and‘s’ tables. |6 |

| |Matrix | |

| |Dimension | |

| | | |

| |A1 | |

| |30×35 | |

| | | |

| |A2 | |

| |35×15 | |

| | | |

| |A3 | |

| |15×5 | |

| | | |

| |A4 | |

| |5×10 | |

| | | |

| |A5 | |

| |10×20 | |

| | | |

| |A6 | |

| |20×25 | |

| | | |

| |Find an optimal parenthesization of a matrix-chain product whose sequence of dimension is |6 |

| |How to solve Longest Common Subsequence problem using dynamic programming? |6 |

| |How to solve main change problem using dynamic programming? |6 |

| |How to solve knapsack problem using dynamic programming? |6 |

|UNIT 5: Exploring Graphs |

| |What is preconditioning? |2 |

| |What is the use of DFS? |3 |

| |What is the use of BFS? |3 |

| |What is preorder, in order and post order traversal or a tree? |4 |

| |Explain recursive algorithm of DFS for undirected graph. |4 |

| |Explain recursive algorithm of DFS for directed graph. |4 |

|UNIT 6: String Matching |

| |Define String-matching problem. |1 |

| |What is preprocessing and matching time for naïve string matching algorithm? |1 |

| |What is preprocessing and matching time for Rabin-Karp algorithm? |1 |

| |What is preprocessing and matching time for naïve string matching algorithm? |1 |

| |What is preprocessing and matching time for string matching with finite automata? |1 |

| |Show the comparisons the naïve string matcher makes for the pattern P=0001 in the next T=000010001010001 |2 |

| |Explain spurious hit. |2 |

| |Compare all string matching algorithms |3 |

| |Suppose that all the characters in the pattern P are different. Show how to accelerate NAÏVE-STRING-MATCHER to run |3 |

| |in time O (n) on n-character text T. | |

| |Construct the string matching automata for the pattern P= aabab. |3 |

| |Explain Naïve string matching algorithm. |5 |

| |Write algorithm for Rabin-Karp string matching algorithm and explain in brief. |5 |

| |Construct the string matching automata for the pattern P= aabab and illustrate its operation on the text string T = |5 |

| |aaababaabaababaab. | |

| |Draw a state-transition diagram for a string-matching automaton for the pattern ababbabbababbababbabb over the |5 |

| |alphabet Σ = {a,b}. | |

| |Given two patterns P and P’, describe how to construct a finite automaton that determines all occurrences of either |5 |

| |pattern. Try to minimize the number of states in your automaton. | |

| |How would you extend the Rabin-Karp method to the problem of searching a text string for an occurrence of any one of|8 |

| |a given set of k patterns? Start by assuming that all k patterns have the same length. Then generalize your solution| |

| |to allow the patterns to have different lengths. | |

|UNIT 7: Introduction to NP-Completeness |

| |Define polynomial time algorithm? |1 |

| |Define Class P Problem. |1 |

| |Define Class NP problem. |1 |

| |Compare NP-Complete and NP-Hard problem. |1 |

| |Differentiate decision problem and optimization problem |2 |

| |List out the problems which can solve in polynomial time. |2 |

| |List out the problems which cannot solve in polynomial time. |2 |

| |Is P= NP? Explain with reason. |3 |

| |Show that the class P, viewed as a set of languages, is closed under union, intersection, concatenation, complement,|5 |

| |and Kleen star. | |

| |Consider two problems A and B. If A ≤PT B and if B can be solved in polynomial time, then A can also be solved in |5 |

| |polynomial time. | |

-----------------------

H

B

C

G

E

D

F

A

14

10

3

6

4

5

2

9

15

8

................
................

In order to avoid copyright disputes, this page is only a partial summary.

Google Online Preview   Download