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

Download our Android App from Google Play Store and start reading Reference Notes Offline.

daa question paper 2070Fifth 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

  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)
    2 no. question
  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 : Digvijay | Comment RSS | Category : Fifth Semester, Old Question Collection
Tag :

Post a Comment

Your email is never published nor shared. Required fields are marked *

*
*

Wordpress DMCA
Community | Toolbar | Android App | Founder/Developer : Hari Prasad Chaudhary | CSIT Portal Manager : Digvijay Chaudhary