CS702 Paper
q1.
using given probabilities for q and p
find OBST (optimal binary search tree)
make tables for w[i,j], e[i,j], root[i,j]
q2.
a. fractionnal knapsack problem find the optimal solution for given data.
b. find optimal solution using greedy approach for 01-knapsack for the given problem, wheather it is optimal or not.
q3.
Question No. 3 was about timestamping in DFS.
q4.
write an algorithm for the given
weighted directed graph, find an optimal cost using S as source vertex, cost fo each vertex reachable from S
should be less than or equal to 9, it should output vertices like
A,B, C, D and cost as 3, 4, 8, 7
q5.
use floyed warshal algo to find shortest past in the given graph.
q6.
a. if gcd(a,m)=1 , m > 1, there is a unique inverse for a that is a' modolu m .
b. for all primes p, for all integers a, b, if p|ab, then either p|a or p|b or p| both a and b.
q7.
a. using rabin-karp algorithm, if the text T=812349039987 (somethin like that) and p=39, how many spurious hits will be encountered.
b. prove that 3-SAT is in NP
Download: Click Here