Questions that i remember are:
1. Prove that f(n) = O(g(n)) g(n) = (f(n)) (5 Marks)
2.Prove that 2.n3 + 3.n + 10 ∈O(n4) (5 Marks)
3. Consider the recurrence
tn = n if n = 0, 1, 2
tn=6tn-1 - 11tn-2 + 6tn-3
Find the general solution of the recurrence above.
4. To write algorithm for n-line assembly using dynamic algorithm
5. To write algorithm for complete knapsack using dynamic algorithm
6. Let N be a set of natural numbers. The symbols, < (less than), ≤ (less than or equal) and =
(equal) are relations over N. Prove or disprove the following.
a. < is reflexive, symmetric and transitive
b. ≤ is reflexive, symmetric and transitive
c. = is reflexive, symmetric and transitive
7. Compute optimal multiplication order for matrices A1.A2.A3 with order 10x100, 100x5 and
5x50.
8. Given a sequence [A1, A2, A3, A4]
• Order of A1 = 10 x 100
• Order of A2 = 100 x 5
• Order of A3 = 5x 50
• Order of A4 = 50x 20
Compute the order of the product A1 . A2 .A3 . A4 in such a way that minimizes the total
number of
scalar multiplications. (15 mark)
Cs702: Paper
No objective questions
ProblemNo.1
Use Dynamic Programming to find an optimal solution for the 0-1 Knapsack problem.
item weight value knapsack capacity W = 11
111
226
3 5 18
4 6 22
5 7 28
And write algorithm for it.
There was a question based on this question format
Problem No. 2
Prove that 2.n3 + 3.n + 10 ∈ O(n4)
There was a question based on this question format
Problem No. 3
Suppose sequence, b0, b1, b2, . . ., satisfies recurrence relation
bk= 6bk-1-9bk-2 ∀k≥2
with condition initial condition: b0=2 and b1=6
Then find explicit formula for b0, b1, b2, . . ., using characteristic equation of the above recursion.
There was a question based on this question format
Problem No. 4
Show that any amount in cents ≥ 20 cents can be obtained using 5 cents and 6 cents coins only.
There was a question based on this question format
Question 5 (10 Marks)
Use mathematical induction to prove sigma i=0 to n (i] = n(n+1)(2n+1)/6 .
Question 6:
There was some program of 2 line assembly whose algo was given, we were to take out
mistakes from that algo and write the correct algo.
Question 7:
A question was there where a fibonacci sequence was given and we were to write formula for
it.
Other paper cs 702
1. Sigma i=0 to n (i] = n(n+1)(2n+1)/6 . Prove by mathematical induction
3 cents and 7 cents coins , make a general formula for it.
2. A Fibonacci sequence was given and question was to write formula for it.
3. nline assebly algo was given to find errors in it.
To find an algo for n-line assembly where the transfer time from one line to the other was
different.
another paper
cs702 paper
1:write algo of 0-1 knapsack problem by brute force.
2:write algo knapsack problem by dynammic programming.
3:algorithm of 2-dimension points.
4:write algoritm 2-line assembly language.
5:algorithm n-line assembly language
6:N be a set of natural number < or = over relation prove or
disprove ,symmetric ,transitive ,reflexive
