daa viva question

 1. What is an algorithm? 

An algorithm is a sequence of unambiguous instructions for solving a problem. i.e., for  obtaining a required output for any legitimate input in a finite amount of time  

2. What are important problem types? (or) Enumerate some important types of problems.  1. Sorting 2. Searching  

3. Numerical problems 4. Geometric problems  

5. Combinatorial Problems 6. Graph Problems  

7. String processing Problems  

3. Name some basic Efficiency classes  

1. Constant 2. Logarithmic 3. Linear 4. nlogn  

5. Quadratic 6. Cubic 7. Exponential 8. Factorial  

4. What are algorithm design techniques?  

Algorithm design techniques ( or strategies or paradigms) are general approaches to solving  problems algorithmatically, applicable to a variety of problems from different areas of  computing. General design techniques are:  

(i) Brute force (ii) divide and conquer  

(iii) decrease and conquer (iv) transform and concquer  

(v) greedy technique (vi) dynamic programming  

(vii) backtracking (viii) branch and bound  

5. How is an algorithm’s time efficiency measured?  

Time efficiency indicates how fast the algorithm runs. An algorithm’s time efficiency is  measured as a function of its input size by counting the number of times its basic operation

(running time) is executed. Basic operation is the most time consuming operation in the  algorithm’s innermost loop.  

6. How is the efficiency of the algorithm defined?  

The efficiency of an algorithm is defined with the components.  

(i) Time efficiency -indicates how fast the algorithm runs  

(ii) Space efficiency -indicates how much extra memory the algorithm needs  

7. What are the characteristics of an algorithm?  

Every algorithm should have the following five characteristics  

(i) Input  

(ii) Output  

(iii) Definiteness  

(iv) Effectiveness  

(v) Termination  

Therefore, an algorithm can be defined as a sequence of definite and effective instructions, which  terminates with the production of correct output from the given input.  

8. Write general plan for analyzing non-recursive algorithms.  

i. Decide on parameter indicating an input’s size.  

ii. Identify the algorithm’s basic operation  

iii. Checking the no.of times basic operation executed depends on size of input.  iv. Set up sum expressing the no.of times the basic operation is executed. depends on some  additional property,then best,worst,avg.cases need to be investigated (establishing order of  growth)  

9. Define the terms: pseudocode, flow chart  

A pseudocode is a mixture of a natural language and programming language like constructs. A  pseudocode is usually more precise than natural language. A flowchart is a 

method of expressing an algorithm by a collection of connected geometric shapes containing  descriptions of the algorithm’s steps.  

10. write general plan for analyzing recursive algorithms.  

i. Decide on parameter indicating an input’s size.  

ii. Identify the algorithm’s basic operation  

iii. Checking the no.of times basic operation executed depends on size of input.if it depends on  some additional property,then best,worst,avg.cases need to be investigated of times the basic operation is executed  

iv. Set up the recurrence relation,with an appropriate initial condition,for the number  v. Solve recurrence (establishing order of growth)  

11. Define the divide an conquer method.  

Given a function to compute on ‘n’ inputs the divide-and-comquer strategy suggests splitting the  inputs in to’k’ distinct susbsets, 1<k <n, yielding ‘k’ subproblems. The subproblems must be  solved recursively, and then a method must be found to combine subsolutions into a solution of  the whole.  

12. What is Merge sort?  

Merge sort is divide and conquer strategy that works by dividing an input array in to  two halves,sorting them recursively and then merging the two sorted halves to get the  original array sorted  

13. What is general divide and conquer recurrence?  

 Time efficiency T(n)of many divide and conquer algorithms satisfies the equation  T(n)=a.T(n/b)+f(n).This is the general recurrence relation.  

14. Describe the recurrence relation for merge sort?  

If the time for the merging operation is proportional to n, then the computing time of  merge sort is described by the recurrence relation   

T(n) = a n = 1, a a constant 

2T (n/2) + n n >1, c a constant 

15. The relation between order of growth of functions 

O(1) < O(log n) < O(n) < O(n * log n) < O(n2) < O(n3) < O(2n) 

16. Asymptotic notations 

Big Oh(Worst Case), Big Theta (Average Case), Big Omega(Best Case) 

GREEDY METHOD  

1. Explain the greedy method.  

Greedy method is the most important design technique, which makes a choice that looks best at  that moment. A given ‘n’ inputs are required us to obtain a subset that satisfies some constraints  that is the feasible solution. A greedy method suggests that one candevice an algorithm that  works in stages considering one input at a time.  

