CSIT 5th Semester
Design and Analysis of Algorithms Board Question Paper 2079

CSC 325-2079 ✡
Tribhuvan University
Institute of Science and Technology
2079
✡
Bachelor Level/Third Year/Fifth Semester/Science
Computer Science Information Technology (CSC 325)
(Design and Analysis of Algorithms)
(New 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.

Explain the divide and conquer strategy for problem solving. Describe the worst-case linear time selection algorithm and analyze its complexity.

2.

Write the dynamic programming algorithm for matrix chain multiplication. Find the optimal parenthesization for the matrix chain product ABCD with size of each is given as A₅ₓ₁₀, B₁₀ₓ₁₅, C₁₅ₓ₁₀, D₁₀ₓ₁₅.

3.

What do you mean by Backtracking? Explain the backtracking algorithm for solving 0-1 knapsack problem and find the solution for the problem given below:

Items →1234
Weight (wᵢ) →6235
Profit (Pᵢ) →45107

and capacity of knapsack: 10 kg

Section B

Attempt any Eight questions

[8x5=40]
4.

Explain the iterative algorithm to find the GCD of given two numbers and analyze its complexity.

5.

Trace the quick sort algorithm for array A[ ] = {15, 7, 6, 23, 18, 34, 25} and write it's best and worst complexity.

6.

Generate the prefix code for "CYBER CRIME" using Huffman algorithm and find the total number of bits required.

7.

Solve the following recurrence relations using masters method
a) T(n) = 2T(n/2) + kn², n > 1
= 1, n = 1.
b) T(n) = 5T(n/4) + kn, n > 1
= 1, n = 1.

8.

Find the edit distance between the string "ARTIFICIAL" and "NATURAL" using dynamic programming.

9.

Find the MST from following graph using Kruskal's algorithm.
graph for kruskal algorithm

10.

Solve the following linear congruences using Chinese Remainder Theorem.
x ≡ 1 (MOD 2)
x ≡ 3 (MOD 5)
x ≡ 6 (MOD 7)

11.

Define tractable and intractable problem. Illustrate vertex cover problem with an example.

12.

Write short notes on:
a) Best, Worst and average case complexity
b) Greedy Strategy