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

CSC 325-2082 ✡
Tribhuvan University
Institute of Science and Technology
2082
✡
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 we need backtracking? Discuss with an example. Write and find the time and space complexity of binary search algorithm.

2.

Write Euclidean algorithm to find the GCD of two given integers. Explain the elements of Greedy strategy.

3.

Define tractable and intractable problems with examples. Find the edit distance between the string "CARPET" and "MARKET" using dynamic programming.

Section B

Attempt any Eight questions

[8x5=40]
4.

Given the dataset {10, 20, 30, 40}, use the backtracking approach to find the subset of elements that equals to the sum 40.

5.

Write the algorithm for Miller - Rabin primality test.

6.

Justify the concept of CNF-SAT with an example.

7.

Solve the recurrence relation T(n) = T(n/2) + 1, T(1) = 1, using iteration method.

8.

Write and discuss the time and space complexity of insertion sort.

9.

Describe in brief about aggregate analysis. Write and discuss about best and worst case for sequential search.

10.

Find max and min element in {5, 7, 3, 4, 9, 12, 6, 2} using divide and conquer approach.

11.

Write dynamic programming approach to solve Floyd Warshall algorithm.

12.

Define recursion. How does Kruskal's algorithm follow greedy approach to find minimum spanning tree? Illustrate with an example.