2. Define feasible and optimal solution.  

Given n inputs and we are required to form a subset such that it satisfies some given constraints  then such a subset is called feasible solution.  

A feasible solution either maximizes or minimizes the given objective function is called as  optimal solution  

3. What are the constraints of knapsack problem?  

To maximize ∑pixi  

The constraint is : ∑wixi ≥ m and 0 ≤ xi ≤ 1 1≤ i ≤ n 

where m is the bag capacity, n is the number of objects and for each object i wi  and pi are the weight and profit of object respectively.  

4. Specify the algorithms used for constructing Minimum cost spanning tree.  a) Prim’s Algorithm  

b) Kruskal’s Algorithm  

5. State single source shortest path algorithm (Dijkstra’s algorithm).  

For a given vertex called the source in a weigted connected graph,find shotrtest paths to all its  other vertices.Dijikstra’s algorithm applies to graph with non-negative weights only.  

6. State efficiency of prim’s algorithm.  

O(|v|2) (WEIGHT MATRIX AND PRIORITY QUEUE AS UNORDERED ARRAY)  O(|E| LOG|V|) (ADJACENCY LIST AND PRIORITY QUEUE AS MIN-HEAP)  

7. State Kruskal Algorithm.  

The algorithm looks at a MST for a weighted connected graph as an acyclic subgraph with |v|-1  edges for which the sum of edge weights is the smallest.  

8. State efficiency of Dijkstra’s algorithm.  

O(|v|2) (WEIGHT MATRIX AND PRIORITY QUEUE AS UNORDERED ARRAY) 

O(|E| LOG|V|) (ADJACENCY LIST AND PRIORITY QUEUE AS MIN-HEAP)  

DYNAMIC PROGRAMMING 

1. Define multistage graph 

A multistage graph G =(V,E) is a directed graph in which the vertices are partitioned into K>=2  disjoint sets Vi,1<=i<=k.The multi stage graph problem is to find a minimum  cost paths from s(source ) to t(sink)  

Two approach(forward and backward)  

2. Define All pair shortest path problem  

Given a weighted connected graph, all pair shortest path problem asks to find the lengths of  shortest paths from each vertex to all other vertices.  

3.Define floyd’s algorithm  

To find all pair shortest path  

4. State the time efficiency of floyd’s algorithm  

O(n3)  

It is cubic  

***************************SET II***************************

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 

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 sorted part and right sorted 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) Who invented Dijkstra’s Algorithm? 

Edsger Dijkstra invented this algorithm. 

16) What is the other name for Dijkstra’s Algorithm? 

Single Source Shortest Path Algorithm. 

17) Which technique the Dijkstra’s algorithm is based on? 

Greedy Technique. 

18) What is the purpose of Dijkstra’s Algorithm? 

To find the shortest path from source vertex to all other remaining vertices 19) Name the different algorithms based on Greedy technique. 

Prim’s Algorithm, Kruskal’s algorithm 

20) What is the constraint on Dijkstra’s Algorithm? 

This algorithm is applicable to graphs with non-negative weights only. 

21) What is a Weighted Graph? 

A weighted graph is a graph with numbers assigned to its edges. These numbers are called  weights or costs. 

22) What is a Connected Graph? 

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. 23) What is the time complexity of Dijkstra’s algorithm? 

For adjacency matrix, It is O(IVI*IVI) 

For adjacency list with edges stored as min heap, it is O(IEIlogIVI) 

24) Differentiate b/w Traveling Salesman Problem(TSP) and Dijkstra’s Algorithm. In TSP, given n cities with known distances b/w each pair , find the shortest tour that passes  through all the cities exactly once before returning to the starting city.  

In Dijkstra’s Algorithm, find the shortest path from source vertex to all other remaining vertices 25) Differentiate b/w Prim’s Algorithm and Dijkstra’s Algorithm? 

Prim’s algorithm is to find minimum cost spanning tree. 

Dijkstra’s algorithm is to find the shortest path from source vertex to all other remaining vertices.

26) What are the applications of Dijkstra’s Algorithm? 

It finds its application even in our day to day life while travelling. 

They are helpful in routing applications. 

27) Who was the inventor of the Quicksort? 

C.A.R.HOARE, a British Scientist. 

28) Which design strategy does Quicksort uses? 

Divide and Conquer 

29) What is Divide and Conquer Technique? 

