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