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

Views: ...
CSC 325-2082 ✡

Tribhuvan University

Institute of Science and Technology

TUpapers.com TUpapers.com
Bachelor Level/Third Year/Fifth Semester/Science
Bachelors in Computer Science and Information Technology (CSC 325)
(Design and Analysis of Algorithms) <br> <b class='underline'>(Old Course</b>)
Full Marks: 60 Pass Marks: 24 Time: 3 hours

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

Section A
Long Answer Questions
Attempt any Two questions.
[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

[8×5=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.