(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 these solutions 

30) What is the another name for Quicksort? 

Partition Exchange Sort 

31)Is Quicksort Stable as well as In place? 

Not Stable but In place. 

32) When do you say that a Quick sort having best case complexity? 

When the pivot exactly divides the array into equal half 

33) When do you say that Quick sort having worst case complexity? 

When any one of the subarray is empty 

34) How many more comparisons are needed for average case compared to best case? 38% more 

35) 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 >= pivot. 

36) What technique does kruskal’s algorithm follow. 

Greedy technique 

37) What is the time complexity of kruskal algorithm. 

With an efficient sorting algorithm, the time efficiency of an kruskal’s algorithm will be in  O(|E|log|E|). 

38) Who is the inventor of kruskal’s algorithm. 

Joseph Kruskal.

39) Which technique is used to solve BFS & DFS problems? 

Decrease and Conquer 

40) What is DFS traversal? 

Consider an arbitrary vertex v and mark it as visited on each iteration, proceed to an unvisited  vertex w adjacent to v. we can explore this new vertex depending upon its adjacent information.  This process continues until dead end is encountered.(no adjacent unvisited vertex is available).  At the dead end the algorithm backs up by one edge and continues the process of visiting  unvisited vertices. This process continues until we reach the starting vertex. 

41) What are the various applications of BFS & DFS tree traversal technique? Application of BFS 

Checking connectivity and checking acyclicity of a graph. 

Check whether there is only one root in the BFS forest or not. 

If there is only one root in the BFS forest, then it is connected graph otherwise disconnected  graph. 

For checking cycle presence, we can take advantage of the graph's representation in the form of a  BFS forest, if the latter vertex does not have cross edge, then the graph is acyclic.

Application of DFS 

To check whether given graph is connected or not. 

To check whether the graph is cyclic or not. 

To find the spanning tree. 

Topological sorting. 

42) Which data structures are used in BFS & DFS tree traversal technique? We use Stack data structure to traverse the graph in DFS traversal. 

We use queue data structure to traverse the graph in BFS traversal. 

43) What is Dynamic Programming? 

It is a technique for solving problems with overlapping sub problems. 

44) What does Dynamic Programming have in common with Divideand Conquer? 

Both solve the problems by dividing the problem into sub problems. Using the solutions of sub  problems, the solutions for larger instance of the problem can be obtained.

45) What is a principle difference between the two techniques?

Only one instance of the sub problem is computed & stored. If the same instance of sub problem  is encountered, the solution is retrieved from the table and never recomputed. Very precisely re - computations are not preformed. 

46) What is a spanning tree ? 

A spanning tree of a weighted connected graph is a connected acyclic(no cycles) subgraph (i.e. a  tree)that contains all the vertices of a graph and number of edges is one less than number of  vertices. 

47) What is a minimum spanning tree ? 

Minimum spanning tree of a connected graph is its spanning tree of smallestweight. 48) Prim’s algorithm is based on which technique. 

Greedy technique. 

49) 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, to pass the data from one node to another node we can find the shortest  distance easily by this algorithm. Communication Networks: Suppose there are 5 different cities  and we want to establish computer connectivity among them, then we take into the account of 

cost factor for communication links. Building a road network that joins n cities with minimum  cost. 

50) Does Prim’s Algorithm always yield a minimum spanning tree ? 

Yes 

51) What is the purose of Floyd’s algoreithm? 

- To find the all pair shortest path. 

52) What is the time efficiency of floyd’s algorithm? 

- It is same as warshall’s algorithm that is θ(n3). 

53) What is shortest path? 

- It is the path which is having shortest length among all possible paths. 

54) warshall’s algorithm is optimization problem or non-optimization problem ? Non-optimization problem 

55) For what purpose we use Warshall’s algorithm? 

Warshall’s algorithm for computing the transitive closure of a directed graph 56) Warshall’s algorithm depends on which property?\

Transitive property 

57) what is the time complexity of Warshall’s algorithm? 

Time complexity of warshall’s algorithm is θ(n3). 

58) what is state space tree? 

Constructing a tree of choices being made and processing is known as state-spacetree. Root represents an initial state before the search for solution begins. 60) what are promising and non-promising state-space-tree? Node which may leads to solution is called promising. 

Node which doesn’t leads to solution is called non-promising. 

61) What are the requirements that are needed for performing Backtracking? Complex set of constraints. They are: 

i. Explicit constraints. 

ii. Implicit constraints.