CSIT 5th Semester
Design and Analysis of Algorithms Board Question Paper 2081 Old Course

Views: ...
CSC 325-2081 ✡
Tribhuvan University
Institute of Science and Technology
2081
✡
Bachelor Level/Third Year/Fifth Semester/Science
Computer Science Information Technology (CSC 325)
(Design and Analysis of Algorithms)
(Old Course)
Full Marks:60 Pass Marks:24 Time:3 hours

Candidates are required to give their answers in their own words as for as practicable.
The figures in the margin indicate full marks

Section A
Long Answer Questions
Attempt any Two question.
[2x10=20]
1.

Why do you need analysis of algorithms? Explain RAM model for the analysis of algorithm with example.

2.

What is recurrence relation? Solve the following recurrence relations using Master method.
a) T(n) = 4T(n/2) + n
b) T(n) = 3T(n/4) + n log n

3.

What is the worst-case of quick sort? Show how quick sort can be made to run in O(n log n) time in the worst case assuming all elements are distinct.

Section B

Attempt any Eight questions

[8x5=40]
4.

Trace the heap-sort algorithm for the following data {4, 6, 17, 10, 12, 9, 8}.

5.

You have given 5 jobs with profit pᵢ and deadline dᵢ as

i12345
Pᵢ201010205
dᵢ21232

Find the optimal job lists that can be executed in a sequence within their deadline so as to maximize the profit.

6.

Write algorithm to compute the LCS of given two sequences. Trace the running of the algorithm to find the LCS of the sequences {abbaba} and {aaaba}.

7.

Write the Dijkstra's algorithm for single source shortest path in a graph. Find the shortest path from the node s to other nodes.
graph for dijkstra algorithm

8.

How can you determine the intersection of the two line segment efficiently? Explain with suitable examples.

9.

How can you find the shortest path from a vertex of directed acyclic graph? Explain with example.

10.

Define convex hull in 2D. Show that lower bound for computing the convex hull in 2D is Ω(n log n).

11.

No question

12.

No question