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
2076
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
What do you mean by the complexity of an algorithm? Explain the asymptotic notations used to describe the time/space complexity of any algorithm with their geometrical interpretation and example.
Explain the divide and conquer paradigm from algorithm design with a suitable example. Write the Quick sort algorithm using a randomized approach and explain its time complexity.
Explain in brief the Backtracking approach for algorithm design. How it differs with recursion? Explain the N-Queen problem and algorithm using backtracking and analyze its time complexity.
Section B
Attempt any EIGHT questions
Write the algorithm for selection sort and explain its time and space complexity.
Solve the following recurrence relation using the master method.
Explain the greedy algorithm for the fractional knapsack problem with its time complexity.
Trace heap sort algorithm for the following data:
{2, 9, 3, 12, 15, 8, 11}
What do you mean by Dynamic programming strategy? Explain the element of DP.
Explain the approximation for solving vertex cover with a suitable example.
Explain Prism’s algorithm for MST problem and analyze its time complexity.
Explain in brief about the classes P, NP, and NP complete with examples.
Write short notes on