Mekala Rajasekaran

RANIPPETTAI ENGINEERING COLLEGE DEPARTMENT OF INFORMATION TECHNOLOGY CS-2201 DATA STRUCTURES AND ALGORITHMS 2 MARKS QUESTIONS AND ANSWER UNIT I LINEAR STRUCTURES 1. Define ADT. An abstract data type is a set of operations. The implementation of these set of operations is not defined. The implementation depends on the application of ADT. E.g. Objects such as lists, sets and graphs along with their operations can be viewed as ADT. 2. Define List ADT. A list is defined as a linear collection of data items. General Form A1, A2, A3………….,AN A1  First element AN  Last element N  Size of the list The list of size 0 is called empty list 3. Define Linked list. A linked list is a data structure which contains a series of structures, with each structure containing an element and a pointer to next structure .This is called next pointer. Each structure consists of i. Element ii. Next pointer General form of a linked list Figure: A linked list 4. What is the use of a header node? There are three problems associated with linked list: 1. There is no way to insert at the front of the list. 2. Deleting from the front of the list changes the start of the list thus careless coding will lose the list. 3. The Deletion algorithm requires us to keep track of the cell before the one that we want to elete To solve all the three problems, a node, sometimes called as header or dummy node or entinal node is used The header is in position 0 Linked List with a header 5. Why cursor implementation of linked list is used? Cursor implementation is useful where linked list concept has to be implemented without using pointers. Many languages like BASIC and FORTRAN,do not support pointers.If linked lists are required and pointers are not available ,then an alternative implementation must be used which is known as cursor implementation. 6. What are the Difference between cursor implementation and pointer implementation Pointer implementation Cursor implementation 1. Data are stored in a collection of structures. Each structure contains a data and next pointer 1. Data are stored in a global array of structures. Here array index is considered as an address. 2. Malloc function is used to create a node and free function is used to release the cell. 2. Cursor Alloc function is used to Allocate a space for new node and cursor free function is used to release the cell. 7. What is a doubly linked list? A Doubly linked list is a linked list in which each node has three fields namely, Data field Forward Link(FLINK) Backward Link(BLINK) FLINK-Points to the successor node in the list BLINK-Points to the predecessor node in the list 8. What are the advantages of doubly linked list? Deletion operation is easier. Finding the predecessor and successor of node is easier 9. Define circular linked list. In circular linked list the pointer of the last node points to the first node. Circular linked list can be implemented as singly linked list or doubly linked list with or without headers 10. What are the types of circular linked list? 1) Singly linked circular list It is a linked list in which the last node of the list points the first node. 2) Doubly linked circular list Doubly linked circular list is Doubly linked list in which the forward link of the last node points to the first node and backward link of the first node points to the last node of the list. 11. What are advantages of circular linked list? It allows to traverse the list starting at any point. It allows quick access to the first and last records. Doubly linked Circular list allows to traverse the list in either direction. 12. What are the applications of list? The applications of lists are the following: 1. Polynomial ADT 2. Radix Sort 3. Multilist 13. What is radix sort? The Radix Sort perform sorting, by using bucket sorting technique. In Radix Sort, first, bucket sort is performed by least significant digit, then next digit and so on.It is sometime known as Card Sort. 14. Define Stack. A Stack is a list in which the insertions and deletions can be performed in only one position called top. It is also called as LIFO (Last –In –First -Out) list. Push – Insert an element into the stack. Pop – Deletes the most recently inserted element. The most recently inserted element can be examined prior to Pop by Top routine. 15. What are the applications of stack? The Application of stack are Balancing Symbols Postfix (Reverse Polish) expressions Infix to Postfix expression Function call 16. Write the algorithm for balancing symbols. Algorithm 1. Make an empty stack. Read characters until end of file. 2. If the character is an opening symbol, push it onto stack. 3. If it is a closing symbol and if the stack is empty report an error. 4. If it is a closing symbol (of same type), pop the stack, and otherwise report an error. 5. At end of file, if the stack is not empty, report error. 17. Define Queue. Queue is a list in which insertion is done at one end, deletion is performed at other end . It is also called as FIFO (First –In –First -Out) list.  Enqueue: which inserts an element at the end of the list called rear.  Dequeue: deletes the element at the start of the list called front. 18. What are the applications of queue? Jobs sent to line printer are placed on queue. Lines at ticket counters are queues. Computer networks where the sensor takes the jobs of the client as per the queue strategy. Calls to large companies are placed on queue when all operations are busy. In large universities, where resources are limited, students must sign a waiting list it all terminals are occupied. Queuing theory in mathematics : o Deals with computing how long users expect to wait on line, how long the line gets etc: o The answer depends on how frequently users arrive to the line and how long it takes to process a user once the user is served. 19. What is a circular queue? When front or rear gets to end of array, it is wrapped around to the beginning .this is known as circular array implementation. 20. What are the exceptional conditions in a queue? Overflow –inserting an element when the queue is full. Underflow –deleting an element from the queue when queue is empty. UNIT II TREE STRUCTURES 1. Define tree? A tree is a collection of nodes. A tree consists of a root and zero or more sub trees T1, T2…………TK each of whose roots are connected to root. 2. Define leaf? Node with no children are called leaves. Example: The leaves in above tree are B,C,H,I,P,Q,K,L,M,N. 3. Define Path. A path from node n1 to nk is defined as a sequence of nodes n1,n2,…………nk such that ni is a parent of ni+1 for 1≤ i < k. 4. What is a Binary tree? A binary tree is a tree in which no node can have more than two children. It is a binary tree that consists of a root and two subtrees TL and TR. 5. What are the two methods of binary tree implementation? There are 2 ways for implementing binary trees Linear Representation Linked Representation Linear Representation The elements are represented using arrays. For any element in position i, the left child is in position 2i, the right child is in position (2i + 1) and the parent is in position (i/2). Linked Representation Fig: Linear representation of binary trees The elements are represented by pointers. The declaration of tree nodes is similar in structure for doubly linked lists in which each node consists of three fields Pointer to left subtree Pointer to right subtree Data Leaf nodes are represented by assigning both left and right pointer field as NULL. 6. What are the applications of binary tree? The aplications of binary tree are, 1. searching and 2. compiler design 7. What is meant by traversing? Traversing means visiting each node only once. Tree traversal is a method for visiting all the nodes in the tree exactly once. 8. What are the different types of traversing? There are 3 types of tree traversals Inorder Traversal Preorder Traversal Postorder Traversal 9. Define pre-order traversal? Pre-order traversal entails the following steps; a. Visit the root node b. Traverse the left subtree c. Traverse the right subtree 10. Define post-order traversal? Post order traversal entails the following steps; a. Traverse the left subtree b. Traverse the right subtree c. Visit the root node 11. Define in -order traversal? In-order traversal entails the following steps; a. Traverse the left subtree b. Visit the root node c. Traverse the right subtree 12. Define expression trees? Expression tree is a binary tree in which the leaf nodes are operands and other nodes contain operators. For eg: Expression tree for (a+b*c)+((d*e+f)*g) 13. Define AVL Tree. An AVL tree is a binary search tree, except that for every node in the tree, the height of left and right subtrees can differ by atmost 1.  The height of empty tree is defined to be -1. 14. Define Binary Search Tree. Binary search tree is a binary tree in which for every node X in the tree, the values of all the keys in its left subtree are smaller than the key value in X, and the values of all keys in its right subtree are larger than the key value in X. Example: 15. Write the difference between binary tree and Binary Search Tree? Binary Tree Binary Search Tree A tree is said to be a binary tree if it has atmost two children It is a binary tree in which the key values in left node is less than root and the key values in right is greater than the root Example Example: 16. Define Priority Queue. A priority queue is special kind of queue data structure which will have precedence over jobs. It allows the operations of inserting a new element and deleting the minimum element. 17. What are the applications of Priority Queue? 1. CPU scheduling with process priority 2. For external sorting 3. Implementation of Greedy algorithm 18. What are the Properties of Binary Heap? The properties of binary heap are • Structure property • Heap order property 19. What is structure property of Binary Heap? Structure Property:  A heap is a binary tree that is completely filled with the possible exception of bottom level which is filled from left to right. Such a tree is known as complete binary tree.  A complete binary tree of height h has between 2h and 2h+1-1 nodes.  For eg. If the height is 3 than the number of nodes is in between 8 and 15(i.e 23 and 24-1). A Complete binary tree 20. What is heap order property of Binary Heap? Heap Order Property:  It allows operations to be performed quickly.  In order to find the minimum quickly, the smallest element should be the root.  Every node should be smaller than all of its descendants.  For every node X, the key in the parent of X is smaller than or equal to the key in X, with the exception of the root. Binary Tree with Structure and Heap order property: UNIT III HASHING AND SETS 1. Define Hashing. Hash table data structure is an array of some fixed size containing the keys. A key is a string with an associated value. The implementation of hash tables is called hashing. Hashing is a technique used for performing insertion, deletion and find operations. 2. Define Hash function. A hash function is a key to address transformation which acts upon a given key to compute the relative position of the key in an array. A simple hash function Hash (Key) = key mod Tablesize 3. Write notes on separate chaining. Separate chaining is a technique that keeps a list of elements that hash to the same value. This is called separate chaining because each hash table element is a separate chain(linked list). A separate chaining hash table 4. What is linear probing? Probing is the process of getting next available cell. In linear probing, F is a linear function of i, typically F (i) = i.This amounts to trying cells sequentially in search of an empty cell. If the end of the table is reached and no empty cells has been found then the search is continued from the beginning of the table. It has tendency to create clusters in the table. 5. Define Primary clustering. Any key that hashes into cluster will require several attempts to resolve the collision, and then it will add to the cluster. 6. What is Quadratic probing? Quadratic probing is a collision resolution method that eliminates the primary clustering problem of linear probing. The collision function is quadratic, the popular choice is (i) = i2. 7. What are the disadvantages of Quadratic probing? There is no guarantee of finding an empty cell once the table gets more than half full, or even before the table gets half full if the table size is not prime. If quadratic probing is used, and the table size is prime, then a new element can always be inserted if the table is at least half empty. 8. What is secondary clustering? Although quadratic probing eliminates primary clustering, elements that hash to the same position will probe the same alternate cells. This is known as secondary clustering. 9. What is rehashing? If the table gets too full, the running time for the operations will start taking too long and inserts might fail for closed hashing with quadratic resolution. This can happen if there are too many deletions intermixed with insertions. A solution, then, is to build another table that is about twice as big and scan down the entire original hash table, computing the new hash value for each (non-deleted) element and inserting it in the new table. 10. What is extendible hashing? Extendible hashing is used where the amount of data is too large to fit in main memory. The main consideration then is the number of disk accesses required to retrieve data. We assume that at any point we have n records to store, and at most m records fit in one disk block so assume m = 4. Extendible hashing, allows a find to be performed in two disk accesses. The root of the "tree" contains four pointers determined by the leading two bits of the data. Each leaf has up to m = 4 elements. D will represent the number of bits used by the root, which is sometimes known as the directory. 11. What is equivalence relation? A relation R is defined on a set S if for every pair of elements (a, b), a, b €S, a R b is either true or false. If a R b is true, then we say that a is related to b. 12. What are the properties of equivalence relation? An equivalence relation is a relation R that satisfies three properties: 1. (Reflexive) a R a, for all a €S. 2. (Symmetric) a R b if and only if b R a. 3. (Transitive) a R b and b R c implies that a R c. 13. What is equivalence class? The equivalence class of an element a €S is the subset of S that contains all the elements that are related. Every member of S appears in exactly one equivalence class. To decide if a ~ b, we need only to check whether a and b are in the same equivalence class. 14. What are the operations on a set? There are two permissible operations. 1. The first is find, which returns the name of the set (that is, the equivalence class) containing a given element. 2. The second operation is Union which merges the two equivalence classes containing a and b into a new equivalence class. 3. 15. What are the types of smart union algorithms? 1)Union-By-Size 2)Union-By-Height 16. What is Union by size? In this method the smaller tree is made a subtree of the larger one. 17. What is union by height? In this method the unions are performed by making the shallow tree a subtree of the deeper tree. 18. What is path compression? If there many number of find operation than unions, this running time is worse than that of the quick-find algorithm. Moreover, no more improvements possible is possible for the union algorithm. Therefore, the only way to speed the algorithm up, without reworking the data structure entirely, is known as path compression. 19. What are the applications of set? 1) Disjoint-set data structures model the partitioning of a set, for example to keep track of the connected components of an undirected graph. This model can then be used to determine whether two vertices belong to the same component, or whether adding an edge between them would result in a cycle. Finding connected components: For all v in V do MAKE-SET(v) For all (u,v) in E do UNION(u,v) 2) This data structure is used for implementing Kruskal's algorithm to find the spanning tree of a graph. 3) Maintain lists of duplicate copies of webpages. minimum 20) Write the code for hash function? Index Hash (const Char *key, int TableSize) { unsigned int HashVal = 0; while ( *key != ’\0’) HashVal += *key++; return HashVal % TableSize; } UNIT IV GRAPHS 1. Define Graph. A graph G consist of a nonempty set V which is a set of nodes of the graph, a set E which is the set of edges of the graph, and a mapping from the set for edge E to a set of pairs of elements of V. It can also be represented as G=(V, E). 2. Define adjacent nodes. Any two nodes which are connected by an edge in a graph are called adjacent nodes. For example, if an edge x ε E is associated with a pair of nodes (u,v) where u, v ε V, then we say that the edge x connects the nodes u and v. 3. What is a directed graph? A graph in which every edge is directed is called a directed graph. 4. What is a undirected graph? A graph in which every edge is undirected is called a directed graph. 5. What is a loop? An edge of a graph which connects to itself is called a loop or sling. 6. What is a simple graph? A simple graph is a graph, which has not more than one edge between a pair of nodes than such a graph is called a simple graph. 7. What is a weighted graph? A graph in which weights are assigned to every edge is called a weighted graph. 8. Define outdegree 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. 9. Define indegree of a graph? In a directed graph, for any node v, the number of edges which have v as their terminal node is called the indegree of the node v. 10. Define path in a graph? The path in a graph is the route taken to reach terminal node from a starting node. 11. What is a simple path? A path in a diagram in which the edges are distinct is called a simple path. It is also called as edge simple. 12. What is a cycle or a circuit? A path which originates and ends in the same node is called a cycle or circuit. 13. What is an acyclic graph? A simple diagram which does not have any cycles is called an acyclic graph. 14. 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. 15. When is a graph said to be weakly connected? When a directed graph is not strongly connected but the underlying graph is connected, then the graph is said to be weakly connected. 16. Name the different ways of representing a graph? a. Adjacency matrix b. Adjacency list 17. What is an undirected acyclic graph? When every edge in an acyclic graph is undirected, it is called an undirected acyclic graph. It is also called as undirected forest. 18. What are the two traversal strategies used in traversing a graph? a. Breadth first search b. Depth first search 19. What is a minimum spanning tree? A minimum spanning tree of an undirected graph G is a tree formed from graph edges that connects all the vertices of G at the lowest total cost. 20. Name two algorithms two find minimum spanning tree Kruskal’s algorithm Prim’s algorithm 21. Define graph traversals. Traversing a graph is an efficient way to visit each vertex and edge exactly once. 22. List the two important key points of depth first search. i) If path exists from one node to another node, walk across the edge – exploring the edge. ii) If path does not exist from one specific node to any other node, return to the previous node where we have been before – backtracking. 23. What do you mean by breadth first search (BFS)? BFS performs simultaneous explorations starting from a common point and spreading out independently. 24. Differentiate BFS and DFS. No. DFS BFS 1. Backtracking is possible from a Backtracking is not possible 2. Vertices from which exploration is incomplete are processed in a The vertices to be explored are organized as a 3. Search is done in one particular The vertices in the same level are maintained 25. What do you mean by tree edge? If w is undiscovered at the time vw is explored, then vw is called a tree edge and v becomes the parent of w. 26. What do you mean by back edge? If w is the ancestor of v, then vw is called a back edge. 27. Define biconnectivity. A connected graph G is said to be biconnected, if it remains connected after removal of any one vertex and the edges that are incident upon that vertex. A connected graph is biconnected, if it has no articulation points. 28. What do you mean by articulation point? If a graph is not biconnected, the vertices whose removal would disconnect the graph are known as articulation points. 29. What do you mean by shortest path? A path having minimum weight between two vertices is known as shortest path, in which weight is always a positive number. 30. Define Activity node graph. Activity node graphs represent a set of activities and scheduling constraints. Each node represents an activity (task), and an edge represents the next activity. 31. Define adjacency list. Adjacency list is an array indexed by vertex number containing linked lists. Each node Vi the ith array entry contains a list with information on all edges of G that leave Vi. It is used to represent the graph related problems. UNIT V ALGORITHM DESIGN AND ANALYSIS 1. Define an algorithm. The algorithm is defined as a collection of unambiguous instructions occurring in some specific sequence and such an algorithm should produce output for given set of input in finite amount of time. 2. What is greedy algorithm? In greedy method, the solution is constructed through a sequence of steps, each expanding a partially constructed solution obtained so far, until a complete solution to the problem is reached. At each step the choice made should be, Feasible – It should satisfy the problem’s constraints. Locally Optimal – Among all feasible solutions the best choice is to be made Irrevocable – Once the particular choice is made then it should not get changed on subsequent steps. 3. What are the applications of greedy method? a) Knapsack Problem. b) Prim’s algorithm c) Kruskal’s algorithm d) Finding shortest path e) Job sequencing with deadlines f) Optimal storage on tapes 4. Write general method of divide and conquer. In divide and conquer method, a given problem is, i.Divided into smaller sub problems. ii. These sub problems are solved independently. iii. Combining all the solutions of sub problems into a solution of the whole. If the sub problems are large enough then divide and conquer is reapplied. The generated sub problems are usually of same type as the original problem. A control abstraction for divide and conquer is as given below using control abstraction a flow of control of a procedure is given. 5. Define Dynamic Programming Dynamic Programming is typically applied to optimization problem. For each given problem, we may get any number of solutions from which we obtain for optimum solution (i.e. minimum value or maximum value solution.) And such an optimal solution becomes the solution to the given problem. 6. Comparison between divide and conquer and dynamic programming. Sl. No. Divide and conquer Dynamic programming 1. The problem is divided into small sub problems. These sub problems are solved independently. Finally all the solutions of sub problems are collected together to get the solution to the given problem. In dynamic programming many decision sequences are generated and all the overlapping sub instances are considered. 2. In this method duplications in sub solutions are neglected, i.e., duplicate In dynamic computing duplications in solutions is avoided totally. sub solutions may be obtained. 3. Divide and conquer is less efficient because of rework on solutions. Dynamic programming is efficient than divide and conquer strategy. 4. The divide and conquer uses top down approach of problem solving. Dynamic programming uses bottom up approach of problem solving. 5. Divide and conquer splits its input at specific deterministic points usually in the middle. Dynamic programming splits its input at every possible split points rather than at a particular point. After trying all split points it determines which split point is optimal. 7. Comparison between greedy algorithm and dynamic programming. Sl. No. Greedy Method Dynamic Programming 1. Greedy method is used for obtaining optimum solution. Dynamic programming is also for obtaining optimum solution. 2. In greedy method a set of feasible solutions and the picks up the optimum solution. There is no special set of feasible solutions in this method. 3. In greedy method optimum selection is without revising previously generated solutions. Dynamic programming considers all possible sequences in order to obtain the optimum solution. 4. In greedy method there is no as such guarantee of getting optimum solution. It is guaranteed that the dynamic programming will generate optimal solution using principle of optimality. 8. What are the steps of dynamic programming? Characterize the structure of optimal solution. That means develop a mathematical notation that can express any solution and sub solution for the given problem. Recursively define the value of an optimal solution. CS 2201 DATA STRUCTURES AND ALGORITHMS II CSE By using bottom up technique compute value of optimal solution. For that you have to develop a recurrence relation that relates a solution to its sub solutions, using the mathematical notation of step 1. Compute an optimal solution from computed information. 9. State the principle of backtracking. Backtracking is a method in which the desired solution is expressed as n tuple (x1, x2, x3….. xn)which is chosen from solution space, using backtrack formulation. The solution obtained i.e. (x1, x2, x3….. xn) can either minimizes or maximizes or satisfies the criteria function. 10. What is state space tree? A state space tree is a rooted tree whose nodes represent partially constructed solutions to given problem. In backtracking method the state space tree is built for finding the solution. This tree is built using depth first search fashion. 11. How to write an algorithm? Algorithm is basically a sequence of instructions written in simple English language. The algorithm is broadly divided into two sections. Algorithm heading It consists of name of algorithm, problem description, input and output. Algorithm body It consists of logical body of the algorithm by making use of various programming constructs and assignment statement. 12. What are the steps of algorithm design? 1. Understand the problem. 2. Decision making 25 CS 2201 DATA STRUCTURES AND ALGORITHMS II CSE a. Capabilities of computational devices b. Select exact/approximate method c. Data structures d. Algorithmic strategies 3. Design of algorithm 4. Algorithm verification 5. Analysis of an algorithm 6. Coding of algorithm 13. What are the types of asymptotic notation? a. Big oh notation. b. Omega notation c. Theta notation 14. Define Big oh notation? Let F(n) and g(n) be two non negative functions. Let n0 and constant c are two integers such that n0 denotes some value of input and n> n0 similarly c is some constant such that c>0. We can write F(n)<=c*g(n). then F(n) is big oh of g(n). It is also denoted as F(n)€O(g(n)). In other words F(n) is less than g(n) is multiple of some constant c. 15. Define Recurrence equation. The recurrence equation is an equation that defines a sequence recursively. It is normally in following form T(n) = T(n-1)+n …..1 for n>0 T(0) = 0 …..2 Here equation 1 is called recurrence relation and equation 2 is called initial condition. The recurrence equation can have infinite number of sequence. The general solution to the recursive function specifies some formula. 26 CS 2201 DATA STRUCTURES AND ALGORITHMS II CSE 16. Define solving recurrence equation. The recurrence relation can be solved by following methods a. Substitution method b. Master’s method 17. What is the general plan for mathematical analysis of non recursive algorithm? 1. Decide the input size based on parameter n. 2. Identify algorithm’s basic operation(s). 3. Check how many times the basic operation is executed. Then find whether the Execution of basic operation depends upon the input size n. Determine worst, average, and best cases for input of size n. If the basic operation depends upon worst case, average case, and best case then that has to be analyzed separately. 4. Set up a sum for the number of times the basic operation is executed. 5. Simplify the sum using standard formula and rules. 18. What is the general plan for mathematical analysis of non recursive algorithm? 1. Decide the input size based on parameter n. 2. Identify algorithm’s basic operation(s). 3. Check how many times the basic operation is executed. Then find whether the Execution of basic operation depends upon the input size n. Determine worst, average, and best cases for input of size n. If the basic operation depends upon worst case, average case, and best case then that has to be analyzed separately. 4. Set up the recurrence relation with some initial condition and expressing the basic operation. 5. Solve the recurrence relation. 19. Distinguish between backtracking and branch and bound techniques. Sl. No. Backtracking Branch and Bound 27 CS 2201 DATA STRUCTURES AND ALGORITHMS II CSE 1. Solution for backtracking is traced using depth first search. In this method, it is not necessary to use depth first search for obtaining the solution, even the breadth first search, best first search can be applied. 2. Typically decision problems can be solved using backtracking. Typically optimization problems can be solved using branch and bound. 3. While finding the solution to the problem bad choices can be made. It proceeds on better solutions. So there cannot be a bad solution. 4. The state space tree is searched until the solution is obtained. The state space tree needs to be searched completely as there may be chances of being an optimum solution any where in state space tree. 5. Applications of backtracking are M coloring, knapsack. Applications of branch and bound are job sequencing, TSP. 20. Define P and NP. Problems that can be solved in polynomial time” (“P” stands for polynomial). Eg. Searching of key element, sorting of elements, All pair shortest path. NP stands for “non deterministic polynomial time”. Note that NP does not stand for “non polynomial” Eg. Traveling salesman Problem, graph coloring problem, Knapsack problem, Hamiltonian circuit problem. 21. Two stages of non deterministic algorithm. a. Non deterministic (Guessing) stage  Generate an arbitrary string that can be thought of as a candidate solution. b. Deterministic (“Verification”) stage  In this stage it takes as input the candidate solution and the instance to the problem and returns yes if the candidate solution represents actual solution. 28