about ada viva qustions v t u in to the right box for getting free material and support from us/dedicated premium members...

---

about ada viva qustions v t u in to the right box for getting free material and support from us/dedicated premium members...

To get full information or details of ada viva qustions v t u please have a look on the pages

https://scribddoc/94502850/DAA-ADA-Viva-Questions

if you again feel trouble on ada viva qustions v t u please reply in that page and ask specific fields in ada viva qustions v t u

dhanya pls help me to get anasys vtu viva questions pls its urgent need to prepare now

  ada viva qustions v t u.pdf (Size: 361.83 KB / Downloads: 2)

1) What is the time complexity of linear search?
Θ(n)
2) What is the time complexity of binary search?
Θ(log2n)
3) What is the major requirement for binary search?
The given list should be sorted.
4) What is binary search?
It is an efficient method of finding out a required item from a given list,
provided the list is in order.
The process is:
1. First the middle item of the sorted list is found.
2. Compare the item with this element.
3. If they are equal search is complete.
4. If the middle element is greater than the item being searched, this process
is repeated in the upper half of the list.
5. If the middle element is lesser than the item being searched, this process is
repeated in the lower half of the list.
5) What is parental dominance?
The key at each node is greater than or equal to the keys at its children.
6) What is heap?
A heap can be defined as a binary tree with keys assigned to its nodes
( one key per node) provided the following two conditions are met:
1 The tree’s shape requirement – The binary tree is essentially complete ( or
simply complete), that is, all its levels are full except possibly the last level,
where only some rightmost leaves may be missing.
2. The parental dominance requirement – The key at each node is greater than
or equal to the keys at its children.


2
7) What is height of Binary tree?
It is the longest path from the root to any leaf.
8) What is the time complexity of heap sort?
Θ( n logn)
9) What is Merge Sort?
Merge sort is an O (n log n) comparison-based sorting algorithm.
Where the given array is divided into two equal parts. The left part of the array
as well as the right part of the array is sorted recursively. Later, both the left
part and right part are merged into a single sorted array.
10) Who invented Merge Sort?
John Von Neumann in 1945.
11) On which paradigm is it based?
Merge-sort is based on the divide-and-conquer paradigm.
12) What is the time complexity of merge sort?
n log n.
13) What is the space requirement of merge sort?
Space requirement: Θ(n) (not in-place).
14) When do you say an algorithm is stable and in place?
Stable – if it retains the relative ordering.
In – place if it does not use extra memory.
15 ) Name the design strategy used in Selection Sort.
Brute force
16) Define Brute force strategy.
Brute force is a straight forward approach to solving a problem, usually
directly based on the problem’s statement and definitions of the concepts
involved.
3
17) What is the time complexity of Selection Sort algorithm?
 (n2
)
18) Is Selection Sort Inplace?
Yes.
19) Is Selection Sort stable?
Yes.
20) Why is the name Selection Sort?
Algorithm selects the smallest number in the array and places it in its final
position the sorted array

Viva Questions

1) What is the time complexity of linear search? Θ(n) 2) What is the time complexity of binary search? Θ(log2n) 3) What is the major requirement for binary search? The given list should be sorted. 4) What is binary search? It is an efficient method of finding out a required item from a given list, provided the list is in order. The process is: 1. 2. 3. 4. First the middle item of the sorted list is found. Compare the item with this element. If they are equal search is complete. If the middle element is greater than the item being searched, this process

is repeated in the upper half of the list. 5. If the middle element is lesser than the item being searched, this process is

repeated in the lower half of the list. 5) What is parental dominance? The key at each node is greater than or equal to the keys at its children. 6) What is heap?

A heap can be defined as a binary tree with keys assigned to its nodes ( one key per node) provided the following two conditions are met: 1 The tree’s shape requirement – The binary tree is essentially complete ( or simply complete), that is, all its levels are full except possibly the last level, where only some rightmost leaves may be missing. 2. The parental dominance requirement – The key at each node is greater than or equal to the keys at its children. MCA | Collections:

1

