Tribhuvan University
Bachelor of Science in Computer Science and Information Technology
Semester 5 · TU Board 2078
Course Title: Design and Analysis of Algorithms (CSC314)
Full Marks: 60Pass Marks: 24Time: 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.
Group A
Attempt Two Question.(2 × 10 = 20)
- 1.10
What are the elementary properties of algorithm? Explain. Why do you need algorithm? Discuss about analysis of the RAM model for analysis of algorithm with suitable example.
- 2.10
Explain about the divide and conquer paradigm for algorithm design with suitable example. Write the Quick sort algorithm using randomized approach and explain its time complexity.
Answer comingAlso asked in 2076
- 3.10
Explain in brief about the Dynamic Programming Approach for algorithm design. How it differs with recursion? Explain the algorithm for solving the 0/1 Knapsack problem using the dynamic programming approach and explain its complexity.
Group B
Attempt Eight Questions.(8 × 5 = 40)
- 4.5
Explain the recursion tree method for solving the recurrence relation. Solve following recurrence relation using this method.
T(n)=2T(n/2) +1 for n> 1, T(n) =1 for n =1Answer comingAlso asked in 2082, 2081, 2079, 2076
- 5.5
Write an algorithm to find the maximum element of an array and analyze its time complexity.
- 6.5
Write the algorithm for bubble sort and explain its time complexity.
Answer comingAlso asked in 2080, 2076, Model question
- 7.5
What do you mean by optimization problem? Explain the greedy strategy for algorithm design to
solve optimization problems. - 8.5
Explain the algorithm and its complexity for solving job sequencing with deadline problem using greedy strategy.
- 9.5
What do you mean by memorization strategy? Compare memorization with dynamic programing.
- 10.5
Explain the concept of backtracking. How it differ with recursion?
- 11.5
Explain in brief about the complexity classes P, NP and NP Complete.
Answer comingAlso asked in 2076, Model question
- 12.5
Write short notes on:
a. NP Hard Problems and NP Completeness
b. Problem Reduction
— The End —