Short Question & Answers


Q1: Write Chain Matrix multipication algorithm using brute force approach.
Fall 2015 – Mid


Q2: Solve the recurrence: j_{n} = j_{n2}
Fall 2015 – Mid


Q3: Given a sequence [A_{1}, A_{2}, A_{3}, A_{4}]
[A_{1} = 10 x 100], [A_{2} = 100 x 5], [A_{3} = 5 x 50] [A_{4} = 50 x 20]
Compute the order of the product A_{1}, A_{2}, A_{3}, A_{4} 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 2D 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 01 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 01 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 2n^{3} + 3n + 10 ∈ O(n^{4})
Fall 2015 – Mid


Q14: Suppose sequence, b_{0}, b_{1}, b_{2},….., satisfies recurrence relation
b_{k}= 6b_{k1}  9b_{k2} ∀ k ≥ 2
with condition initial condition: b_{0}=2 and b_{1}=6,
then find explicit formula for b_{0}, b_{1}, b_{2}, . . ., 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 nline assembly line algorithm.
Fall 2015 – Mid
Spring 2016 – Mid


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


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


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


Q23: Prove that √n + n= O(n^{3})
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 2d.
Spring 2016 – Mid


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


Q27: Prove that n^{2} ∈ O(n^{2})
Spring 2016 – Mid


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


Q29: Solve the recurrence using substitution method: T(n)=T(n1)+c
Spring 2016 – Mid


