CS702 – Advanced Algorithms Analysis and Design
In CS702 Advanced Algorithms Analysis and Design we have you covered with Digitized Past Papers From Fall of Mid Term and Final Term.
+92 307 41 51 71 8 vuassassins@gmail.com
In CS702 Advanced Algorithms Analysis and Design we have you covered with Digitized Past Papers From Fall of Mid Term and Final Term.
1. Steps of greedy algorithm design
2. Pseudo code of Huffman coding
3. Prove that circuit-sat is hard
4. Prove gcd(an,bn)=n.gcd(a,b)
5. Decrypted message (example in slides)
6. Backtracking to find maximum profit maximum weight is 8. see example in backtracking)
7. In DFS if vi is en-queued before vj then prove that d[vi] b ≥ 1 and the invocation EUCLID (a, b) takes k ≥ 1 recursive calls, then a ≥ Fk+2
and b ≥ Fk+1 ?
22. If p is prime, a is positive integer not divisible by p, ap-1 = 1 mod p OR ap = a mod p
23. If gcd(a, m) = 1 and m > 1, then a has a unique inverse a′ (modulo m).
24. If X is problem such that P‘≤ p X for some P’∈NPC, then X is NP-hard. Moreover, X ∈
NP→X∈ NPC.
25. Why we use dynamic programming? Give limitations…..5 marks
26. Pseudo code for Johnson’s algorithm….5 marks
27. How to print path in BFS algorithm…5 marks.
28. Prove that for a problem X and P’ such that P’ <p NPC , X is NP hard. …10 marks
29. Extend Shortest Path algorithm.5 marks.