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
2079
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.
Group A
Attempt any TWO questions.
Explain the divide and conquer strategy for problem solving. Describe the worst-case linear time selection algorithm and analyze its complexity.
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 A5×10 , B10×15 , C15×20 , D20×30
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:
Group B
Attempt any EIGHT questions
Explain the iterative algorithm to find the GCD of given two numbers and analyze its complexity.
Generate the prefix code for the string ” CYBER CRIME” using Huffman algorithm and find the total number of bits required.
Define tractable and intractable problem. Illustrate vertex cover problem with an example.
Find the edit distance between the string ” ARTIFICIAL” and “NATURAL” Using dynamic programming.
Write short notes on:
a) Best, Worst and average case complexity
b) Greedy Strategy
Solve the following recurrence relations using masters method
a. T(n) = 2T(n/4) + kn2, n > 1
=1 , n=1
b. T(n) = 5T(n/4) + kn , n > 1
=1 , n=1
Solve the following linear congrvences using Chinese Remainder Theorem.
X=l (MOD 2)
X=3 (MOD 5)
x=6 (MOD 7)
Find the MST from following graph using Kruskal’s algorithm.
Trace the quick sort algorithm for sorting the array A[ ]={15,7,6,23, 18,34,25} and write it’s best and worst complexity.