7) What is height of Binary tree? It is the longest path from the root to any leaf. In – place if it does not use extra memory.html . Brute force 16) Define Brute force strategy.blogspot. MCA | Collections: . Where the given array is divided into two equal parts. 14) When do you say an algorithm is stable and in place? Stable – if it retains the relative ordering. The left part of the array as well as the right part of the array is sorted recursively. 15 ) Name the design strategy used in Selection Sort. 12) What is the time complexity of merge sort? n log n. 8) What is the time complexity of heap sort? Θ( n logn) 9) What is Merge Sort? Merge sort is an O (n log n) comparison-based sorting algorithm. both the left part and right part are merged into a single sorted array. 13) What is the space requirement of merge sort? Space requirement: Θ(n) (not in-place). 10) Who invented Merge Sort? John Von Neumann in 1945. Later. usually directly based on the problem’s statement and definitions of the concepts involved. 11) On which paradigm is it based? Merge-sort is based on the divide-and-conquer paradigm. 2 Brute force is a straight forward approach to solving a problem.

means it would require the entire array to be in main memory. 22) What are the drawbacks of Selection Sort? Inefficient on large lists.blogspot. 20) Why is the name Selection Sort? Algorithm selects the smallest number in the array and places it in its final position the sorted array.html 3 . 23) When is a problem said to have overlapping sub problems? A problem is said to have overlapping subproblems if it can be broken down into subproblems which are reused multiple times. This is closely related to recursion. 21) When is Selection Sort algorithm useful? Selection Sort algorithm is useful for small inputs because it requires (n ) comparisons. 24) What is principle of optimality? The optimal solution to any instance of an optimization problem is composed of optimal solutions to its subinstances. 2 Selection Sort algorithm requires (n-1) swaps & hence  (n) memory writes. It uses internal sorting. 25) Can knapsack problem be solved in any other technique? MCA | Collections: . Thus it can be very useful if writes are the most expensive operation. It requires same number of iterations no matter how well-organized the array is. 19) Is Selection Sort stable? Yes.17) What is the time complexity of Selection Sort algorithm?  (n2) 18) Is Selection Sort Inplace? Yesp/mca-study-materials.

in/p/mca-study-materials. To find the longest common substrings of the strings "ABAB". "BABA" and "ABBA" are the strings "AB" and "BA" of length 2. 30) Which technique the Dijkstra’s algorithm is based on? Greedy Technique.blogspot..e. 27) Compare Dynamic programming and Divide and conquer. new subproblems may be generated when the method is applied. 31) What is the purpose of Dijkstra’s Algorithm? To find the shortest path from source vertex to all other remaining vertices 32) Name the different algorithms based on Greedy technique. "B" and the empty string “”. Both use recursion. 28) Who invented Dijkstra’s Algorithm? Edsger Dijkstra invented this algorithm.html . 35) What is a Connected Graph? MCA | Collections: . These numbers are called weights or costs.i. 26) Mention few applications of dynamic programming.. Other common substrings are "A". Prim’s Algorithm. fibonacci numbers in which the required value may depend on previously computed values. 29) What is the other name for Dijkstra’s Algorithm? Single Source Shortest Path Algorithm. Can be applied to find factorial. Branch and bound etc.It can be solved using many other techniques such as BruteForce. 34) What is a Weighted Graph? 4 A weighted graph is a graph with numbers assigned to its edges. Kruskal’s algorithm 33) What is the constraint on Dijkstra’s Algorithm? This algorithm is applicable to graphs with non-negative weights only. etc. Greedy technique. Dynamic programming differs from the "Divide and Conquer" (D-and-C) method in the fact that the problems solved by D-and-C can have many nonoverlapping subproblems .

