NOVEMBER 2021 PSB3H
Time
: Three
hours Maximum :
75 marks
PART A — (10
× 1
= 10
marks) Answer any TEN questions.
1. What is performance measurement?
2. What is meant by algorithm?
3. Define
divide and conquer method.
4. Write any two characteristics of Greedy
Algorithm.
5. What
are the drawbacks of dynamic
programming?
6. Write
the general procedure of dynamic
programming.
7. What are the factors that influence the efficiency of the backtracking algorithm?
8. Stale 8-Queens problem.
9. What
are connected
components?
10. Write
a note
on Big-"oh"
notation.
11. What
is lower
bound through
reduction?
12. What
is comparison
tree?
PART B — (5 × 5 = 25 marks)
Answer any FIVE questions.
13. What is a randomized algorithm? Explain briefly about two categories of
randomized algorithm?
14. Write
the general plan for analyzing time
efficiency of recursive algorithms.
15. What is the aim of Greedy
method? Give an example.
16. Write
an algorithm for the knapsack problem
using greedy method.
17. Explain the
multistage graphs giving an example.
18. Describe the Hamiltonian cycle’s problem in
an undirected Graph.
19. Summarize
the Oracles
and advisory
arguments.
PART C — (4 × 10 = 40 marks) Answer any FOUR questions.
20. Define
time complexity and space complexity.
Write an algorithm for adding "n" natural
numbers.
21. Compare
ordinary matrix multiplication and
Strassen's matrix
multiplication.
22. Illustrate
the Job sequencing with deadlines
through an example.
23. Explain
about the traveling salesman problem
using dynamic programming.
24. Discuss
the 8-Queen problem using backtracking
method.
25. Explain NP-hard and NP-complete problems with example.
No comments:
Post a Comment