## Subjective Questions

*Question*

(Mid Term, Marks = 10, Lesson No. )
algorithm of shortest distance between n points

*Answer:*

*Question*

(Mid Term, Marks = 10, Lesson No. )
Prove tautology by logical equivalence.

*Answer:*

*Question*

(Mid Term, Marks = 10, Lesson No. )
assembly line problem 6 stations

*Answer:*

*Question*

( Term, Marks = , Lesson No. )
write down the brute force chain matrix multiplication algorithm and complexity.

*Answer:*

*Question*

( Term, Marks = , Lesson No. )
write pseudo code algorithm of merge sort.

*Answer:*

*Question*

(Final Term, Marks = 5, Lesson No. 24)
Explain situation and example in which greedy algorithm does not work.

*Answer:*

*Question*

(Final Term, Marks = 10, Lesson No. 28)
Write BFS (Breadth First Search) pseudo code algorithm.

*Answer:*

*Question*

(Final Term, Marks = 10, Lesson No. 23)
Write pseudo code of LCS (Longest Common Subsequence) problem.

*Answer:*

*Question*

(Final Term, Marks = 10, Lesson No. 41)
Prove that if p is prime, a is positive integer not divisible by p,

a^{p-1} = 1 mod p OR a^{p} = a mod p

*Answer:*

*Question*

(Final Term, Marks = 10, Lesson No. 39)
If a and b are integers, not both zero then gcd(a,b) is the smallest positive element of the set {ax + by : x, y ε Z} of linear combination of a nad b.

*Answer:*

*Question*

(Final Term, Marks = 5, Lesson No. 36)
Write pseudo code of EXTEND-SHORTEST-PATH.

*Answer:*

*Question*

(Final Term, Marks = 5, Lesson No. 41)
Decrypt 0981 0461 if encrypted using RSA

public key = (e, n) = (13, 43.59 = 2537)

*Answer:*

*Question*

(Final Term, Marks = 5, Lesson No. 29)
Write pseudo code of DFS-Visit.

*Answer:*

*Question*

(Final Term, Marks = 10, Lesson No. 24)
Write pseudo code of optimal binary search tree.

*Answer:*

*Question*

(Final Term, Marks = 5, Lesson No. 26)
Write pseudo code of Huffman algorithm.

*Answer:*

*Question*

(Final Term, Marks = 5, Lesson No. 38)
Prove that if a|b, a|c then a|(b + c) ∀ a, b, c ε Z

*Answer:*

*Question*

(Final Term, Marks = 5, Lesson No. 40)
Prove taht if gcd(a, m) = 1 and m > 1, then a has a unique inverse a' (modulo m).

*Answer:*

*Question*

(Final Term, Marks = 5, Lesson No. 39)
Prove that x and y are relatively prime iff gcd(x, y) = 1

*Answer:*

*Question*

(Mid Term, Marks = 5, Lesson No. 19)
Write the pseudo code of 0-1 knapsack brute force algorithm.

*Answer:*

*Question*

(Mid Term, Marks = 5, Lesson No. 18)
Write the pseudo code of n-line assembly: dynamic programming for print stations.

*Answer:*

*Question*

(Mid Term, Marks = 10, Lesson No. 16)
Given a sequence [A_{1}, A_{2}, A_{3}, A_{4}]

- Order of A
_{1}= 10 x 100 - Order of A
_{2}= 100 x 5 - Order of A
_{3}= 5 x 50 - Order of A
_{4}= 20 x 50

_{1}, A

_{2}, A

_{3}, A

_{4}in such a way that minimizes the total number of scalar multiplications.

*Answer:*

*Question*

(Mid Term, Marks = 10, Lesson No. 19)
Write the Pseudo code of complete knapsack dynamic programming algorithm for 0-1 knapsack problem.