CSC314 Design and Analysis of Algorithms
Design and Analysis of Algorithms: most repeated questions
Questions that have come up in more than one paper, matched by what they ask rather than exact wording. Most repeated first.
- 5×Asked in 2080, 2078, 2076, Model questionDiscuss heapify operation with example. Write down its algorithm and analyze its time and space complexity.Answer coming10
See the wording in each paper
- Discuss heapify operation with example. Write down its algorithm and analyze its time and space complexity.TU Board 2080
- Write down algorithm of insertion sort and analyze its time and space complexity.TU Board 2080
- Write the algorithm for bubble sort and explain its time complexity.TU Board 2078
- Write the algorithm for selection sort and explain its time and space complexity.TU Board 2076
- Write down algorithm of insertion sort and analyze its time and space complexity.Model question
- 5×Asked in 2082, 2081, 2079, 2078, 2076Solve the recurrence relation T(n) = 2T(n/2) + n using recursion tree method.Answer coming5
See the wording in each paper
- Solve the recurrence relation T(n) = 2T(n/2) + n using recursion tree method.TU Board 2082
- Solve the following recurrence relations using master's method. (a) T(n) = 2T ( n2 ) + n^3, n 1 T(n) = 1, n = 1 (b) T(n) = 2T ( n4 ) + 1, n 1 T(n) = 1, n = 1TU Board 2081
- Solve the following recurrence relations using masters method a) T(n) = 2T(n/4) + kn^2, n 1 =1 , n=1 b) T(n) = 5T(n/4) + kn , n 1 =1 , n=1TU Board 2079
- Explain the recursion tree method for solving the recurrence relation. Solve following recurrence relation using this method. T(n)=2T(n/2) +1 for n 1, T(n) =1 for n =1TU Board 2078
- Solve the following recurrence relation using the master method. 1. T(n) = 7 T(n/2) + n^2 1. T(n) = 4 T(n/4) + knTU Board 2076
- 3×Asked in 2078, 2076, Model questionExplain in brief about the complexity classes P, NP and NP Complete.Answer coming5
See the wording in each paper
- 2×Asked in 2079, Model questionFind the MST from following graph using Kruskal's algorithm. [figure in the original paper]Answer coming5
See the wording in each paper
- 2×Asked in 2078, 2076Explain about the divide and conquer paradigm for algorithm design with suitable example. Write the Quick sort algorithm using randomized approach and explain its time complexity.Answer coming10
See the wording in each paper
- Explain about the divide and conquer paradigm for algorithm design with suitable example. Write the Quick sort algorithm using randomized approach and explain its time complexity.TU Board 2078
- 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.TU Board 2076
- 2×Asked in 2076, Model questionWhat 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.Answer coming10
See the wording in each paper
- 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.TU Board 2076
- Explain the asymptotic notations used to describe the time/space complexity of any algorithm.Model question
- 2×Asked in 2079, Model questionWrite 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 A 5×10 , B 10×15 , C 15×20 , D 20×30Answer coming10
See the wording in each paper
- 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 A 5×10 , B 10×15 , C 15×20…TU Board 2079
- Find the optimal parenthesization for the matrix chain product ABCD with size of each is given as A 5×10 , B 10×15 , C 15×20 , D 20×30Model question
- 2×Asked in 2081, Model questionGiven a set A=(5,7,10,12,15,18,20, find the subset that sum to 35 using backtracking.Answer coming5
See the wording in each paper
- 2×Asked in 2081, 2079Solve the following linear equation using Chinese Remainder Theorem. x = 1 MOD 3 x = 2 MOD 5 x = 0 MOD 7Answer coming5
See the wording in each paper
- 2×Asked in 2076, Model questionTrace heap sort algorithm for the following data: 2, 9, 3, 12, 15, 8, 11Answer coming5
See the wording in each paper
- 2×Asked in 2079, Model questionWrite short notes on: a) Best, Worst and average case complexity b) Greedy StrategyAnswer coming5
See the wording in each paper