CS702 PREVIOUS MID TERM PAPER

CS702 MID TERM PAPER Part 1

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 MID TERM PAPER Part 2

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.n³ + 3.n + 10 ∈ O (n⁴)

There was a question based on this question format

Problem No. 3

Suppose sequence, b₀, b₁, b₂, . . ., satisfies recurrence relation

b_k= 6b_k-1-9b_k-2  ∀k≥2

With condition initial condition: b₀=2 and b₁=6

Then find explicit formula for b₀, b₁, b₂, . . ., 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. 

CS702 MID TERM PAPER Part 3

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.

CS702 MID TERM PAPER Part 4

Questions that i remember are:

1. Prove that f(n) = O(g(n)) g(n) = (f(n))         (5 Marks)

2. Prove that 2.n³ + 3.n + 10 ∈O (n⁴)               (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 A₁.A₂.A₃ 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 MID TERM PAPER Part 5

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.n³ + 3.n + 10 ∈ O(n⁴)

There was a question based on this question format

Problem No. 3

Suppose sequence, b₀, b₁, b₂, . . ., satisfies recurrence relation

b_k= 6b_k-1-9b_k-2  ∀k≥2

With condition initial condition: b₀=2 and b₁=6

Then find explicit formula for b₀, b₁, b₂, . . ., 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. 

CS702 MID TERM PAPER Part 6

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.               Inline assembly 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.

CS702 MID TERM PAPER Part 7

1: write algo of 0-1 knapsack problem by brute force.
2: write algo knapsack problem by dynamic programming.
3: algorithm of 2-dimension points.
4: write algorithm 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