S. No. Question Unit Explain the following notations; Big O-notation 1 1 Theta notation Omega notation 2 Obtain the average time complexity of quick sort algorithm. 1 3 Explain Strassen’s matrix multiplication method 1 4 Design a non-recursive algorithm for traversal of a binary tree. 2 5 Design a non-recursive algorithm for pre-order traversal of a binary tree. 2 6 Design a non-recursive algorithm for post-order traversal of a binary tree. 2 7 What is Collapsing rule? Improve algorithm by implementing Collapsing rule. 2 ‘find’ 8 What is Weighting Rule? Improve algorithm by implementing Weighting rule. 2 ‘union’ 9 Write an algorithm for obtaining connected components of a given graph. 2 What is an articulation in a graph? What is a bi-connected graph? Write an algorithm for transforming a given 10 2 graph into a bi-connected graph?
S. No. Question Unit 1 Explain the following notations; Big O-notation Theta notation Omega notation 1 2 Obtain the average time complexity of quick sort algorithm. 1 3 Explain Strassen’s matrix multiplication method 1 4 Design a non-recursive algorithm for traversal of a binary tree. 2 5 Design a non-recursive algorithm for pre-order traversal of a binary tree. 2 6 Design a non-recursive algorithm for post-order traversal of a binary tree. 2 7 What is Collapsing rule? Improve ‘find’ algorithm by implementing Collapsing rule. 2 8 What is Weighting Rule? Improve ‘union’ algorithm by implementing Weighting rule. 2 9 Write an algorithm for obtaining connected components of a given graph. 2 10 What is an articulation in a graph? What is a bi-connected graph? Write an algorithm for transforming a given graph into a bi-connected graph? 2
10026_27012017mid1_-_daa_-_sem_I_2016-17.docx