Question Bank - B.tech - Answer Key(nov 2014).docx

BCS 301 DATA STRUCTURES AND ALGORITHMS PART –A [2 Marks] UNIT I Data Structure and Complexity 1. Write down the definition of data structures? A data structure is a mathematical or logical way of organizing data in the memory that consider not only the items stored but also the relationship to each other and also it is characterized by accessing functions. 2. Define Algorithm? Algorithm is a solution to a problem independent of programminglanguage. It consist of set of finite steps which, when carried out for a given set of inputs, produce the corresponding output and terminate in a finite time. 3.What is meant by an abstract data type? An ADT is a set of operation. Abstract data types are mathematical abstractions. Eg.Objects such as list, set and graph along their operations can be viewed as ADT's.

4. What is meant by list ADT? List ADT is a sequential storage structure. General list of the form a1, a2,a3.…., an and the size of the list is 'n'. Any element in the list at the position I is defined to be ai, ai+1 the successor of ai and ai-1 is the predecessor of ai. 5. What are the various operations done under list ADT? • Print list • Insert • Make empty • Remove • Next • Previous • Find kth 6. What are the different ways to implement list? • Simple array implementation of list • Linked list implementation of list 7. What do asymptotic notation means? Asymptotic notations are terminology that is introduced to enable us to make meaningful statements about the time and space complexity of an algorithm. The different notations are Big – Oh notation Omega notation Theta notation.

8. Define O-notation? A function t(n) is said to be in O(g(n)), denoted by t(n) O(g(n)), if t(n) is bounded above by some constant multiple of g(n) for all large n, i.e., if there exists some positive constant c and some nonnegative integer n0 such that T(n) ” cg(n) for all n • n0 9. What is worst-case efficiency? The worst-case efficiency of an algorithm is its efficiency for the worst-case input of size n, which is an input or inputs of size n for which the algorithm runs the longest among all possible inputs of that size. 10. What is best-case and average case efficiency? The best-case efficiency of an algorithm is its efficiency for the best-case input of size n, which is an input or inputs for which the algorithm runs the fastest among all possible inputs of that size. The average case efficiency of an algorithm is its efficiency for an average case input of size n. It provides information about an algorithm behavior on a “typical” or “random” input. UNIT - II 1. Define Linked Lists Linked list consists of a series of structures, which are not necessarily adjacent in memory. Each structure contains the element and a pointer to a structure containing its successor. We call this theNext Pointer. The last cell’sNext pointer points to NULL. 2. State the different types of linked lists The different types of linked list include singly linked list, doubly linked list and circular linked list. List the basic operations carried out in a linked list The basic operations carried out in a linked list include: • Creation of a list • Insertion of a node • Deletion of a node • Modification of a node • Traversal of the list 3. List out the advantages of using a linked list • It is not necessary to specify the number of elements in a linked list during its declaration

• Linked list can grow and shrink in size depending upon the insertion and deletion that occurs in the list • Insertions and deletions at any place in a list can be handled easily and efficiently • A linked list does not waste any memory space 4. State the difference between arrays and linked lists Arrays

Linked Lists

Size of an array is fixed

Size of a list is variable

It is necessary to specify the It is not necessary to specify the number of elements during number of elements during declaration. declaration Insertions and deletions are

Insertions and deletions are carried

somewhat difficult

out easily

It occupies less memory than a It occupies more memory linked list for the same number of elements

5. What is a pointer? Pointer is a variable, which stores the address of the next element in the list. Pointer is basically a number. 6. What is a doubly linked list? In a simple linked list, there will be one pointer named as 'NEXT POINTER' to point the next element, where as in a doubly linked list, there will be two pointers one to point the next element and the other to point the previous element location. 7. Define double circularly linked list? In a doubly linked list, if the last node or pointer of the list, point to the first element of the list, then it is a circularly linked list. 8. What is a stack? Stack is a data structure in which both insertion and deletion occur at one end only. Stack is maintained with a single pointer to the top of the list of elements. The other name of stack is Last-in -First-out list. 9. How do you test for an empty queue?