in/p/mca-study-materials. 41) Which design strategy does Quicksort uses? Divide and Conquer 42) What is Divide and Conquer Technique? 5 (I) Divide the instance of a problem into two or more smaller instances (II) Solve the smaller instances recursively (III) Obtain solution to original instances by combining MCA | Collections: . 36) What is the time complexity of Dijkstra’s algorithm? For adjacency matrix. find the shortest path from source vertex to all other remaining vertices 38) Differentiate b/w Prim’s Algorithm and Dijkstra’s Algorithm? Prim’s algorithm is to find minimum cost spanning tree.blogspot.HOARE. 39) What are the applications of Dijkstra’s Algorithm? It finds its application even in our day to day life while travelling. 40) Who was the inventor of the Quicksort? C. it is O(IEIlogIVI) 37) Differentiate b/w Traveling Salesman Problem(TSP) and Dijkstra’s Algorithm. They are helpful in routing applications.A graph is said to be connected if for every pair of its vertices u and v there is a path from u to v.A. a British Scientist. In Dijkstra’s Algorithm. It is O(IVI*IVI) For adjacency list with edges stored as min heap. find the shortest tour that passes through all the cities exactly once before returning to the starting city. In TSP. Dijkstra’s algorithm is to find the shortest path from source vertex to all other remaining vertices.html . given n cities with known distances b/w each pair .R.

these solutions 43) What is the another name for Quicksort? Partition Exchange Sort 44) What are the advantages and disadvantages? Advantage: Fastest among all sorting algorithms Suitable when the input size is very large Disadvantage: Heavily based on recursive sorting technique It takes O (n* log n) time and O (log n) additional space due to Recursion 45)Is Quicksort Stable as well as In place? Not Stable but In place.H header file.html . 6 51) What technique does kruskal’s algorithm follow.blogspot. greedy technique MCA | Collections: . 50) What is CLK_TCK? macro defines the number of clock ticks per second which is available in the TIME. 46) When do you say that a Quick sort having best case complexity? When the pivot exactly divides the array into equal half 47) When do you say that Quick sort having worst case complexity? When any one of the subarray is empty 48) How many more comparisons are needed for average case compared to best case? 38% more 49) when do you say that the pivot element is in its final position? When all the elements towards the left of pivot are <= pivot and all the elements towards the right of pivot are >= pivotp/mca-study-materials.

Is encountered. With an efficient sorting algorithm. it is attached as a child to the vertex from which it is being visited.52) What is the time complexity. the time efficiency of an kruskal’s algorithm will be in O(|E|log|E|). Back edge: An edge leading to a previously visited vertex other than its immediate predecessor. 54) Which technique is used to solve BFS & DFS problems? Decrease and Conquer 55) What is BFS traversal? It proceeds in a concentric manner by visiting first all the vertices that are adjacent to a starting vertex. If there still remains unvisited vertices. Back edge & Cross edge ? Tree edge: whenever a new unvisited vertex is reached for the first time.html 7 . This process continues until dead end is encountered. 56) What is DFS traversal? Consider an arbitrary vertex v and mark it as visited on each iteration. the algorithm to be restarted at an arbitrary vertex of another connected component of a graphp/mca-study-materials.blogspot. 57) What are Tree edge. its parent in the tree). At the dead end the algorithm backs up by one edge and continues the process of visiting unvisited vertices. 53) Who is the inventor of kruskal’s algorithm. Such an edge is called a tree edge.e. Joseph Kruskal. we can explore this new vertex depending upon its adjacent information. This process continues until we reach the starting vertex. the edge is noted as a cross edge. 58) What are the various applications of BFS & DFS tree traversal technique? MCA | Collections: . until all the vertices are in the same connected component as the starting vertex are visited. Such an edge is called a back edge Cross edge If an edge leading to a previously visited vertex other than its immediate predecessor (i. proceed to an unvisited vertex w adjacent to v.(no adjacent unvisited vertex is available). then all unvisited vertices two edges apart from it and so on .

if the latter vertex does not have cross edge.n-1) MCA | Collections: . we can take advantage of the graph's representation in the form of a BFS forest. then it is connected graph otherwise disconnected graph.…. 62) Define power set? The set of all subsets of a set is a power set. For checking cycle presence.2. 59) Which data structures are used in BFS & DFS tree traversal technique? We use Stack data structure to traverse the graph in DFS traversal. 60) What are the efficiencies of BFS & DFS algorithms for Adjacency matrix and adjacency list representation? Adjacency matrices: Θ(V2) Adjacency linked lists: Θ(V+E) 61) Define set? Set is unordered collection of distinct items.aj-1(j=1. We use queue data structure to traverse the graph in DFS traversal.Application of BFS Checking connectivity and checking acyclicity of a graph.html . To check whether the graph is cyclic or not.…. then the graph is acyclic. If there is only one root in the BFS forest.blogspot. Topological sorting. Check whether there is only one root in the BFS forest or not. To find the spanning tree. 8 63) Define squashed order? Any subsets involving aj can be listed only after all the subsets involving a1. Application of DFS To check whether given graph is connected or not.

