Define data structure. List the operations that can be performed on data structure.
[3 marks]Apply insertion sort algorithm on following elements. Show your steps. 32, 74, 68, 21, 28.
[4 marks]What is order of growth of algorithm? Explain Big Oh (O), Omega (Ω) and Theta (Θ) notations with example.
[7 marks]Compare greedy and dynamic programming techniques for problem solving.
[3 marks]Write and explain an algorithm for POP operation on the stack.
[4 marks]Sort following elements applying quick sort algorithm. State time complexity of quick sort in best, worst and average case. 21, 79, 45, 66, 31, 27, 93, 46
[7 marks]Explain linear probing, quadratic probing and double hashing to solve hash collisions.
[7 marks]State differences between linear data structure and non-linear data structure.
[3 marks]What is queue? Explain ENQUEUE and DEQUEUE operations on queue.
[4 marks]Convert following infix expression to postfix showing content of stack in every step in a tabular form. (A * (B + C)) – (D * E) – (F / G) + H
[7 marks]Define following for Graph (i) Isolated Node (ii) Digraph (iii) Path
[3 marks]How to detect overflow while inserting an element in circular queue? Explain with example.
[4 marks]Write and explain algorithm to insert an element at specified position in doubly linked list.
[7 marks]Insert following elements in given AVL tree. 11, 5, 211
[3 marks]Briefly explain divide and conquer method to solve large integer multiplication problem.
[4 marks]Explain BFS and DFS traversal of Graph in detail with suitable example.
[7 marks]Explain adjacency matrix representation of a graph.
[3 marks]Explain any one method to solve recurrence.
[4 marks]Construct Binary Search Tree (BST) for given list of elements. Also explain how to find minimum and maximum elements from BST. 34, 56, 32, 18, 12, 51, 43, 49, 42, 60
[7 marks]Define Principle of Optimality. How dynamic programing gives efficient solution to binomial coefficient problem?
[3 marks]Explain minimax principle used in game theory.
[4 marks]What is Minimum Spanning Tree (MST)? Apply Kruskal’s algorithm to find MST of following graph. Also calculate total weight of MST.
[7 marks]Write and explain greedy activity selection algorithm.
[3 marks]Apply dynamic programming and find longest common subsequence of given strings. A = “XYZYXZ” and B = “XZYXY”
[4 marks]Explain backtracking method to solve 4 – queens problem.
[7 marks]