CS702 - Advancd Algorithms Analysis and Design Course Page Mcqs Q & A Video Downloads Short Question & Answers   Q1: Write Chain Matrix multipication algorithm using brute force approach.
Fall 2015 – Mid

Q2: Solve the recurrence: jn = jn-2
Fall 2015 – Mid

Q3: Given a sequence [A1, A2, A3, A4]
[A1 = 10 x 100], [A2 = 100 x 5], [A3 = 5 x 50] [A4 = 50 x 20]
Compute the order of the product A1, A2, A3, A4 in such a way that minimizes the total number of scalar multiplications.
Fall 2015 – Mid

Q4: Let N be a set of natural numbers. Then ≤ is relations over N. Prove or disprove the < is reflexive, symmetric and transitive.
Fall 2015 – Mid

Q5: Write algorithm to Closest Pair in 2-D using Divide and Conquer.
Fall 2015 – Mid

Q6: Write algorithm to find line assembly scheduling DP pseudo code
Fall 2015 – Mid

Q7: Write down the 0-1 knapsack problem DP pseudo code
Fall 2015 – Mid

Q8: Write pseudo code of assembly line scheduling.
Fall 2015 – Mid

Q9: Write knapsack for brute force algorithm.
Fall 2015 – Mid

Q10: Write steps for divide and conquer with time complexity.
Fall 2015 – Mid

Q11: Write assembly line dynamic algorithm.
Fall 2015 – Mid

Q12: Use Dynamic Programming to find an optimal solution for the 0-1 Knapsack problem. item weight value knapsack capacity W = 11
 i 1 2 3 4 5 Vi 1 2 5 6 7 Wi 1 6 18 22 28
And write algorithm for it.
Fall 2015 – Mid

Q13: Prove that 2n3 + 3n + 10 ∈ O(n4)
Fall 2015 – Mid

Q14: 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.
Fall 2015 – Mid

Q15: Show that any amount in cents ≥ 20 cents can be obtained using 5 cents and 6 cents coins only.
Fall 2015 – Mid

Q16: Use mathematical induction to prove ∑i=0 to n
(i) = n(n+1)(2n+1)/6
Fall 2015 – Mid

Q17: Write 2 line assembly algorithm
Fall 2015 – Mid

Q18: What is the Fibonacci sequence, write formula for it.
Fall 2015 – Mid

Q19: Write n-line assembly line algorithm.
Fall 2015 – Mid
Spring 2016 – Mid

Q20: Write algorithm knapsack problem by dynamic programming.
Fall 2015 – Mid

Q21: Write algorithm of 2-dimension points.
Fall 2015 – Mid

Q22: Write steps in devide and conquer approach
Spring 2016 – Mid

Q23: Prove that √n + n= O(n3)
Spring 2016 – Mid

Q23: Prove that f(n) = o(g(n) ≡ g(n) = Ωf(n)
Spring 2016 – Mid

Q24: Write down Chain matrix multiplication algorithm.
Spring 2016 – Mid

Q25: Write algorithm for closest pair improved version for 2-d.
Spring 2016 – Mid

Q26: Write down the Brute Force Chain Matrix Multiplication Algorithm and its complexity.
Spring 2016 – Mid

Q27: Prove that n2 ∈ O(n2)
Spring 2016 – Mid

Q28: Write a pseudo Code of algorithm of finding closest pair in 2-D using divide and conquer approach.
Spring 2016 – Mid

Q29: Solve the recurrence using substitution method: T(n)=T(n-1)+c
Spring 2016 – Mid   Course Instructor Dr. N. A. Zafar Ph.D Computer Science Kyushu University, Japan Javascript is disable - Webestools - Vote Service (notation module) Books Introduction to Algorithms by T. H. Cormen, C. E. Leiserson and R. L. Rivest Introduction to Formal Languages and Automata by Peter Linz Fundamentals of Algorithmics by Gilles Brassard and Paul Bretly Discrete Mathematics and Its Applications by Kenneth Rosen Computers & Intractability, Guide to the Theory of NPC by M. R. Garey