html . It is a technique in which the problem’s input is preprocessed in whole or in part and the additional information stored is obtained to solve the problem. a) In brute-force. 66) Which technique does the Horspool algorithm uses? Input enhancement technique 67) Explain Input enhancement technique. if there is a character mismatch then we shift the pattern to the right by 1 position.64) What are the ways of generating subsets? Decrease by constant Bit string based algorithm Minimal change algorithm 65) Explain time and space trade off strategy. 68) What is a shift table? It is a table that stores the shift information i. In Horspool. b) In brute-force technique.blogspot. It is a strategy in which time efficiency can be achieved at the cost of extra memory usage. if there is a mismatch then the shift size is obtained from the shift table and the pattern is shifted accordingly. 71) Differentiate between Horspool and Boyer -Moore algorithms. 69) Which is better Brute Force or Horspool algorithm for string matching? Horspool is better as it reduces the number of comparisons. comparison starts from left where as in Horspool comparison starts from rightp/mca-study-materials. 9 MCA | Collections: . 70) Differentiate between Brute-Force technique and Horspool algorithm for string matching.e it stores the distance of each rightmost character in the first “m-1” characters of the pattern from the last character of the pattern and stores the length of the pattern as the shift size if the character is not present in the pattern.

in/p/mca-study-materials. the solution is retrieved from the table and never recomputed. the solutions for larger instance of the problem can be obtained. Shifting is done by taking max(d1. If the same instance of sub problem is encountered. 74) What is the Space & Time complexity of DP algo for Binomial Coefficient C(n.d2).Moore algorithm uses 2 tables. a tree)that contains all the vertices of a graph.html . Very precisely re . 72) What is Dynamic Programming? It is a technique for solving problems with overlapping sub problems. Using the solutions of sub problems. -Bad symbol shift table (same as the shift table used by Horspool). k)? Θ(nk) 75) What is a principle difference between the two techniques? Only one instance of the sub problem is computed & stored.Horspool algorithm uses only Shift table to obtain the shift information.blogspot. 76) What is a spanning tree ? A spanning tree of a weighted connected graph is its connected acyclic(no cycles) subgraph (i.The shift information of this table is known as d1 -Good suffix shift table The shift information from this table is known as d2. 73) What does Dynamic Programming have in common with Divideand-Conquer? Both solve the problems by dividing the problem into sub problems.computations are not preformed.e. Boyer . 10 77) What is a minimum spanning tree ? MCA | Collections: .

What are fringes and unseen vertices? Fringes: vertices which are connected are called fringes.e. Greedy technique. it has to satisfy the problem’s constraints. then we take into the account of cost factor for communication links.html . it cannot be changed on subsequent steps of the algorithm.blogspot. 80) Name some of the application greedy technique They are helpful in routing applications: In the case of network where large number of computers are connected. On each step the choice must be made as Feasible: i. Irrevocable: i. Communication Networks: Suppose there are 5 different cities and we want to establish computer connectivity among them.e. Building a road network that joins n cities with minimum cost. once made. to pass the data from one node to another node we can find the shortest distance easily by this algorithm. 11 81) Does Prim’s Algorithm always yield a minimum spanning tree ? Yes MCA | Collections: . Unseen vertices : vertices which are not adjacent are called unseen. A greedy approach constructs a problem through a sequence of steps each expanding a partially constructed solution obtained so far. Locally optimal: i.e. 78) Prim’s algorithm is based on which technique. 79) State greedy technique for solving problem. it has to be the best local choice among all feasible choices available on that step. untill the complete solution is reached.Minimum spanning tree of a connected graph is its spanning tree of smallest weight.

