BSc CSIT (TU) Science Design and Analysis of Algorithms (BSc CSIT, CSC314) Question Paper 2080
This is the official BSc CSIT (TU) (Science stream) Design and Analysis of Algorithms (BSc CSIT, CSC314) question paper for 2080, as set in the regular annual examination. It carries 60 full marks and a time allowance of 180 minutes, across 12 questions. On Kekkei you can attempt this Design and Analysis of Algorithms (BSc CSIT, CSC314) past paper online with a timer, get instant AI feedback and step-by-step solutions, and track the topics where you lose marks — completely free. Whether you are revising for your BSc CSIT (TU) Design and Analysis of Algorithms (BSc CSIT, CSC314) exam or solving previous years' question papers, this 2080 paper is a great way to practise under real exam conditions.
Section A: Long Answer Questions
Attempt any TWO questions.
Define asymptotic notations (Big-O, Big-Omega, Big-Theta). State the master theorem and use it to solve the recurrences T(n)=3T(n/2)+n and T(n)=2T(n/4)+sqrt(n).
Explain the complexity classes P, NP, NP-Hard and NP-Complete with examples. Discuss how a problem is proved to be NP-Complete using polynomial-time reduction.
Write a dynamic programming algorithm for the 0/1 knapsack problem and solve it for items with weights {2, 3, 4, 5} and values {3, 4, 5, 6} with knapsack capacity W = 5.
Section B: Short Answer Questions
Attempt any EIGHT questions.
Differentiate between Breadth First Search (BFS) and Depth First Search (DFS) with examples and their time complexities.
Solve the recurrence relation T(n) = 2T(n/2) + n using the substitution method and the recursion tree method.
Explain the job sequencing with deadlines problem and solve it using the greedy approach for a given set of jobs.
Explain the naive string matching algorithm and the Rabin-Karp algorithm with their time complexities.
Write an algorithm for binary search using divide and conquer. Analyze its best-case, worst-case and average-case time complexity.
Explain the randomized quicksort algorithm and analyze its expected time complexity.
Write a greedy algorithm for the fractional knapsack problem and analyze its time complexity.
Find the edit distance between the strings "ARTIFICIAL" and "NATURAL" using dynamic programming.
Write Dijkstra's algorithm to find single-source shortest paths and explain it with an example.