Algorithms: Question Set – 13

Algorithms: Question Set – 13

What is the maximum and minimum problem?

The objective of this problem is to determine which items in a set of ‘n’ elements are the most and least numerous. Even while this problem can appear to be so straightforward that it was invented, it actually gives us the opportunity to demonstrate divide and conquer in a straightforward context.

What is the Quick sort?

Quicksort is a divide-and-conquer method that operates by splitting the elements that are fed into it based on their value in comparison to some element that has been picked in advance (pivot). Recursion is utilised in this method, which is also referred to as the partition-exchange sort.

what is Merge sort? and Is insertion sort better than the merge sort?

  • Merge sort is divide and conquer strategy that works by dividing an input array into two halves, sorting them recursively and then merging the two sorted halves to get the original array sorted
  • Insertion sort works exceedingly fast on arrays of less than 16 elements, though for large ‘n’ its computing time is O(n2).

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

Algorithm BINARY_SEARCH(A, n, key)
// Given an array A[1:n] of elements in nondecreasing
// order, n > 0, determine whether key is present

low := 1
high := n
while (low < high) do
    mid : = [(low+high)/2]
    if(x < a[mid]) then 
        high:= mid-1
    else if (x > a[mid]) then 
        low:=mid + 1
    else 
        return mid;
return False

Specify the algorithms used for constructing Minimum cost spanning tree.

  • Prim’s Algorithm
  • Kruskal’s Algorithm

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

Find the shortest paths from one vertex in a weighted connected graph, which is referred to as the source, to each of the other vertices in the graph. The approach developed by Dijikstra can only be used to graphs with positive weights.

Define forest.

The collection of sub-trees that remain after the root node has been removed is referred to as the forest.

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)