91) hard problems can be solved by which method? Back tracking and branch and bound techniques used for large instance of combinatorial problems. 85) What is shortest path? .It is the path which is having shortest length among all possible paths.In which the element dij indicates the length of the path from ith vertex to the jth vertex.To find the all pair shortest path. MCA | Collections: .It is same as warshall’s algorithm that is θ(n3). 83) What is the time efficiency of floyd’s algorithm? . 12 92) what is state space tree? Constructing a tree of choices being made and processing is known as state-spacetree. 84) What is distance matrix? .82) What is the purose of Floyd’s algoreithm? . Root represents an initial state before the search for solution beginsp/mca-study-materials. 86) warshall’s algorithm is optimization problem or non-optimization problem ? Non-optimization problem 87) For what purpose we use Warshall’s algorithm? Warshall’s algorithm for computing the transitive closure of a directed graph 88) Warshall’s algorithm depends on which property? Transitive property 89) what is the time complexity of Warshall’s algorithm? Time complexity of warshall’s algorithm is (n3) 90) what is hard problem? Optimization problems which are having complexity of exponential or factorial.

94) Differentiate between backtracking and Branch and Bound. 13 MCA | Collections: .html . It uses DFS search technique. Node which doesn’t leads to solution is called non-promising. 95) In Backtracking what does the leaf node indicates? It indicates either a non promising dead ends or solutions to the problem.blogspot. Backtracking is applicable to non-optimization problems most of the times and sometimes optimization problems.93) what are promising and non-promising state-space-tree? Node which may leads to solution is called promising. Branch and Bound uses Best first search technique and is applicable to optimization problemsp/mca-study-materials.

Viva Questions

1) What is the time complexity of linear search? Θ(n) 2) What is the time complexity of binary search? Θ(log2n) 3) What is the major requirement for binary search? The given list should be sorted. 4) What is binary search? It is an efficient method of finding out a required item from a given list, provided the list is in order. The process is: 1. 2. 3. 4. First the middle item of the sorted list is found. Compare the item with this element. If they are equal search is complete. If the middle element is greater than the item being searched, this process

is repeated in the upper half of the list. 5. If the middle element is lesser than the item being searched, this process is

repeated in the lower half of the list. 5) What is parental dominance? The key at each node is greater than or equal to the keys at its children. 6) What is heap?

A heap can be defined as a binary tree with keys assigned to its nodes ( one key per node) provided the following two conditions are met: 1 The tree’s shape requirement – The binary tree is essentially complete ( or simply complete), that is, all its levels are full except possibly the last level, where only some rightmost leaves may be missing. 2. The parental dominance requirement – The key at each node is greater than or equal to the keys at its children. MCA | Collections:

1

7) What is height of Binary tree? It is the longest path from the root to any leaf. In – place if it does not use extra memory.html . Brute force 16) Define Brute force strategy.blogspot. MCA | Collections: . Where the given array is divided into two equal parts. 14) When do you say an algorithm is stable and in place? Stable – if it retains the relative ordering. The left part of the array as well as the right part of the array is sorted recursively. 15 ) Name the design strategy used in Selection Sort. 12) What is the time complexity of merge sort? n log n. 8) What is the time complexity of heap sort? Θ( n logn) 9) What is Merge Sort? Merge sort is an O (n log n) comparison-based sorting algorithm. both the left part and right part are merged into a single sorted array. 13) What is the space requirement of merge sort? Space requirement: Θ(n) (not in-place). 10) Who invented Merge Sort? John Von Neumann in 1945. Later. usually directly based on the problem’s statement and definitions of the concepts involved. 11) On which paradigm is it based? Merge-sort is based on the divide-and-conquer paradigm. 2 Brute force is a straight forward approach to solving a problem.

