CS2251 -DESIGN AND ANALYSIS OF ALGORITHMS UNIT II QUESTIONS

UNIT II

1) Explain divide and conquer algorithms

Divide and conquer is probably the best known general algorithm design technique. It work according to the following general plan

i)A problem's instance is divided into several smaller instances of the same problem, ideally of about the same size.

ii) The smaller instances are solved

iii) If necessary, the solutions obtained for the smaller instances are combined to get a solution to the original problem

2) Define Merge Sort

Merge sort is a perfect example of a successful application of the divide and conquer technique. It sorts a given array A[0...n-l] by dividing it into two halves A[0...[n/2] - 1] and A[[n/2]....n-l], sorting each of them recursively, and then merging the two smaller sorted arrays into a single sorted one.

3) Define Binary Search

Binary Search is remarkably efficient algorithm for searching in a sorted array. It works by comparing a search key K with the array's 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 for the second half if K > A[m]

A[0].............A[m-l] A[m] A[m+l]............. A[n-l]

4) What can we say about the average case efficiency of binary search?

A sophisticated analysis shows that the average number of key comparisons made by binary search is only slightly smaller than that in the worst case

C_avg(n) » log₂n

5) Define Binary Tree

A binary tree T is defined as a finite set of nodes that is either empty or consists of s root and two disjoint binary trees t_L, and t_r called, respectively the left and right subtree of the root.

     6) How divide and conquer technique can be applied to binary trees?

Since the binary tree definition itself divides a binary tree into two smaller structures of the same type, the left subtree and the right subtree, many problems about binary trees can be solved by applying the divide-conquer technique.

7) Explain Internal and External Nodes

To draw the tree's extension by replacing the empty subtrees by special nodes.The extra nodes shown by little squares are called external. The original nodes shown by littile circles are called internal.

8) Define Preorder, inorder and postorder Traversal

PREORDER -The root is visited before the left and right subtrees are visited (in that order)

INORDER -The root is visited after visiting its left subtree but before visiting the right Subtree

POSTORDER - The root is visited after visiting the left and right subtrees(in that order)

9) Define the Internal Path Length

The Internal Path Length I of an extended binary tree is defined as the sum of the lengths of the paths - taken over all internal nodes- from the root to each internal node.

10) Define the External Path Length

The External Path Length E of an extended binary tree is defined as the sum of the lengths of the paths - taken over all external nodes- from the root to each external node.

11) Explain about greedy technique

The greedy technique suggests constructing a solution to an optimization problem through a sequence of steps, each expanding a partially constructed solution obtained so far, until a complete solution to the problem is reached. On each step, the choice made must be feasible, locally optimal and irrevocable.

12) Define Spanning Tree

A Spanning Tree of a connected graph is its connected acyclic subgraph(i.e., a tree) that contains all the vertices of the graph.

13) Define Minimum Spanning Tree

A minimum spanning tree of a weighted connected graph is its spanning tree of the smallest weight ,where the weight of a tree is defined as the sum of the weights on all its edges.

14) Define min-heap

A min-heap is a complete binary tree in which every element is less than or equal to its children. All the principal properties of heaps remain valid for min-heaps, with some obvious modifications.

15) Define Kruskal's Algorithm

Kruskal's algorithm looks at a minimum spanning tree for a weighted connected graph G =(V,E) as an acyclic subgraph with | V| - 1 edges for which the sum of the edge weights is the smallest.

16) Define Prim's Algorithm

Prim's algorithm is a greedy algorithm for constructing a minimum spanning tree of a weighted connected graph.It works by attaching to a previously constructed subtree a vertex to the vertices already in the tree.

17) Explain Dijkstra's Algorithm

Dijkstra's algorithm solves the single - source shortest - path problem of finding shortest paths from a given vertex (the source) to all the other vertices of a weighted graph or digraph. It works as prim's algorithm but compares path lengths rather than edge lengths. Dijkstra's algorithm always yields a correct solution for a graph with nonnegative weights.