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.
To fulfill the demand for quickly locating and searching documents.
It is intelligent file search solution for home and business.
Related searches
- wordpress passing data between pages
- wordpress business templates
- wordpress rss feed not working
- wordpress jquery is not defined
- create wordpress blog
- wordpress roles editor
- wordpress full rss feed
- wordpress rss feed settings
- wordpress rss feed plugin
- wordpress display rss feed
- wordpress rss feed link
- wordpress rss feed to post