data structure and algorithm

a) __________ is one of the properties of an algorithm.
(b) __________ is the process of executing a correct program on data sets and measuring the time and space it takes to compute the results.
(c) _________ is a technique of defining a process by itself
(d) A graph with out self loop and parallel edges is __________
(e) A tree with n vertices has _________ edges.
(f) Searching for a word in the dictionary is an example for ________ search.
(g) One of the properties of an algorithm is ‘structured’ (true/false)
(h) Stack works on the strategy of ‘first in first out’ (True/ false)
(i) Circular queue works on the strategy ‘first in first out’ (True/false)
(j) Tree is a __________ data structure.
(k) A binary tree of depth l has atmost ___________ number of nodes
(l) The percentage of memory wastage in linked representation of binary tree is ____________
(m) The percentage of memory wastage in adjacency matrix representation of binary tree is ____________

2.
(a) Define algorithm? What are its properties
(b) Define circular queue? What are its advantages
(c) Draw atleast two connected graph that become disconnected when exactly two edges are removed from them
(d) What are the merits and demerits of recursion
(e) Draw all complete graphs with n=2, 3, 4, 5 vertices.
(f) How can one validate the designed algorithm

PART
1.
(a) Design two different algorithms to check if a given number is prime.
(b) Design an iterative and recursive algorithm to generate Fibonacci sequence of length n.
2.
(a) Explain and illustrate insertion sort algorithm to sort a list of n numbers
(b) Design iterative and recursive algorithm to find the minimum among n elements
3.
(a) Design an algorithm to check whether the given graph is connected from the adjacency matrix representation
(b) Design an iterative and recursive algorithm to search for an element using binary search
4.
(a) Design an iterative algorithm to traverse a binary tree represented in two dimensional matrix
(b) Draw a binary tree of level 6 having atleast 18 nodes and obtain the inorder, preorder sequences of the tree
5.
(a) Design a recursive algorithm to sort a list of elements using quick sort and hand simulate on a data set of atleast 9 elements

6.
(a) Design a recursive algorithm to sort a list of elements using Mergesort and hand simulate on a data set of atleast 9 elements.
7.
(a) Draw all binary trees with six pendent vertices
(b) Design recursive algorithms to traverse a binary tree represented in linked lists in inorder, preorder, postorder.
8. Write short notes on
(a) Stack and its applications
(b) Incidence matrix
(c) One dimensional representation of a Binary tree