cs702mid term paper (75 marks paper)
Total 8 Questions
2 questions of 5 marks
1 question of 15 marks
5 questions of 10 marks
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
1 1 1
2 2 6
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
- 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. - A Fibonacci sequence was given and question was to write formula for it.
- 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.