Posts

Backtracking with N-Queen Problem

-
Image
  Backtracking Introduction Recursion, a fundamental concept in computer science and mathematics, is both a fascinating and powerful technique that enables us to solve complex problems by breaking them down into simpler, more manageable sub problems. Derived from the Latin word "recursion," meaning "returning," recursion is a concept deeply woven into the fabric of computer programming and mathematical thinking. In this exploration, we delve into the captivating world of recursion, understanding its principles, applications, and the profound impact it has had on various fields. At its core, recursion is a process where a function calls itself to solve a problem. This self-referential property distinguishes recursion from traditional iterative approaches. Imagine a set of Russian nesting dolls, where each doll contains a smaller doll inside it. Recursion operates in a similar manner, as a problem is broken down into smaller, similar sub problems, which ...
Post a Comment
Read more

Greedy Algorithm

-
Image
            The greedy method is one of the strategies like Divide and conquer used to solve the problems. This method is used for solving optimization problems. An optimization problem is a problem that demands either maximum or minimum results. Let's understand through some terms. The Greedy method is the simplest and straightforward approach. It is not an algorithm, but it is a technique. The main function of this approach is that the decision is taken on the basis of the currently available information. Whatever the current information is present, the decision is made without worrying about the effect of the current decision in future. This technique is basically used to determine the feasible solution that may or may not be optimal. The feasible solution is a subset that satisfies the given criteria. The optimal solution is the solution which is the best and the most favorable solution in the subset. In the case of feasible, if more ...
Post a Comment
Read more

Quick sort in Divide and Conquer

-
Image
It is an algorithm of Divide & Conquer type. Divide: Rearrange the elements and split arrays into two sub-arrays and an element in between search that each element in left sub array is less than or equal to the average element and each element in the right sub- array is larger than the middle element. Conquer: Recursively, sort two sub arrays. Combine: Combine the already sorted array. Algorithm: QUICKSORT (array A,  int  m,  int  n)      1   if  (n > m)      2  then      3  i ← a random index from [m,n]      4  swap A [i] with A[m]      5  o ← PARTITION (A, m, n)      6  QUICKSORT (A, m, o -  1 )     7  QUICKSORT (A, o +  1 , n) ...
Post a Comment
Read more

Merge Sort in Divide and Conquer

-
Image
  Merge Sort Merge sort is yet another sorting algorithm that falls under the category of Divide and Conquer technique. It is one of the best sorting techniques that successfully build a recursive algorithm. Divide and Conquer Strategy In this technique, we segment a problem into two halves and solve them individually. After finding the solution of each half, we merge them back to represent the solution of the main problem. Suppose we have an array A , such that our main concern will be to sort the subsection, which starts at index p and ends at index r , represented by A[p..r] . Divide If assumed q to be the central point somewhere in between p and r , then we will fragment the subarray A[p..r] into two arrays A[p..q] and A[q+1, r] . Conquer After splitting the arrays into two halves, the next step is to conquer. In this step, we individually sort both of the subarrays A[p..q] and A[q+1, r] . In case if we did not reach the base situation, then we again follow the ...
Post a Comment
Read more