Suggestion for Even semester
Design Analysis and Algorithm
Module-1
[Link] is Algorithm? Explain it’s properties.
[Link] of Algorithm’s analysis- Best case , Worst case , Average
case.
[Link] is Time complexity and Space complexity [ just one marks]
[Link] is Asymptotic Notation? Explain Big-O notation, Omega
notation, Theta notation.
5. [ For Math -5 marks ]
Recurrence Relation : -
(a) Substitution Method:
• [T(n)= T(n/2)+C if n>1 ,
1 if n=1]
(b) Iteration Method
• [ T (n) = 1 if n=1
= 2T (n-1) if n>1 ]
(c) Recursion Tree Method
(d) Master Method
• T (n) = aT(n/b)+ f (n) with a≥1 and b>1 be constant & f(n) be a
function
[Link] between Recursion and Iteration. Short note on
Recursion tree.
Module-2
[Link] is greedy method? Explain it’s property
[Link] is Brute-Force Approach? Explain advantage and
disadvantage.
[Link] Knapsack problem:
Consider the below example:
• Objects: 1 2 3 4 5 6 7
• Profit (P): 5 10 15 7 8 9 4
• Weight(w): 1 3 5 4 1 3 2
• W (Weight of the knapsack): 15
• n (no of items): 7
[Link] is 0/1 Knapsack Problem .
Example of 0/1 knapsack problem.
• P={1,2,5,6}
• W={2,3,4,5}
• M=8 The weight of the knapsack
• n=4 The number of items
5. Branch and Bound.
Example :
Jobs = {j1, j2, j3, j4}
P = {10, 5, 8, 3}
d = {1, 2, 1, 2}
6. Analyse the time complexity of Merge sort and Quick sort
7. What is Dynamic Programming ? explain it’s properties
8. Algorithm of Fibonacci
[Link] the algorithm of chain Matrix multiplication.
10. Solve Eight-Queen’s problem using backtracking approach
[Link] the parenthesization of a matrix-chain product whose
sequence of dimensions is < 5 , 10,3,12,5,50,6>
• Give an algorithm of above procedure
• analyse it’s procedure
12. Difference between Divide-and-conquer & Dynamic
programming
13. Explain Bellman-Ford's algorithm for single source shortest path
problem.
14. Write an algorithm of N-queen’s problem.
15. Difference between Backtracking and Branch and Bound.
16. Algorithm of heap Sort, Merge sort , Quick sort {time
complexity}
[Link] is Travelling Sales man problem :-
[Link] and Bound [ just know the concept & example ]
[Link] notes :
a. 8 queens problem
b. Bellman-Ford Algorithm
c. Heuristic Algorithm
20. Create a Max-Heap-containing the following elements:
10, 20, 30, 40, 50, 60, 70, 80, 90, 100 (also practice Min-Heap)
21. Bin packing [ just know the concept & solve the problem]
[Link] the algorithm to solve the job sequencing with Deadline
problem using Greedy method. What is the time complexity of the
algorithm. ***
Module:3
[Link] between BFS and DFS
[Link] Floyd’s algorithm. Find it’s time complexity
3. Difference between prim’s and Kruskal Algorithm
4. Find out the minimum cost spanning tree using any
algorithm:(using Prim’s and Kruskal Algorithm)
5. Find the maximum flow of the following network. Mention each
steps.
[Link] the algorithm in Greedy method to find the maximum
spanning tree by prim’s algorithm. What is the time complexity of
the algorithm.**
[Link] the Dijkstra’s algorithm for finding the shortest path And
also short notes on Dijkstra’s algorithm.**
[Link] notes:
a. Directed and Undirected graph
b. What is In-Degree and Out- Degree
c. Bridge
d. Minimum Spanning Tree
e. Network Flow Diagram
f. Ford -Fulkerson algorithm
Module:4
[Link] is Complexity classes? Types of complexities classes [ Ans:
P,NP, NP-complete and NP-hard.
[Link] Cook’s Theorem
Module:5
[Link] is Approximation Algorithm and Approximation Schemes?
[Link] is randomized Algorithm.
[Link] Selection problem-
Example: Given 10 activities along with their start and end time as
• S = (A1 A2 A3 A4 A5 A6 A7 A8 A9 A10)
Si = (1,2,3,4,7,8,9,9,11,12)
fi = (3,5,4,7,10,9,11,13,12,14)
4. Explain Class of problems beyond NP – P SPACE
5. Find the minimum number of scalar operation needed to
multiply the matrices A1, A2, A3 and A4 having dimensions 30×35,
35×15, 15×5 and 5×10 respectively.
