Important short questions and answers: Sorting and Searching

1. What is maxheap?

If we want the elements in the more typical increasing sorted order, we can change the ordering property so that the parent has a larger key than the child. it is called max heap.

2. What is divide and conquer strategy?

In divide and conquer strategy the given problem is divided into smaller problems and solved recursively. The conquering phase consists of patching together the answers. Divide and conquer is a very powerful use of recursion that we will see many times.

3. Differentiate between merge sort and quick sort?

Mergesort

1.Divide and conquer strategy 2.Partition by position Quicksort

1. Divide and conquer strategy

2. Partition by value

4. Mention some methods for choosing the pivot element in quicksort?

1. Choosing first element

2. Generate random number

3. Median of three

5. What are the three cases that arise during the left to right scan in quicksort?

I and j cross each other

I and j do not cross each other

I and j points the same position

6. What is the need of external sorting?

External sorting is required where the input is too large to fit into memory. So external sorting is necessary where the program is too large. It is a basic external sorting in which there are two inputs and two outputs tapes.

7. Define multi way merge?

If we have extra tapes then we can expect to reduce the number of passes required to sort

8. Define polyphase merge?

The k-way merging strategy requires the use of 2 k tapes. This could be prohibitive for some applications. It is possible to get

9. What is replacement selection?

We read as many records as possible and sort them. Writing the result to some tapes. This seems like the best approach possible until one realizes that as soon as the first record is written to a output tape the memory it used becomes available for another record. If the next record on the input tape is larger than the record we have just output then it can be included in the item. Using this we can give algorithm. This is called replacement selection.

10. What is sorting?

Sorting is the process of arranging the given items in a logical order. Sorting is an example where the analysis can be precisely performed.

11. What is mergesort?

The mergesort algorithm is a classic divide and conquer strategy. The problem is divided into two arrays and merged into single array

12. What are the properties involved in heapsort?

1.Structure property 2.Heap order property

13. Define articulation points.

If a graph is not biconnected, the vertices whose removal would disconnect the graph are known as articulation points. An expression tree is a binary tree in which the operands are attached as leaf nodes and operators become the internal nodes.

14. What is an acyclic graph?

A simple diagram which does not have any cycles is called an acyclic graph.

15. Give some example of NP complete problems.

·        Hamiltonian circuit.

·        Travelling salesmen problems

16.            What are AVL trees?

An AVL tree is a binary search tree with a balancing condition.For every node in the tree the heigh of the left and right subtrees can differ at most by 1.The height of an empty tree is defined to be -1.It ensures that the depth of the tree is O(log N)

17. What is topological sort?

A topological sort is an ordering of vertices in a directed acyclic graph, such that if there is a path from vi then vj appears after vi in the ordering.

18.What is single source shortest path problem?

Given as an input a weighted graph, G=(V,E) and a distinguished vertex,’s’ find the shortest weighted path from ‘s’ to every other vertex in G.

19.Mention some shortest –path problems.

·        Unweighted shortest paths

·        Dijikstra’s algorithm

·        All-pairs shortest paths

20.            Define threaded Binary Tree.

A binary tree is threaded by making all right child pointers that would normally be null point to the inorder successor of the node, and all left child pointers that would normally be null point to the inorder predecessor of the node.