Introduction: Algorithm Specification, Performance Analysis -Space complexity, Time complexity, Asymptotic Notations (Big-oh notation, Omega notation, Theta notation).
1. Explain the various algorithm design methodologies problem.
2. Write about asymptotic notations and give its properties
3. Give the Big–O notation definition and briefly discuss with suitable example
4. Explain the method of determining the complexity of procedure by the step count approach. Illustrate with an example.
5. Define Time and Space Complexity, and calculate the time space complexity for multiplication of two matrices.
6. Write different pseudo code conventions used to represent an algorithm
7. What do you mean by performance analysis? Give the algorithm for matrix multiplication and find the time complexity using step–count method.
8. What are the different mathematical notations used for algorithm analysis? Explain them. (Ans: asymptotic notations)
9. Give the algorithm for transpose of a matrix of size mxn and determine the time complexity of the algorithm by frequency – count method.
Divide and Conquer: General method, Binary search, Merge sort, Quick sort, Strassen’s matrix multiplication.
1. Write the general method of Divide – And – Conquer approach.
3. Describe binary search in detail and provide time complexity analysis with an example
4. Write a recursive algorithm for binary search and also bring out its efficiency.
5. Discuss the time complexity of Binary search algorithm for best and worst case.
6. Given 2 sorted lists of numbers. Write the algorithm to merge them and analyze its time complexity.
7. Discuss the working strategy of merge sort and illustrate the process of merge sort algorithm for the given data: 43, 32, 22, 78, 63, 57, 91 and 13
8. Apply Merge Sort to sort the list a[1:10]=(31,28,17,65,35,42.,86,25,45,52). Draw the tree of recursive calls of merge sort, merge functions.
9. Illustrate the tracing of quick sort algorithm for the following set of numbers:25, 10, 72, 18, 40, 11, 64, 58, 32, 9.
10. Write Divide – And – Conquer recursive Quick sort algorithm and analyze the algorithm for average time complexity.
11. Derive the time complexity of the Quicksort algorithm for the worst case.
Greedy method: General method, Knapsack problem, Job sequencing with deadlines, Minimum cost spanning trees, Single source shortest paths.
1. Explain the general principle of Greedy method and also list the applications of Greedy method.
2. Solve the following instance of knapsack problem using greedy method. n=7(objects), m=15, profits are (P1,P2,P3,P4,P5,P6,P7)=(10,5,15,7,6,18,3) and its corresponding weights are (W1,W2,W3,W4, W5, W6, W7 )=(2,3,5,7,1,4,1).
3. State the Greedy Knapsack. Find an optimal solution to the Knapsack instance n=3, m=20, (P1, P2, P3) = (25, 24, 15) and (W1, W2, W3) = (18, 15, 10)
4. Find an optimal solution to the knapsack instance n=7 objects and the capacity of knapsack m=15. The profits and weights of the objects are (P1,P2,P3,P4,P5,P6,P7)=(10,5,15,7,6,18,3), (W1,W2,W3,W4, W5,W6,W7)=(2,3,5,7,1,4,1) respectively.
5. Write and explain Prism’s algorithm for finding minimum cost spanning tree of a graph with an example.
6. What is a Minimum Cost Spanning tree? Explain Kruskal’s Minimum costs panning tree algorithm with a suitable example.
7. What is a Spanning tree? Explain Prim’s Minimum cost spanning tree algorithm with suitable example
8. Discuss the Dijkstra’s single source shortest path algorithm and derive its time complexity.
9. A motorist wishing to ride from city A to B. Formulate greedy based algorithms to generate shortest path and explain with an example graph.
10. Discuss the single-source shortest paths algorithm with a suitable example.
12. Use the greedy algorithm for sequencing unit time jobs with deadlines and profits to generate the solution when n=7, (p1, p2,…p7)=(3, 5, 20, 18, 1, 6, 30), and (d1, d2,…, d7)=(1, 3, 4, 3, 2, 1, 2).
13. State the Job – Sequencing with deadlines problem. Find an optimal sequence to the n=5 Jobs where profits (P1, P2, P3, P4, P5) = (20, 15, 10, 5, 1) and deadlines (d1, d2, d3, d4, d5) =( 2, 2, 1, 3, 3).
Dynamic Programming: The General method, All pairs shortest path problem, Optimal binary search trees, 0/1 knapsack, Reliability design, The Travelling sales person problem, Matrix-chain multiplication.
3. With an example, explain how to construct OBST with successful and unsuccessful search probabilities.
4. Solve the following instance of 0/1 KNAPSACK problem using Dynamic programming n = 3, (W1, W2, W3) = (2, 3, 4), (P1, P2, P3) = (1, 2, 5), and m = 6.
5. Define merging and purging rules in 0/1 knapsack problem and explain with an example.
6. Describe the Dynamic 0/1 Knapsack problem. Find an optimal solution for the dynamic programming 0/1 knapsack instance for n=3, m=6, profits are (p1, p2, p3) = (1, 2, 5), weights are (w1, w2, w3)=(2, 3, 4).
7. What is principles of optimality? Explain how travelling sales person problem uses the dynamic programming technique with example?
UNIT-V
Backtracking: The General method, N-Queen problem, Sum of subsets, Graph coloring, Hamiltonian cycles.
1. Write control abstraction for backtracking. Explain with an example.
2. Why Backtracking always produces an optimal solution? Justify
3. Draw the state-space tree along with answer nodes for 4-queens problem
4. What is a backtracking? Give the explicit and implicit constraints in 8 queen’s problem.
5. State N-Queens problem and solve 8-Queens problem using backtracking
6. Find all possible subsets of w that sum to m. Let w={5,7,10,12,15,18,20}and m=35 and draw the portion of the state space tree that is generated using backtracking.
7. Give the statement of sum –of subsets problem. Find all sum of subsets for n=4, (w1, w2, w3, w4) = (11, 13, 24, 7) and M=31. Draw the portion of the state space tree using fixed –tuple sized approach.
8. Solve the following instance of sum of subsets problem using backtracking. W = (5, 7, 10, 12, 15); M = 15.
9. Explain the Graph–Coloring problem and draw the state space tree for m= 3 colors and n=4 vertices graph. Discuss the time and space complexity.
10. State and explain m- colourability decision problem.
11. Write an algorithm for finding m-coloring of a graph and explain with an example.
12. What are the applications of graph coloring? Explain in detail.
13. What is a Hamiltonian Cycle? Explain how to find Hamiltonian path and cycle using backtracking algorithm?
14. Write an algorithm to determine the Hamiltonian Cycle in a given graph using backtracking.
Branch and Bound: The method, 0/1 knapsack problem, Travelling sales person problem.