In the name of ALLAH, the most beneficient, the most merciful

## Advanced Algorithms Analysis and Design (CS702)

Subjective, Short Questions from Past Papers

## Subjective Questions

### Question

(Mid Term, Marks = 10, Lesson No. )

algorithm of shortest distance between n points

### Question

(Mid Term, Marks = 10, Lesson No. )

Prove tautology by logical equivalence.

### Question

(Mid Term, Marks = 10, Lesson No. )

assembly line problem 6 stations

### Question

( Term, Marks = , Lesson No. )

write down the brute force chain matrix multiplication algorithm and complexity.

### Question

( Term, Marks = , Lesson No. )

write pseudo code algorithm of merge sort.

### Question

(Final Term, Marks = 5, Lesson No. 24)

Explain situation and example in which greedy algorithm does not work.

### Question

(Final Term, Marks = 10, Lesson No. 28)

Write BFS (Breadth First Search) pseudo code algorithm.

### Question

(Final Term, Marks = 10, Lesson No. 23)

Write pseudo code of LCS (Longest Common Subsequence) problem.

### Question

(Final Term, Marks = 10, Lesson No. 41)

Prove that if p is prime, a is positive integer not divisible by p,
ap-1 = 1 mod p OR ap = a mod p

### 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.

### Question

(Final Term, Marks = 5, Lesson No. 36)

Write pseudo code of EXTEND-SHORTEST-PATH.

### Question

(Final Term, Marks = 5, Lesson No. 41)

Decrypt 0981 0461 if encrypted using RSA
public key = (e, n) = (13, 43.59 = 2537)

### Question

(Final Term, Marks = 5, Lesson No. 29)

Write pseudo code of DFS-Visit.

### Question

(Final Term, Marks = 10, Lesson No. 24)

Write pseudo code of optimal binary search tree.

### Question

(Final Term, Marks = 5, Lesson No. 26)

Write pseudo code of Huffman algorithm.

### Question

(Final Term, Marks = 5, Lesson No. 38)

Prove that if a|b, a|c then a|(b + c) ∀ a, b, c ε Z

### 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).

### Question

(Final Term, Marks = 5, Lesson No. 39)

Prove that x and y are relatively prime iff gcd(x, y) = 1

### Question

(Mid Term, Marks = 5, Lesson No. 19)

Write the pseudo code of 0-1 knapsack brute force algorithm.

### Question

(Mid Term, Marks = 5, Lesson No. 18)

Write the pseudo code of n-line assembly: dynamic programming for print stations.

### Question

(Mid Term, Marks = 10, Lesson No. 16)

Given a sequence [A1, A2, A3, A4]

• Order of A1 = 10 x 100
• Order of A2 = 100 x 5
• Order of A3 = 5 x 50
• Order of A4 = 20 x 50
Using the Brute force method compute the order of the product A1, A2, A3, A4 in such a way that minimizes the total number of scalar multiplications.

### Question

(Mid Term, Marks = 10, Lesson No. 19)

Write the Pseudo code of complete knapsack dynamic programming algorithm for 0-1 knapsack problem.