means it would require the entire array to be in main memory. 22) What are the drawbacks of Selection Sort? Inefficient on large lists.blogspot. 20) Why is the name Selection Sort? Algorithm selects the smallest number in the array and places it in its final position the sorted array.html 3 . 23) When is a problem said to have overlapping sub problems? A problem is said to have overlapping subproblems if it can be broken down into subproblems which are reused multiple times. This is closely related to recursion. 21) When is Selection Sort algorithm useful? Selection Sort algorithm is useful for small inputs because it requires (n ) comparisons. 24) What is principle of optimality? The optimal solution to any instance of an optimization problem is composed of optimal solutions to its subinstances. 2 Selection Sort algorithm requires (n-1) swaps & hence  (n) memory writes. It uses internal sorting. 25) Can knapsack problem be solved in any other technique? MCA | Collections: . Thus it can be very useful if writes are the most expensive operation. It requires same number of iterations no matter how well-organized the array is. 19) Is Selection Sort stable? Yes.17) What is the time complexity of Selection Sort algorithm?  (n2) 18) Is Selection Sort Inplace? Yesp/mca-study-materials.

in/p/mca-study-materials. To find the longest common substrings of the strings "ABAB". "BABA" and "ABBA" are the strings "AB" and "BA" of length 2. 30) Which technique the Dijkstra’s algorithm is based on? Greedy Technique.blogspot..e. 27) Compare Dynamic programming and Divide and conquer. new subproblems may be generated when the method is applied. 31) What is the purpose of Dijkstra’s Algorithm? To find the shortest path from source vertex to all other remaining vertices 32) Name the different algorithms based on Greedy technique. "B" and the empty string “”. Both use recursion. 28) Who invented Dijkstra’s Algorithm? Edsger Dijkstra invented this algorithm.html . 35) What is a Connected Graph? MCA | Collections: . These numbers are called weights or costs.i. 26) Mention few applications of dynamic programming.. Other common substrings are "A". Prim’s Algorithm. fibonacci numbers in which the required value may depend on previously computed values. 29) What is the other name for Dijkstra’s Algorithm? Single Source Shortest Path Algorithm. Can be applied to find factorial. Branch and bound etc.It can be solved using many other techniques such as BruteForce. 34) What is a Weighted Graph? 4 A weighted graph is a graph with numbers assigned to its edges. Kruskal’s algorithm 33) What is the constraint on Dijkstra’s Algorithm? This algorithm is applicable to graphs with non-negative weights only. etc. Greedy technique. Dynamic programming differs from the "Divide and Conquer" (D-and-C) method in the fact that the problems solved by D-and-C can have many nonoverlapping subproblems .

in/p/mca-study-materials. 41) Which design strategy does Quicksort uses? Divide and Conquer 42) What is Divide and Conquer Technique? 5 (I) Divide the instance of a problem into two or more smaller instances (II) Solve the smaller instances recursively (III) Obtain solution to original instances by combining MCA | Collections: . 36) What is the time complexity of Dijkstra’s algorithm? For adjacency matrix. find the shortest path from source vertex to all other remaining vertices 38) Differentiate b/w Prim’s Algorithm and Dijkstra’s Algorithm? Prim’s algorithm is to find minimum cost spanning tree.blogspot.HOARE. 39) What are the applications of Dijkstra’s Algorithm? It finds its application even in our day to day life while travelling. 40) Who was the inventor of the Quicksort? C. it is O(IEIlogIVI) 37) Differentiate b/w Traveling Salesman Problem(TSP) and Dijkstra’s Algorithm. They are helpful in routing applications.A graph is said to be connected if for every pair of its vertices u and v there is a path from u to v.A. a British Scientist. In Dijkstra’s Algorithm. It is O(IVI*IVI) For adjacency list with edges stored as min heap. find the shortest tour that passes through all the cities exactly once before returning to the starting city. In TSP. Dijkstra’s algorithm is to find the shortest path from source vertex to all other remaining vertices.html . given n cities with known distances b/w each pair .R.

these solutions 43) What is the another name for Quicksort? Partition Exchange Sort 44) What are the advantages and disadvantages? Advantage: Fastest among all sorting algorithms Suitable when the input size is very large Disadvantage: Heavily based on recursive sorting technique It takes O (n* log n) time and O (log n) additional space due to Recursion 45)Is Quicksort Stable as well as In place? Not Stable but In place.H header file.html . 6 51) What technique does kruskal’s algorithm follow.blogspot. greedy technique MCA | Collections: . 50) What is CLK_TCK? macro defines the number of clock ticks per second which is available in the TIME. 46) When do you say that a Quick sort having best case complexity? When the pivot exactly divides the array into equal half 47) When do you say that Quick sort having worst case complexity? When any one of the subarray is empty 48) How many more comparisons are needed for average case compared to best case? 38% more 49) when do you say that the pivot element is in its final position? When all the elements towards the left of pivot are <= pivot and all the elements towards the right of pivot are >= pivotp/mca-study-materials.

