Design and Analysis of Algorithms
This course introduces basic elements of the design and analysis of computer algorithms. Topics include asymptotic notations and analysis, divide and conquer strategy, greedy methods, dynamic programming, basic graph algorithms, NP-completeness, and approximation algorithms. For each topic, beside in-depth coverage, one or more representative problems and their algorithms shall be discussed.
Tribhuvan University
Institute of Science and Technology
2078
Bachelor Level / fifth-semester / Science
Computer Science and Information Technology( CSC314 )
Design and Analysis of Algorithms
Full Marks: 60 + 20 + 20
Pass Marks: 24 + 8 + 8
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
Attempt Two Question.
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.
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.
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.
Section B
Attempt Eight Questions.
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 =1
Write an algorithm to find the maximum element of an array and analyze its time complexity.
Write the algorithm for bubble sort and explain its time complexity.
What do you mean by optimization problem? Explain the greedy strategy for algorithm design to
solve optimization problems.
Explain the algorithm and its complexity for solving job sequencing with deadline problem using greedy strategy.
What do you mean by memorization strategy? Compare memorization with dynamic programing.
Explain the concept of backtracking. How it differ with recursion?
Explain in brief about the complexity classes P, NP and NP Complete.
Write short notes on:
a. NP Hard Problems and NP Completeness
b. Problem Reduction