#aoa-may-2018
- Write short notes on : Longest common subsequence The longest common subsequence (LCS) of two strings is the longest sequence of characters that appears in both in the same order (not necess... 1
- Write short notes on : 8 Queen problem The 8-queen problem is to place 8 queens on an 8×8 chessboard so that no two queens attack each other; it is solved by backtracking. Constra... 1
- Write short notes on : Job sequencing with deadlines. Job sequencing with deadlines is a greedy method that picks jobs in decreasing order of profit and puts each one in the latest free time slo... 1
- Explain how backtracking is used for solving n- queens problem. Show the state space tree. Backtracking places queens one row at a time and undoes (backtracks) a placement as soon as no safe column is left for the next row. Problem... 1
- write a detailed note on Hamiltonian cycles. A Hamiltonian cycle is a cycle in a graph that visits every vertex exactly once and returns to the starting vertex. Definition. For a graph... 1
- What do you understand by NP Complete? Explain is subset sum problem NP complete? If so explain A problem is NP-complete if it is in NP and every problem in NP can be reduced to it in polynomial time. Yes, the subset sum problem is NP-c... 1
- Explain different string matching algorithms. String matching finds all occurrences of a pattern P (length m) in a text T (length n). The main algorithms are the naive method, Rabin–Karp... 1
- Sort the list of the elements 10,5,7,6,1,4,8,3,2,9 using merge sort algorithm Sorted list: 1, 2, 3, 4, 5, 6, 7, 8, 9, 10. Merge sort satisfies T(n) = 2T(n/2) + cn , which gives O(nlog n) . Divide (mid = ⌊(low + high)/2... 1
- Solve sum of subsets problem for following 10M N=6 W={3,5,7,8,9,15} & M=20 Also write the Algorithm for it. Solutions: 3, 8, 9, 5, 7, 8 and 5, 15, i.e. x = (1,0,0,1,1,0), (0,1,1,1,0,0) and (0,1,0,0,0,1). Given n = 6 , W = \3, 5, 7, 8, 9, 15\ (alrea... 1
- Explain with example how divide and conquer strategy is used in binary Search? Binary search divides a sorted array into two halves, compares the key with the middle element, and conquers by searching only the half that... 1
- What is backtracking Approach? Explain how it is used in Graph Coloring Backtracking builds a solution step by step and abandons ("backtracks" from) a partial solution as soon as it cannot lead to a valid answer.... 1
- Determine the frequency counts for all statement in the following algorithm Segment Total frequency count = 3n + 2 , so the time complexity is O(n) . StatementFrequency count I = 1;1 while (I <= n) n + 1 X = X + I; n I = I +... 1
- Explain the general procedure of divide and conquer method The Divide and Conquer method is the most widely applicable technique for designing efficient algorithms. It works in three stages, as shown... 1
- Write the difference between greedy method and dynamic programming Greedy method Dynamic programming Does not guarantee an optimal solution Guarantees an optimal solution Assumes sub-problems do not overlap... 1