JISCE / PG / MCSE / R18 / EVEN / SEM-2 / PGCS201 / 2022-2023
ADVANCED ALGORITHMS
PGCS201
TIME ALLOTTED: 3 HOURS FULL MARKS: 70
The figures in the margin indicate full marks.
Candidates are required to give their answers in their own words as far as practicable(each question will carry 14 marks)
Marks CO No.
1. (a) Write the differences between greedy method and Dynamic 3 4
programming?
(b) What is state space tree? 3 3
(c) Find an optimal parenthesizing of a matrix chain product 8 4
whose sequence of dimensions are {10, 20, 4, 5} and find the
number of multiplications.
2. (a) What is lower bound theory? 3 3
(b) Which one is better between Binary Search and Linear 3 2
Search, and why?
(c) Find out the maximum profit. 8 4
Jobs J1 J2 J3 J4 J5
Profits
24 15 13 5 1
Deadlines 2 2 1 3 3
3. (a) Apply Heap sort to sort the following unsorted Array: 5 4
{20, 5, 16, 19, 7, 13, 3, 8, 9, 10, 30}
(b) Given a string 'T' and pattern 'P' as follows: 6 4
Apply KMP algorithm for to find whether 'P' occurs in 'T.'
(c) Find out the time complexity of the following algorithm: 3 1
A ()
{
Int count=1, sum=1, number;
While(sum<=number)
{
count++;
sum+=count;
Print(sum);
}
}
Page 1 of 2
JISCE / PG / MCSE / R18 / EVEN / SEM-2 / PGCS201 / 2022-2023
4. (a) “Travelling salesman problem is the problem of NP- 3 3
complete”- Justify the statement.
(b) Write the pseudo code for Naïve String-matching algorithm. 5 2
(c) Apply any one graph traversal algorithm on the above graph. 6 4
B F
C
A
H
D
E
G
5. (a) What is the necessity of Stressen’s matrix multiplication? 3 2
(b) Find out the length of longest common subsequence for 4 1
strings A = “AB”, B = “APBQABX”.
(c) Let the number of items be n = 5, wi = {5,7,2,3,4}, 7 2
vi= {60,14,16,90,50}, i = 1, 2….5, M=15. Calculate
maximum profits using fractional knapsack method. (w and v
are weight and profit vectors respectively.)
6. (a) Explain 4-queen problem using suitable example. 5 4
(b) Derive the worst-case complexity of Dijkstra’s Algorithm. 6 1
(c) Explain how the process of finding out the time complexity of 3 2
an iterative algorithm differs from that of finding out the time
complexity of a recursive algorithm.
7. (a) Solve the following recurrences: 5
(i) T (n) = 8T (n/2) + n2
(ii) T (n) = 2T (n/2) + n
(b) 10 7 3
2
V
6 1 V 0
3
4 t
S 1 7
0
9
9 V V
2 4 4
14
Find out Maximum flow through the above network.
(c) “Merge sort is an example of Divide & Conquer Approach”- 2 4
Justify the statement.
Page 2 of 2
