Madhumitha

BACKTRACKING                    Backtracking is an algorithmic-technique for solving problems recursively by trying to build a solution incrementally, one piece at a time, removing those solutions that fail to satisfy the constraints of the problem at any point of time (by time, here, is referred to the time elapsed till reaching any level of the search tree). Backtracking can be defined as a general algorithmic technique that considers searching every possible combination in order to solve a computational problem.  There are three types of problems in backtracking – Decision Problem – In this, we search for a feasible solution. Optimization Problem – In this, we search for the best solution. Enumeration Problem – In this, we find all feasible solutions.   PSEUDO CODE: 1. Recursive backtracking solution. void findSolutions(n, other params) : if (found a solution) : sol...

 INSERTION SORT:                  Insertion sort is a simple sorting algorithm that works similar to the way you sort playing cards in your hands. The array is virtually split into a sorted and an unsorted part. Values from the unsorted part are picked and placed at the correct position in the sorted part.   EXAMPLE:   RECURSION IDEA: Base Case: If array size is 1 or smaller, return. Recursively sort first n-1 elements. Insert last element at its correct position in sorted array.   ALGORITHM: We are going to mimic the Iterative Insertion sort in the recursive implementation. We will create a function which will take the array and current index as input. In this function we will iterate through all the elements less than the current index and swap the elements based on the sorting order. If the index is less than 1 then will terminate the recu...