BSc CSIT (TU) Science Design and Analysis of Algorithms (BSc CSIT, CSC314) Question Paper 2074
This is the official BSc CSIT (TU) (Science stream) Design and Analysis of Algorithms (BSc CSIT, CSC314) question paper for 2074, 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 2074 paper is a great way to practise under real exam conditions.
Section A: Long Answer Questions
Attempt any TWO questions.
Explain the divide and conquer strategy of algorithm design. Write the merge sort algorithm, trace it on the array [38, 27, 43, 3, 9, 82, 10] and analyze its time complexity using the recurrence relation.
What is dynamic programming? Explain Floyd-Warshall algorithm to compute all-pairs shortest paths in a weighted graph with a suitable example and analyze its time complexity.
Explain the greedy method of algorithm design. Generate the prefix code for the string "CYBER CRIME" using Huffman algorithm and find the total number of bits required to encode it.
Section B: Short Answer Questions
Attempt any EIGHT questions.
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.
Explain the matrix chain multiplication problem and write its dynamic programming formulation.
Explain heap sort algorithm with an example and analyze its time complexity.
Explain how the subset-sum problem is solved using backtracking with an example.
What are approximation algorithms? Explain the approximation algorithm for the vertex cover problem.