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
2082
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 any TWO questions.
How do you define optimal solution? Does greedy algorithm always guarantee optimal solution? Given the string “SUPER DUPER CSIT”, use a Greedy algorithm to build a Huffman tree.
What is order statistics? Write and analyze the algorithm for randomized quick sort.
Distinguish between dynamic programming and memorization. Parenthesize the matrices A(30 × 1), B(1 × 40), C(40 × 10) and A(10 × 15), for computing matrix multiplication using dynamic programming.
Section B
Attempt any EIGHT questions.
Solve the recurrence relation T(n) = 2T(n/2) + n using recursion tree method.
Find the best and worst case for Bubble sort.
Using Extended Euclidean Algorithm, find the GCD of 12 and 16.
Find all possible subsets of the integers that sum to 21 in the array {5, 6, 10, 11, 15} using back tracking technique.
Define class P and NP problem. Why do we need approximation algorithms? Justify.
State the time and space complexity for sequential search. Write the rules for master theorem for finding asymptotic bounds.
Justify the worst case for binary search. Find the edit distance from the string “RELEVANT” to “ELEPHANT” using dynamic programming approach.
Distinguish between recursion and backtracking. Using Miller-Rabin primality test, check whether 53 is prime or not?
How does 0/1 Knapsack problem differ from fractional one? Find the minimum vertex cover in the following graph.
