## 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)

**Download Question Paper File**

[File Type: PDF | File Size: 450 KB | Download]

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**

- Explain the term Big-oh, Big-omega and Big-theta. Show that a function f=3n
^{2}+4n+7 is big theta of n^{2}. (8) - What do you mean by a recurrence relation? Solve the following recurrence relation using iterative expansion method (2+6)

- 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)
- How can you solve the selection problem in linear time? Write the algorithm and analyze for its time complexity. (8)
- 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)
- Explain Prim’s algorithm for computing the MST of a given graph and analyze it. Also verify the correctness of this algorithm. (5+3)
- 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)
- Define convex hull in 2D. Explain the gram’s scan algorithm for computing convex hull and analyze it. (2+6)
- Explain about the complexity classes P, NP and NP complete with suitable examples. (8)
- Explain Dijkstra’s algorithm for computing the single source shortest path in a graph with suitable example. (8)

(Visited 164 times, 1 visits today)