To test for an empty queue, we have to check whether READ=HEAD where REAR is a pointer pointing to the last node in a queue and HEAD is a pointer that pointer to the dummy header. In the case of array implementation ofqueue, the condition to be checked for an empty queue is READ
UNIT- III 1. What is binary search? Binary search is a remarkably efficient algorithm for searching in a sorted array. It works by comparing a search key K with the arrays middle element A[m]. if they match the algorithm stops; otherwise the same operation is repeated recursively for the first half of the array if K < A[m] and the second half if K > A[m]. K A[0]………A[m-1] A[m] A[m+1]………A[n-1] search here if K
search here if K rel="nofollow">A[m]

2. What are the classic traversals of a binary tree? The classic traversals are as follows i. Preorder traversal: the root is visited before left & right subtrees ii. Inorder traversal: the root is visited after visiting left subtree and before visiting right subtree iii. Postorder traversal: the root is visited after visiting the left and right subtrees 3. Mention an algorithm to find out the height of a binary tree. ALGORITHM Height(T) //Compares recursively the height of a binary tree //Input: A binary tree T //Output: The height of T if T = Φ return –1 else return max{Height(TL), Height(TR)}+1 4. What are binary search trees and what is it mainly used for? Binary search trees is one of the principal data structures for implementing dictionaries. It is a binary tree whose nodes contain elements of a set of orderable items, one element per node, so that all elements in the left subtree are smaller than the element in the subtree’s root and all elements in the right subtree are greater than it. 5. Define AVL Tree.

An empty tree is height balanced. If T is a non-empty binary tree with TL and TR as its left and right subtrees, then T is height balanced if i) TL and TR are height balanced and ii) │hL - hR│≤ 1 Where hL and hR are the heights of TL and TR respectively. 6. What are the various transformation performed in AVL tree? 1.single rotation - single L rotation - single R rotation 2.double rotation -LR rotation -RL rotation 7. What do you mean by balance factor of a node in AVL tree? The height of left subtree minus height of right subtree is called balance factor of a node in AVL tree.The balance factor may be either 0 or +1 or -1.The height of an empty tree is -1. 8. What do you mean by balanced trees? Balanced trees have the structure of binary trees and obey binary search tree properties. Apart from these properties, they have some special constraints, which differ from one data structure to another. However, these constraints are aimed only at reducing the height of the tree, because this factor determines the time complexity. 9. Define Heap. A heap is a partially ordered data structure, and can be defined as a binary tree assigned to its nodes, one key per node, provided the following two conditions are met i.The tree’s shape requirement-The binary tree is essentially complete, that is all the leaves are full except possibly the last level, where only some rightmost leaves will be missing. ii.The parental dominance requirement-The key at each node is greater that or equal to the keys of its children 10.Give three properties of heaps? The properties of heap are  There exists exactly one essentially complete binary tree with ‘n’ nodes. Its height is equal to log2n  The root of the heap is always the largest element  A node of a heap considered with all its descendants is also a heap UNIT – IV 1. Give the general plan for divide-and-conquer algorithms. The general plan is as follows i.A problems instance is divided into several smaller instances of the same problem, ideally about the same size ii.The smaller instances are solved, typically recursively iii.If necessary the solutions obtained are combined to get the solution of the original problem 2.What are the two traversal strategies used in traversing a graph? a. Breadth first search b. Depth first search 3. What is a tree edge and back edge?

In the depth first search forest, whenever a new unvisited vertex is reached for the first time, it is attached as a child to the vertex from which it is being reached. Such an edge is called tree edge because the set of all such edges forms a forest. The algorithm encounters an edge leading to a previously visited vertex other than its immediate predecessor. Such an edge is called a back edge because it connects a vertex to its ancestor, other than the parent, in the depth first search forest. 4. What is a tree edge and cross edge? In the breadth first search forest, whenever a new unvisited vertex is reached for the first time, it is attached as a child to the vertex from which it is being reached. Such an edge is called tree edge. If an edge is leading to a previously visited vertex other than its immediate predecessor, that edge is noted as cross edge. 5. What is transform and conquer technique? The group of design techniques that are based on the idea of transformation is called transform and conquer technique because themethods work as two stage procedures. First in the transformation stage, the problem’s instance is modified to be more amenable (agreeable) to the solution. Then in the second or conquering stage, it is solved. 6. What is greedy technique? Greedy technique suggests a greedy grab of the best alternative available in the hope that a sequence of locally optimal choices will yield a globally optimal solution to the entire problem. The choice must be made as follows i.Feasible : It has to satisfy the problem’s constraints ii.Locally optimal : It has to be the best local choice among all feasible choices available on that step. iii.Irrevocable : Once made, it cannot be changed on a subsequent step of the algorithm 7. Define Divide and Conquer algorithm? Divide and Conquer algorithm is based on dividing the problem to be solved into several, smaller sub instances, solving them independently and then combining the sub instances solutions so as to yield a solution for the original instance. 8. Mention some application of Divide and Conquer algorithm? a. Quick Sort b. Merge Sort c. Binary search 9. What is meant by strongly connected in a graph? An undirected graph is connected, if there is a path from every vertex to every other vertex. A directed graph with this property is called strongly connected. 10.Define out degree of a graph? In a directed graph, for any node v, the number of edges which have v as their initial node is called the out degree of the node v.