Is encountered. With an efficient sorting algorithm. it is attached as a child to the vertex from which it is being visited.52) What is the time complexity. the time efficiency of an kruskal’s algorithm will be in O(|E|log|E|). Back edge: An edge leading to a previously visited vertex other than its immediate predecessor. 54) Which technique is used to solve BFS & DFS problems? Decrease and Conquer 55) What is BFS traversal? It proceeds in a concentric manner by visiting first all the vertices that are adjacent to a starting vertex. If there still remains unvisited vertices. Back edge & Cross edge ? Tree edge: whenever a new unvisited vertex is reached for the first time.html 7 . This process continues until dead end is encountered. 56) What is DFS traversal? Consider an arbitrary vertex v and mark it as visited on each iteration. the algorithm to be restarted at an arbitrary vertex of another connected component of a graphp/mca-study-materials.blogspot. 57) What are Tree edge. its parent in the tree). At the dead end the algorithm backs up by one edge and continues the process of visiting unvisited vertices. 53) Who is the inventor of kruskal’s algorithm. Such an edge is called a tree edge.e. Joseph Kruskal. we can explore this new vertex depending upon its adjacent information. This process continues until we reach the starting vertex. the edge is noted as a cross edge. 58) What are the various applications of BFS & DFS tree traversal technique? MCA | Collections: . until all the vertices are in the same connected component as the starting vertex are visited. Such an edge is called a back edge Cross edge If an edge leading to a previously visited vertex other than its immediate predecessor (i. proceed to an unvisited vertex w adjacent to v.(no adjacent unvisited vertex is available). then all unvisited vertices two edges apart from it and so on .

if the latter vertex does not have cross edge.n-1) MCA | Collections: . we can take advantage of the graph's representation in the form of a BFS forest. then it is connected graph otherwise disconnected graph.…. 62) Define power set? The set of all subsets of a set is a power set. For checking cycle presence.2. 59) Which data structures are used in BFS & DFS tree traversal technique? We use Stack data structure to traverse the graph in DFS traversal. 60) What are the efficiencies of BFS & DFS algorithms for Adjacency matrix and adjacency list representation? Adjacency matrices: Θ(V2) Adjacency linked lists: Θ(V+E) 61) Define set? Set is unordered collection of distinct items.aj-1(j=1. We use queue data structure to traverse the graph in DFS traversal.Application of BFS Checking connectivity and checking acyclicity of a graph.html . To check whether the graph is cyclic or not.…. then the graph is acyclic. If there is only one root in the BFS forest.blogspot. Topological sorting. Check whether there is only one root in the BFS forest or not. To find the spanning tree. 8 63) Define squashed order? Any subsets involving aj can be listed only after all the subsets involving a1. Application of DFS To check whether given graph is connected or not.

html . It is a technique in which the problem’s input is preprocessed in whole or in part and the additional information stored is obtained to solve the problem. a) In brute-force. 66) Which technique does the Horspool algorithm uses? Input enhancement technique 67) Explain Input enhancement technique. if there is a character mismatch then we shift the pattern to the right by 1 position.64) What are the ways of generating subsets? Decrease by constant Bit string based algorithm Minimal change algorithm 65) Explain time and space trade off strategy. 68) What is a shift table? It is a table that stores the shift information i. In Horspool. b) In brute-force technique.blogspot. It is a strategy in which time efficiency can be achieved at the cost of extra memory usage. if there is a mismatch then the shift size is obtained from the shift table and the pattern is shifted accordingly. 71) Differentiate between Horspool and Boyer -Moore algorithms. 69) Which is better Brute Force or Horspool algorithm for string matching? Horspool is better as it reduces the number of comparisons. comparison starts from left where as in Horspool comparison starts from rightp/mca-study-materials. 9 MCA | Collections: . 70) Differentiate between Brute-Force technique and Horspool algorithm for string matching.e it stores the distance of each rightmost character in the first “m-1” characters of the pattern from the last character of the pattern and stores the length of the pattern as the shift size if the character is not present in the pattern.

