Design and Analysis of Algorithm (daa)| BSc.CSIT (TU) Question Paper 2070 | Fifth Semester

Fifth Semester | Third Year | Tribhuvan University Old Question Collection | Question Bank Design and Analysis of Algorithm(daa), Year: 2070 Computer Science and Information Technology (CSc. 303)

Candidates are required to give their answer in their own words as far as practicable.
The figures in the margin indicate full marks.
Attempt all the questions

1. Explain the term Big-oh, Big-omega and Big-theta. Show that a function f=3n2+4n+7 is big theta of n2. (8)
2. What do you mean by a recurrence relation? Solve the following recurrence relation using iterative expansion method (2+6)
3. write an algorithm for quick-sort and trace out the algorithm for the following array A[ ] = { 16,7,15,14,18,25,55,32 }. (4+4)
4. How can you solve the selection problem in linear time? Write the algorithm and analyze for its time complexity. (8)
5. What is prefix code? You have given a message text having seven distinct characters {p,q,r,s,t,u,v} with frequency {40,20,15,12,8,3,2}. Trace the Huffman algorithm to build the free and obtain the optimum prefix codes for each characters. (2+6)
6. Explain Prim’s algorithm for computing the MST of a given graph and analyze it. Also verify the correctness of this algorithm. (5+3)
7. Distinguish the main idea for divide and conquer approach with dynamic programming approach. Find the longest common subsequence between two sequences <A,B,C,B,D,A,B> and <B,D,C,A,B,A>. (2+6)
8. Define convex hull in 2D. Explain the gram’s scan algorithm for computing convex hull and analyze it. (2+6)
9. Explain about the complexity classes P, NP and NP complete with suitable examples. (8)
10. Explain Dijkstra’s algorithm for computing the single source shortest path in a graph with suitable example. (8)

Posted By : | Comment RSS | Category : Fifth Semester, Old Question Collection
Tag :
Subscribe Notes