New Questions UNIT – V 1. What is dynamic programming and who discovered it?

Dynamic programming is a technique for solving problems with overlapping subproblems. These subproblems arise from a recurrence relating a solution to a given problem with solutions to its smaller subproblems only once and recording the results in a table from which the solution to the original problem is obtained. It was invented by a prominent U.S Mathematician, Richard Bellman in the 1950s. 2. What is backtracking? Backtracking constructs solutions one component at a time and such partially constructed solutions are evaluated as follows i. If a partially constructed solution can be developed further without violating the problem’s constraints, it is done by taking the first remaining legitimate option for the next component. ii.If there is no legitimate option for the next component, no alternatives for the remaining component need to be considered. In this case, the algorithm backtracks to replace the last component of the partially constructed solution with its next option. 3. What is the manner in which the state-space tree for a backtracking algorithm is constructed? In the majority of cases, a state-space tree for backtracking algorithm is constructed in the manner of depth-first search. If the current node is promising, its child is generated by adding the first remaining legitimate option for the next component of a solution, and the processing moves to this child. If the current node turns out to be non-promising, the algorithm backtracks to the node’s parent to consider the next possible solution to the problem, it either stops or backtracks to continue searching for other possible solutions. 4. How can the output of a backtracking algorithm be thought of? The output of a backtracking algorithm can be thought of as an n-tuple (x1, …xn) where each coordinate xi is an element of some finite linearly ordered set Si. If such a tuple (x1, …xi) is not a solution, the algorithm finds the next element in Si+1 that is consistent with the values of (x1, …xi) and the problem’s constraints and adds it to the tuple as its (I+1)st coordinate. If such an element does not exist, the algorithm backtracks to consider the next value of xi, and so on. 5. Give a template for a generic backtracking algorithm. ALGORITHM Backtrack (X[1..i]) //Gives a template of a generic backtracking algorithm //Input X[1..i] specifies the first I promising components of a solution //Output All the tuples representing the problem’s solution if X[1..i] is a solution write X[1..i] else for each element x[Si+1 ]consistent with X[1..i] and the constraints do X[i+1] x Backtrack(X[1..i+1] 6. Write a recursive algorithm for solving Tower of Hanoi problem. ALGORITHM To move n>1 disks from peg1 to peg3, with peg2 as auxiliary, first move recursively n-1 disks from peg1 to peg2 with peg3 as auxiliary.  Then move the largest disk directly from peg1 to peg3  Finally move recursively n-1 disks from peg2 to peg3 with peg1 as auxiliary  If n=1 simply move the single disk from source peg to destination peg. 7. What is the basic operation in the Tower of Hanoi problem and give the recurrence relation for the number of moves?

The moving of disks is considered the basic operation in the Tower of Hanoi problem and the recurrence relation for the number of moves is given as M(n)=2M(n)+1 for n>1 M(1)=1 8. What is n-queens problem? The problem is to place ‘n’ queens on an n-by-n chessboard so that no two queens attack each other by being in the same row or in the column or in the same diagonal. 9.What is the traveling salesman problem? The problem can be modeled as a weighted graph, with the graph’s vertices representing the cities and the edge weights specifying the distances. Then the problem can be stated as finding the shortest Hamiltonian circuit of the graph, where the Hamiltonian is defined as a cycle that passes through all the vertices of the graph exactly once. 10. What are the strengths of backtracking and branch-and-bound? The strengths are as follows i.It is typically applied to difficult combinatorial problems for which no efficient algorithm for finding exact solution possibly exist ii.It holds hope for solving some instances of nontrivial sizes in an acceptable amount of time iii.Even if it does not eliminate any elements of a problem’s state space and ends up generating all its elements, it provides a specific technique for doing so, which can be of some value.