in/p/mca-study-materials. the solution is retrieved from the table and never recomputed. the solutions for larger instance of the problem can be obtained. Shifting is done by taking max(d1. If the same instance of sub problem is encountered. 74) What is the Space & Time complexity of DP algo for Binomial Coefficient C(n.d2).Moore algorithm uses 2 tables. a tree)that contains all the vertices of a graph.html . Very precisely re . 72) What is Dynamic Programming? It is a technique for solving problems with overlapping sub problems. Using the solutions of sub problems. -Bad symbol shift table (same as the shift table used by Horspool). k)? Θ(nk) 75) What is a principle difference between the two techniques? Only one instance of the sub problem is computed & stored.Horspool algorithm uses only Shift table to obtain the shift information.blogspot. 76) What is a spanning tree ? A spanning tree of a weighted connected graph is its connected acyclic(no cycles) subgraph (i.The shift information of this table is known as d1 -Good suffix shift table The shift information from this table is known as d2. 73) What does Dynamic Programming have in common with Divideand-Conquer? Both solve the problems by dividing the problem into sub problems.computations are not preformed.e. Boyer . 10 77) What is a minimum spanning tree ? MCA | Collections: .

What are fringes and unseen vertices? Fringes: vertices which are connected are called fringes.e. Greedy technique. it has to satisfy the problem’s constraints. then we take into the account of cost factor for communication links.html . it cannot be changed on subsequent steps of the algorithm.blogspot. 80) Name some of the application greedy technique They are helpful in routing applications: In the case of network where large number of computers are connected. On each step the choice must be made as Feasible: i. Irrevocable: i. Communication Networks: Suppose there are 5 different cities and we want to establish computer connectivity among them.e. Building a road network that joins n cities with minimum cost. once made. to pass the data from one node to another node we can find the shortest distance easily by this algorithm. 11 81) Does Prim’s Algorithm always yield a minimum spanning tree ? Yes MCA | Collections: . Unseen vertices : vertices which are not adjacent are called unseen. A greedy approach constructs a problem through a sequence of steps each expanding a partially constructed solution obtained so far. Locally optimal: i.e. 78) Prim’s algorithm is based on which technique. 79) State greedy technique for solving problem. it has to be the best local choice among all feasible choices available on that step. untill the complete solution is reached.Minimum spanning tree of a connected graph is its spanning tree of smallest weight.

91) hard problems can be solved by which method? Back tracking and branch and bound techniques used for large instance of combinatorial problems. 85) What is shortest path? .It is the path which is having shortest length among all possible paths.In which the element dij indicates the length of the path from ith vertex to the jth vertex.To find the all pair shortest path. MCA | Collections: .It is same as warshall’s algorithm that is θ(n3). 83) What is the time efficiency of floyd’s algorithm? . 12 92) what is state space tree? Constructing a tree of choices being made and processing is known as state-spacetree. 84) What is distance matrix? .82) What is the purose of Floyd’s algoreithm? . Root represents an initial state before the search for solution beginsp/mca-study-materials. 86) warshall’s algorithm is optimization problem or non-optimization problem ? Non-optimization problem 87) For what purpose we use Warshall’s algorithm? Warshall’s algorithm for computing the transitive closure of a directed graph 88) Warshall’s algorithm depends on which property? Transitive property 89) what is the time complexity of Warshall’s algorithm? Time complexity of warshall’s algorithm is (n3) 90) what is hard problem? Optimization problems which are having complexity of exponential or factorial.

94) Differentiate between backtracking and Branch and Bound. 13 It uses DFS search technique. Node which doesn’t leads to solution is called non-promising. 95) In Backtracking what does the leaf node indicates? It indicates either a non promising dead ends or solutions to the problem.blogspot. Backtracking is applicable to non-optimization problems most of the times and sometimes optimization problems.93) what are promising and non-promising state-space-tree? Node which may leads to solution is called promising. Branch and Bound uses Best first search technique and is applicable to optimization problemsp/mca-study-materials.