CS-702 Advancd Algorithms Analysis and Design
Mcqs
Q & A
Video
Online Test
Foram
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 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
Books

Introduction to Algorithms
by T. H. Cormen,

Computers and Intractability, Guide to the Theory of NP Completeness by M. R. Garey and D. S. Johnson

An 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