Model question for Design and analysis of algorithm

Tribhuvan University

Bachelor of Science in Computer Science

And Information Technology

Model Question

FM.= 80

PM = 32                                                                                  Time = 3 hr

Design and analysis of algorithm

1. Can we apply master method to find the big-O estimate of the recurrence T(n)=4T(n/2) + n²logn? Why or why not? Find the big-O estimate for this recurrence by using recursion tree.        
2. Given the following block of code, write a recurrence relation for it with reason and also find asymptotic upper bound (Assume that all dotted code takes linear time)

Fun(int n)

{

            …………….

if(condition1)

x=Fun(n/2)

else if(condition2)

x=Fun(2n/3)

else

x= Fun(n/4)

……………

}

3. What do you mean by order statistics? How can you devise an algorithm that guarantee the selection of i^th order statistics in linear time? Write the algorithms of it and also analyze it.
4. In what situations the dynamic programming algorithms are useful? What are the application areas of Longest Common Subsequence? Write the recursive definition for finding LCS and find the LCS of the strings "Monkey" and "Money"
5. What is the advantage and disadvantage of greedy algorithms over dynamic programming algorithms? Under what circumstances greedy algorithm gives us optimal solution? Devise the greedy algorithm that makes the change of n rupees (n<55000 and n is multiple of 10) with minimum number of notes (consider 100 notes of 10 rupees, 80 notes of 20 rupees, 60 notes of 50 rupees, 50 notes of 100 rupees, 40 notes of 500 rupees and 30 notes of 1000 rupees)  {2 +1+ 3}
6. In which case adjacency matrix representation of graph is better? Explore DFS with example and give it's asymptotic and aggregate analysis.
7. What is the main concept behind randomized algorithms? Write algorithm for randomized quick sort and analyze it.
8. What is NP completeness? What approaches are used in proving NP-completeness of the problems? "Proving a problem as NP-complete is considered as good contribution in computer science" why? Justify with strong argument.
9. What is left turn and right turn? Give an algorithm for finding whether two line segments intersects or not by using left and right turn. Justify with example that algorithm works for all cases.
10. Suppose that our machine does not supports direct multiplication operation. Multiplication must be done by repeated addition. Devise Iterative and recursive algorithm for it and analyze them.